There are 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 card is showing its black side. Answer and prove:
(a) If , can all the cards be made to show white side up through a finite number of operations?
(b) If , can all the cards be made to show white side up through a finite number of operations?
Solution
(a) For , you can make all cards white-side-up.
Label the cards from to in order. WLOG assume the only black card initially is . Consider the following moves (B=black, W=white):
* B, W, B
* B, B, W, B
* B, B, B, W, B
* ...
* B, B, ..., B, W, B
* W, B, B, ..., B, W.
Now, there are consecutive black-side-up cards. Group them by three, and flip them over in groups (which takes moves), and we get all cards white-side-up.
(b) For , you cannot make all cards white-side-up.
Label the card as in order; note that there are equal numbers of and . Now, for each move, you always flip an , an , and a . Suppose the initial black-side-up card is labelled . Then, you need an odd number of moves to let all white-side-up, but you need an even number of moves to let all (or ) card white-side-up. So it is impossible.