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: My solution by nikki)

Yes, the exhaustive proof is

DECLARE SUB try (n!)
DECLARE FUNCTION lcm! (a!, b!)
DECLARE FUNCTION gcd! (a!, b!)
DIM SHARED hist(21), tot

FOR n = 2 TO 19
 hist(1) = n: tot = n
 try 1
NEXT

FUNCTION gcd (a, b)
 dnd = a
 dvr = b
 DO
  r = dnd MOD dvr
  dnd = dvr
  dvr = r
 LOOP UNTIL r = 0
 gcd = dnd
END FUNCTION

FUNCTION lcm (a, b)
 lcm = a * b / gcd(a, b)
END FUNCTION

SUB try (n)
 STATIC lmax
 IF tot = 21 THEN
   l = hist(1)
   FOR i = 1 TO n
    l = lcm(l, hist(i))
   NEXT
   IF l > lmax THEN
    t = 1
    lmax = l
    PRINT
    FOR i = 1 TO n
      PRINT hist(i);
    NEXT
    PRINT : PRINT l
   END IF
 ELSE
   IF 21 - tot >= hist(n) THEN
     FOR addIn = hist(n) TO 21 - tot
      tot = tot + addIn
      hist(n + 1) = addIn
      try n + 1
      tot = tot - addIn
     NEXT
   END IF
 END IF
END SUB

which tries all the ways of different numbers, in ascending sequence, can add up to 21, and keeps track of the highest product thus far.  Its successive "bests" end up with your solution:

2  2  2  2  2  2  2  2  2  3
6

2  2  2  2  2  2  2  2  5
10

2  2  2  2  2  2  2  3  4
12

2  2  2  2  2  2  2  7
14

2  2  2  2  2  2  4  5
20

2  2  2  2  2  3  3  5
30

2  2  2  2  3  3  7
42

2  2  2  3  3  4  5
60

2  2  2  3  5  7
210

2  3  4  5  7
420

Posted by Charlie on 2004-03-19 16:07:02