Let $n$ cards are placed in a circle. Each card has a white side and a black side. On each move, you pick one card with black side up, flip it over, and also flip over the two neighboring cards. Suppose initially, there are only one black-side-up card. (a)If $n=2015$ , can you make all cards white-side-up through a finite number of moves? (b)If $n=2016$ , can you make all cards white-side-up through a finite number of moves?
Problem
Source: 2016 Taiwan 1st TST Quiz 2 P1
Tags: combinatorics
fractals
01.08.2016 22:22
This generalizes to $n\equiv 2\pmod{3}$ and $n\equiv 0\pmod{3}$ (of course, $n\ge 3$). We shall do $n\equiv 1\pmod{3}$ as well.
Call black cards $1$ and white cards $0$.
a) Yes. Flip the card. Then we have $101$. Then flip the right one, and we have $1101$. Flip the right one again, and we have $11101$. Continue until we have $111\cdots 101$, where there are $n - 1$ ones and one zero. Now flip the rightmost one, and since it wraps, we have $011\cdots 110$, with two consecutive zeroes. Now we have $n - 2$ ones in the center, and we can simply partition it into blocks of three to flip over. We win. This works for all $n\equiv 2\pmod{3}$ with $n \ge 3$.
a') Now we assume $n\equiv 1\pmod{3}$ and $n\ge 3$. The same works: once we get to $111\cdots 101$, with $n - 1$ ones and a zero, we can immediately group into threes and win.
b) Let our numbers be $a_0, \ldots, a_{2015}$ and consider $P(x) = a_{2015}x^{2015} + \cdots + a_1x + a_0$ in $\mathbb{F}_2[x]/(x^{2016} - 1)$. That is, consider it as a polynomial with coefficients modulo two, and then consider modulo $x^{2016} - 1$. Assume that initially, $a_0 = 1$ and the rest are zero.
Every operation that we do adds some $x^i(x^2 + x + 1)$, for $0 \le i \le 2015$, taking modulo $x^{2016} - 1$. Thus, we are constrained to $P(x) \equiv 1 \pmod{x^2 + x + 1}$ over $\mathbb{F}_2$. Now we win; if all cards are white, then $P(x) = 0$, a contradiction!
Ali3085
12.05.2020 00:22
here's my solution: claim(1): if $n \equiv 0 \bmod 3$ then you can't make all cards white-side-up through a finite number of moves proof: label the cards $0,1,-1,0,1,-1 \dots$ such that the initial black card is $1$ and let every card have zero on its blackside and one on its white one and mutlipe the number on the card with the label of the card and sum up this for every card amd let it be $S$ first $S=-1$ and in the final $S$ must be zero but it's easy to see that in every step $S$ is invarient $\bmod 2$ $\blacksquare$ claim(2): if $n \equiv 1 ,2 \bmod 3 $ then you can make all cards white-side-up through a finite number of move the strategy: first flip over the black one and start clockwise and flip over every black card once until we have all the cards are black and one is white if: $n \equiv 1 \bmod 3$ then : split the blacks onto triple blocks and flip over every card in the middle of every triple if: $n \equiv 2 \bmod 3$ then : split over the black card that's neighbor to the white and same as previous $\blacksquare$ and we win
pad
06.08.2020 09:03
Solved with dantaxyz. (a) Yes. Call black cards 1 and white 0. Perform \[ 0100\ldots 00 \to 1010\ldots 0 \to 11010 \ldots 0 \to \cdots \to 11\ldots 1101. \]Now toggle the last 1, to get $011\ldots 10$. Since there are $3\mid n-2$ ones in the middle, we can demolish $111\to 000$ repeatedly to end with all 0's. (b) No. Call the $i$th position $x_i$. It is easy to see that \[ S=(x_1,\ldots,x_n)\cdot (-1,0,1,-1,0,1,\ldots)\]is invariant mod 2, by doing casework on $i\mod 3$, where we toggle the $i$th bit. Clearly, $S$ is different at $(1,0,\ldots,0)$ and at $(0,0,\ldots,0)$, so it is impossible.
The construction is the hard part.