Maths Olympiad Prep

Library / /392 of 397

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Taiwan

There are nn cards placed on the table in a circle. Each card has one side black and the other side white. Define one operation as follows: choose a card that is showing its black side, and simultaneously flip it together with the two cards adjacent to it. Suppose that at the start, only 11 card is showing its black side. Answer and prove:
(a) If n=2015n = 2015, can all the cards be made to show white side up through a finite number of operations?
(b) If n=2016n = 2016, can all the cards be made to show white side up through a finite number of operations?

Solution

(a) For n=2015n = 2015, you can make all cards white-side-up.
Label the cards from 11 to 20152015 in order. WLOG assume the only black card initially is 22. Consider the following moves (B=black, W=white):
* 11B, 22W, 33B
* 11B, 22B, 33W, 44B
* 11B, 22B, 33B, 44W, 55B
* ...
* 11B, 22B, ..., 20132013B, 20142014W, 20152015B
* 11W, 22B, 33B, ..., 20142014B, 20152015W.
Now, there are 20132013 consecutive black-side-up cards. Group them by three, and flip them over in groups (which takes 2013/3=6712013/3 = 671 moves), and we get all cards white-side-up.

(b) For n=2016n = 2016, you cannot make all cards white-side-up.
Label the card as α,β,γ,α,β,γ,\alpha, \beta, \gamma, \alpha, \beta, \gamma, \dots in order; note that there are equal numbers of α,β\alpha, \beta and γ\gamma. Now, for each move, you always flip an α\alpha, an β\beta, and a γ\gamma. Suppose the initial black-side-up card is labelled α\alpha. Then, you need an odd number of moves to let all α\alpha white-side-up, but you need an even number of moves to let all β\beta (or γ\gamma) card white-side-up. So it is impossible.

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 translated into English from zh; metadata (topic, difficulty) added by this project.