Tuesday, 03 December, 2002

A Puzzle

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:

  1. Each table is to seat the same number of prisoners.
  2. 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?