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?

(In reply to re: No Subject by Alec Lanter)

You know Alec, I re-thought it, and now I'm not so sure.  The 21 circles could be arranged into as many as 7 sets of 3 circles each.  That would still satisfy the arrow rule.

I think the way to get the most jumps out of this problem is to form two large circles, one made of ten smaller circles, and the other made of 11 smaller circles. 

That way, when the monkeys in the "ten circle" have reached their starting place (on the 10th blow of the whistle), the monkeys in the "eleven circle" will be one circle before their starting place.  So on the next blow, the "ten" monkeys jump to one past the start, while the "eleven" monkeys jump to their starting place.

In order to make them both land on the starting place on the same whistle blow, it will take 110 blows.

Posted by Lisa on 2004-04-27 17:55:10