On a table there are 2016 coins standing in a row. The first half being made of coins placed up while the other half of coins is placed down. The purpose of the game is to place this coins such that their positions alternate: up-down-up-down and so on. There is only one type of move that can be done that being turning simultaneously 2 adjacent coins. What is the minimum number of moves necessary to obtain the alternate up-down configuration for the coins?
Bonus : Generalize this for coins.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Take 4 coins placed up. Let us say all heads ,i.e HHHH . Now in two moves we get HTHT hence in the required position .
Similarly for the position TTTT we can get HTHT in 2 moves.
Hence the combination gives 8 coins with half up and half down to be arranged as desired in a total of 4 moves.
Consider an odd number of halves like HHH . Clearly it is not possible to make it HTH. Similarly take TTT . It is not possible to make it THT .Hence we cannot form HTHTHT by splitting the coins into halves. Hence this way is not suitable where the number of coins is not a multiple of 4.
Now take 2016 coins(a multiple of 4) .1008 of them are placed up. We can divide that into 252 groups of 4 and further each group can be rearranged with 2 moves. Hence we have rearranged the first half with 504 moves.
Similarly the other half can also be rearranged (as mentioned above in TTTT ) within 504 moves.
Hence total number of moves required =1008
This cannot be done with any moves less as atleast 1008 coins has to be flipped and only one pair is adjacent (in exactly the middle position),but that will not be possible as there will be two halves with odd number of coins which will be impossible to rearrange in desired way as said above.