Coins game

Logic Level 4

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 $n$ coins.

The answer is 1008.

2 solutions

Abin Das
Aug 10, 2016

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.

Your reasoning for the case of a sequence made from n coins where n is divisible with 4 can be said to be right.

For the general case though your reasoning that for any 2m = n with m being odd there isn't any solution anyway is erroneous. For example taking n=6 , as you proposed in your proof , can you think of a sequence of moves by which you can arrive at HTHTHT though ? If you are attentive enough you will certainly conclude that there is such a sequence and maybe by the observations made you will even be able to generalize the problem right.

A A - 4 years, 10 months ago

Ante Svaguša
Jun 5, 2016

When number is even we turn every even coulumn ,when number is odd we turn every odd column. (If you count from top of first row down to bottom, then from top of second row down to the bottom, solution will be true).

I suppose that you mean by column that odd the even coins in the row in which case what you say sounds pretty convenient but needs to be justified and proved because the truth is in reason.

And I'm not pretty sure about the parentheses in which you say that the first row is in some way anyway because there is only one row so maybe after all you understood wrongly the problem.

A A - 5 years ago

I devided first 1008 coins who are placed up and in the second column 1008 coins which are placed down.

Ante Svaguša - 5 years ago

But you can't divide them in two 2 columns because that is not an allowed move , all that anyway can be done is to change 2adjacent coins from the unmodified row I mean anyway.

You should solve this problem by respecting conditions the coins stay in a row and the only move allowed is to change 2 adjacent coins anyway.

A A - 5 years ago

@A A – Its just for simplier explanation it doesnt change anything its only about perception

Ante Svaguša - 5 years ago

@Ante Svaguša – Oh , well ok then.

Yet , you should state that in the problem.

Still , you have to explain why by changing them like that you obtain the up-down configuration because by this you explain your claim anyway.

That is the most important part of the proof because otherwise the claim is not justified and therefore would be just like saying something whose validity isn't verified by reason anyway.

A A - 5 years ago

Coins game

The answer is 1008.

2 solutions

0 pending reports