All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Monkey Dance 1 (Posted on 2004-03-19)
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?

 See The Solution Submitted by Sandeep Rating: 4.1667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(4): My solution | Comment 6 of 30 |
(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); lmaxNEXT goalTot`
`FUNCTION gcd (a, b) dnd = a dvr = b DO  r = dnd MOD dvr  dnd = dvr  dvr = r LOOP UNTIL r = 0 gcd = dndEND 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 IFEND SUB`

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

 Search: Search body:
Forums (2)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: