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(3): My solution by Gamer)

Here's a list of the best that can be done with varying numbers of circles from 6 to 50:

 6     2  4                   4
 7     3  4                   12
 8     3  5                   15
 9     4  5                   20
 10    2  3  5                30
 11    5  6                   30
 12    3  4  5                60
 13    6  7                   42
 14    3  4  7                84
 15    3  5  7                105
 16    4  5  7                140
 17    2  3  5  7             210
 18    5  6  7                210
 19    3  4  5  7             420
 20    5  7  8                280
 21    2  3  4  5  7          420
 22    3  3  4  5  7          420
 23    3  5  7  8             840
 24    7  8  9                504
 25    4  5  7  9             1260
 26    3  5  7  11            1155
 27    4  5  7  11            1540
 28    2  3  5  7  11         2310
 29    5  7  8  9             2520
 30    3  4  5  7  11         4620
 31    5  7  8  11            3080
 32    3  4  5  7  13         5460
 33    3  3  4  5  7  11      4620
 34    3  5  7  8  11         9240
 35    7  8  9  11            5544
 36    4  5  7  9  11         13860
 37    3  3  5  7  8  11      9240
 38    4  5  7  9  13         16380
 39    3  5  7  11  13        15015
 40    5  7  8  9  11         27720
 41    2  3  5  7  11  13     30030
 42    5  7  8  9  13         32760
 43    3  4  5  7  11  13     60060
 44    5  7  8  11  13        40040
 45    2  3  4  5  7  11  13  60060
 46    3  3  4  5  7  11  13  60060
 47    3  5  7  8  11  13     120120
 48    7  8  9  11  13        72072
 49    4  5  7  9  11  13     180180
 50    3  3  5  7  8  11  13  120120

Rarely do duplicated numbers appear.  Of course they add nothing, any more than a 2 on a list that contains 4, but they use up the remainder of the circles.

DECLARE SUB try (n!)
DECLARE FUNCTION lcm! (a!, b!)
DECLARE FUNCTION gcd! (a!, b!)
CLEAR , , 4000

DIM SHARED hist(200), histMax(200), tot

DIM SHARED goalTot, lmax, nForMax

FOR goalTot = 6 TO 50
  lmax = 0
  FOR n = 2 TO goalTot - 2
   hist(1) = n: tot = n
   try 1
  NEXT
  t = 0
  FOR i = 1 TO nForMax
    t = t + histMax(i)
  NEXT
  PRINT t; TAB(7);
  FOR i = 1 TO nForMax
    PRINT histMax(i);
  NEXT
  PRINT TAB(30); lmax
NEXT goalTot

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)
 IF tot = goalTot THEN
   l = hist(1)
   FOR i = 1 TO n
    l = lcm(l, hist(i))
   NEXT
   IF l > lmax THEN
    t = 1
    lmax = l
    FOR i = 1 TO n
      histMax(i) = hist(i)
    NEXT
    nForMax = n
   END IF
 ELSE
   IF goalTot - tot >= hist(n) THEN
     FOR addIn = hist(n) TO goalTot - tot
      tot = tot + addIn
      hist(n + 1) = addIn
      try n + 1
      tot = tot - addIn
     NEXT
   END IF
 END IF
END SUB

Posted by Charlie on 2004-03-19 22:57:41