The director of a circus has decided to add a new performance, the monkey dance, to his show.

The monkey dance is danced simultaneously by 21 monkeys.
There are 21 circles drawn on the ground, and in the beginning, each monkey sits on a different circle.
There are 21 arrows drawn from circle to circle in such a way that exactly one arrow starts and exactly one arrow ends in each circle. No arrow can both begin and end at the same circle.

When the show begins, the monkeys dance in their circles until the ringmaster blows his whistle. At each whistle blow, the monkeys simultaneously jump from their circles to the next, following the arrows. The dance ends when all the monkeys have returned to the circles where they initially started.

The director wishes the dance to last as long as possible. What is the maximum number of whistle blows he can make before the dance ends?

Because each circle has exactly one arrow entering and one arrow leaving, and the monkeys each end up in their original circle at some point, the circles have to be connected in (non-overlapping) larger circles of arrows. All the monkeys will end up in their original circles after a number of whistle blows equal to the least common multiple of those larger circle sizes. For instance, if you have three circles of sizes 3, 6, and 12, then the factors are 3, 2*3, and 2*2*3, so the LCM will be 2*2*3 == 12. Similarly, if you have two circles of sizes 10 and 11 (2*5 and 11), the LCM will be 2*5*11 == 110.

This issue, then, is to find the combination of circles, with sizes adding up to exactly 21 and not including any circles of size 1, that has the largest LCM. Here is a list of the possible combinations of circle sizes, after stripping all combinations that include multiple circles of the same size (the reason behind this is that a combination of A, A, B will never give you a larger LCM than 2A, B):

2 19
3 18
4 17
5 16
6 15
7 14
8 13
9 12
10 11

2 3 16
2 4 15
2 5 14
2 6 13
2 7 12
2 8 11
2 9 10
3 4 14
3 5 13
3 6 12
3 7 11
3 8 10
4 5 14
4 6 13
4 7 12
4 8 11
4 9 10
5 6 12
5 7 11
5 8 12
5 9 11
6 7 8

2 3 4 12
2 3 5 11
2 3 6 10
2 3 7 9
2 4 5 10
2 4 6 9
2 4 7 8
2 5 6 8
3 4 5 8
3 4 6 7
3 5 6 7

2 3 4 5 7

It's a fairly simple matter to plug-n-chug all of these into a calculator to see which one gives you the highest LCM. The answer I found was the last one, with an lcm of 2*2*3*5*7, or 420.

Posted by Robin on 2004-05-08 17:16:12