There are $2015$ coins on a table. For $i = 1, 2, \dots , 2015$ in succession, one must turn over exactly $i$ coins. Prove that it is always possible either to make all of the coins face up or to make all of the coins face down, but not both.
Problem
Source: Saudi Arabia IMO TST Day III Problem 3
Tags: combinatorics unsolved, combinatorics
23.07.2014 00:36
Note that flipping a coin twice doesn't do anything. For whatever target configuration we want, we know exactly which coins must be flipped and hence the parity of the number of flips. Appending any number of double-flips doesn't change the parity of the total number of flips we need, so a target configuration can be classified as "even" or "odd" depending on the parity of the number of moves required to reach that configuration. Suppose that we can make all coins face up, then to make them face down we need an additional $2015$ flips, an odd number. But this means the configuration of all up and of all down belong to two different classifications, while we make exactly $2015 \times 1008$ flips, an even number, so only the even configuration among these two can be reached. Now we will prove that we can always reach this configuration. First, we identify whether the face up configuration is an even configuration or odd. WLOG it's even, otherwise reverse the meanings of "face up" and "face down". Now note that we can permute our moves; flipping a coin then another is the same as flipping that other coin before the first coin. In particular, we will do in the order $i=2015,2014,\ldots,1$. First, flip all coins, because $i=2015$. Now, for each $i$, observe the $i$-th coin; if it's face down, then turn over the first $i$ coins, otherwise turn over the first $i-1$ coins and the last coin. This guarantees that the $i$-th coin is face up after our move, and we will never touch it again, so it will be face up. Thus the first $2014$ coins are face up. And since we assume the face up configuration is an even one, the last coin has to be face up too at the end, otherwise it contradicts with our assumption. Thus we have proven that we can make the coins into a particular configuration, and thus cannot be the other.