Seating a Conference in Equal Rows
A conference has N attendees, where 200 < N < 400. Organizers testing room layouts find that when attendees are split into rows of 12, exactly 7 people are left over, and that when the same attendees are split into rows of 9, exactly 4 people are left over. Every attendee is seated, and rows must be complete apart from the leftover group. A venue coordinator claims the two facts pin down N exactly and that a third measurement is unnecessary. The organizers also need the smallest N above 1,000 that is consistent with both remainders, in case the conference is expanded next year.
1. Find every value of N with 200 < N < 400 satisfying both remainder conditions, and assess the coordinator's claim.
Read the worked answer
Write N = 12a + 7 for a nonnegative integer a.
Impose the mod 9 condition: 12a + 7 ≡ 4 (mod 9). Since 12 ≡ 3 and 7 ≡ 7, this is 3a + 7 ≡ 4, so 3a ≡ −3 ≡ 6 (mod 9). Dividing by 3 (legal mod 9 only when the modulus also divides by 3) gives a ≡ 2 (mod 3).
So a = 3k + 2 and N = 12(3k + 2) + 7 = 36k + 31. The solutions repeat every 36.
Scanning the range 200 < N < 400:
- k = 5 → 211
- k = 6 → 247
- k = 7 → 283
- k = 8 → 319
- k = 9 → 355
- k = 10 → 391
(k = 4 gives 175, too small; k = 11 gives 427, too large.) There are six candidates: 211, 247, 283, 319, 355, 391, each confirmed by 355 = 12(29) + 7 and 355 = 9(39) + 4, for example.
The coordinator is wrong: two congruences with moduli 12 and 9 determine N only modulo lcm(12, 9) = 36, so a bounded range typically contains many solutions. A third independent remainder would narrow it.
2. A third measurement shows N is divisible by 5. Which candidate survives, and why is the answer unique?
Read the worked answer
Test N ≡ 0 (mod 5) on the family N = 36k + 31. Since 36 ≡ 1 and 31 ≡ 1 (mod 5), the condition is k + 1 ≡ 0 (mod 5), i.e. k ≡ 4 (mod 5).
Among k = 5, 6, 7, 8, 9, 10 the only value congruent to 4 mod 5 is k = 9, giving N = 36(9) + 31 = 355.
Verification: 355 = 12(29) + 7 ✓, 355 = 9(39) + 4 ✓, 355 = 5(71) ✓.
Uniqueness is guaranteed here because 5 is coprime to lcm(12, 9) = 36: the combined modulus becomes lcm(12, 9, 5) = 180, which already exceeds the 200-wide search window's spacing - the three conditions together admit only one value below 400 (the next would be 355 + 180 = 535).
3. Find the smallest N greater than 1,000 consistent with the two original remainder conditions.
Read the worked answer
Use the family N = 36k + 31 and solve 36k + 31 > 1,000:
36k > 969 → k > 26.92 → smallest integer k = 27.
N = 36(27) + 31 = 972 + 31 = 1,003.
Check: 1,003 − 7 = 996 = 12 × 83 ✓; 1,003 − 4 = 999 = 9 × 111 ✓.
(For reference, k = 26 gives 967, which fails the bound.) The step from 391 is five more multiples of 36 - a reminder that 'smallest above X' requires rounding up on the multiplier, not on N itself, and that a naive estimate of about 1,000 must still be tested against both remainder conditions.