A set of 47 disks are consecutively numbered 1 to 47 and placed in a row as follows: 1, 2, 3, 4, ... 45, 46, 47.

Rearrange the disks so for any two given disks A and B, the disk equal to their arithmetic mean doesn't lie between them. For example, Disk 4 cannot lie between Disk 1 and Disk 7 since the arithmetic mean of 1 and 7 is 4. However, since 7 is not equal to the arithmetic mean of 1 and 4, Disk 7 may lie between Disk 1 and Disk 4.

to ilustrate my method I will use a simpler problem with 8 disks

there 8 places to place them

__ __ __ __ __ __ __ __

slit them in half

__ __ __ __ / __ __ __ __

start with disk 1 and work your way to disk 8

if disk n is odd it is placed on the left side, if it is even it is placed on the right side

now when placing disk n on its correct side do so in a "spiral" pattern like this

1 5 7 3 / 4 8 6 2

thus giving an answer of 1,5,7,3,4,8,6,2 for 8 disks

apply this process to 47 disks and you get

1,5,9,13,17,21,25,29,33,37,41,45,47,43,39,35,31,27,23,19,15,11,7,3
for the left odd half
and
2,6,10,14,18,22,26,30,34,38,42,46,44,40,36,32,28,24,20,16,12,8,4
for the right even half

just append the even list to the right of the odd list and you have a solution.  Now what I'm working on next is a more general solution as I'm sure there are several other solutions

Posted by Daniel on 2006-07-04 11:51:22