Tuesday, 03 December, 2002
My sister sent me this puzzle today.
A jailer has a large number of prisoners to guard and has to seat them at a number of tables at mealtimes. The regulations state the following seating arrangements:
- Each table is to seat the same number of prisoners.
- The number at each table is to be an odd number.
The jailer finds that when he seats the prisoners:
3 per table, he has 2 prisoners left over;
5 per table, he has 4 prisoners left over;
7 per table, he has 6 prisoners left over;
9 per table, he has 8 prisoners left over;
but when he seats them 11 per table there are none left over.
How many prisoners are there?
I spent an embarrassing amount of time trying to find 6 unknowns with a system of 5 equations before I realized that I was looking for a common multiple of 5, 7, and 9 (call it CM) that was one more than the number of prisoners. That is, CM is divisible by 5, 7, and 9, and CM-1 (the number of prisoners) is divisible by 11. The first such number is 2,520 (there are infinitely many), which is 5*7*9*8 (i.e. the 8th common multiple of 5, 7, and 9).
I think the key insight to the puzzle is that you're looking for a common multiple. But given that insight, is there some way (other than trial and error) to know that the answer can be found at the 8th common multiple?