Maths Olympiad Prep

Library / /49 of 54

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it China

There are nn (n2n \ge 2) coins in a row. If one of the coins is head, select an odd number of consecutive coins (or even 1 coin) with the one in head on the leftmost, and then flip all the selected coins upside down simultaneously. This is a move. No move is allowed if all nn coins are tails. Suppose nn coins are heads at the initial stage, determine if there is a way to carry out 2n+13\lfloor \frac{2^{n+1}}{3} \rfloor moves. (posed by Gu Bin)

Solution

The answer is possible.

For any configuration of the coins, we define a corresponding 01-sequence c1c2...cnc_1c_2...c_n of length nn as follows: ci=1c_i = 1, if the ii-th coin from the left is head, otherwise, ci=0c_i = 0. It is easy to see that the status of the nn coins has a one-to-one correspondence to such 01-sequences, so in the following, we will consider this sequence model instead.

Initially, the sequence is 11...1111...11, denoted by 1n1^n (with nn consecutive digits of 1). Similarly, 00...0000...00, denoted by 0n0^n (with nn digits of 0). For any 01-sequence with at least a digit "1", consider the following move: locate the first digit "1" from right to left in the sequence, then take the 01-subsequence from left to right starting this "1" of maximal odd length, and change the 01-parity in this subsequence just like flipping the coins in a move. Denote by ana_n the total number of moves in the way stated above. We claim: an=2n+13a_n = \lfloor \frac{2^{n+1}}{3} \rfloor.

When n=1n=1, it is easy to see that a1=1=223a_1 = 1 = \lfloor \frac{2^2}{3} \rfloor, proceed by induction. Assume ak=2k+13a_k = \lfloor \frac{2^{k+1}}{3} \rfloor holds for n=kn = k, i.e., ak=2k+13a_k = \lfloor \frac{2^{k+1}}{3} \rfloor.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.