Source

I got this problem from Rustan Leino, who got it from Radu Grigore. It may have been used as a problem in the 2009 Math Olympics.

I solved it and wrote up my solution.

Problem

There's a table with a row of 2009 cards. Each card has a red side and a blue side. We'll say that a card is red if the color on its visible face is red, and analogously for blue. Two players take turns making the following move: select any 50 consecutive cards where the left-most card is red, then flip each of those 50 cards (thus, for those 50 cards, turning red cards into blue cards and blue cards into red cards). Both players look at the cards from the same side of the table, so "left-most" means the same to both of the players. (That is, you can think of one end of the table as being designated as the left end.) When it's a player's turn, if that player can't make a move (that is, if there's no way to select 50 consecutive cards the left-most one of which is red), then that player loses and the other player wins. If you're one of the players and all cards are initially red, can you be sure to win, and if so, do you want to be the player who goes first or second?

Solution
Reveal

Yes, you can be sure to win. You want to go second.

Here's why. Call the $n$th card from the left card $n.$ Call a configuration
of cards a *winning* configuration if its cards 1 through 1960 are all
blue. We use this term because if you leave the cards in such a
configuration at the end of your turn then your opponent will have no legal
move and you'll win. Let $S(n)$ be the number of times card $n$ has been
selected so far.

We start by proving the following lemma.

**Lemma.** In a winning configuration, for each $n$ from 1 to 1960,
$S(n)$ is odd if and only if $n \equiv 1 \pmod{50}.$

*Proof.* We prove this by induction on $n.$

For the base case, observe that card $1$ only gets flipped when it's selected, since there are no cards to its left. Thus, it winds up blue if and only if it gets selected an odd number of times. So, the lemma holds for $n=1.$

Next, suppose $1 < N \leq 50,$ and the lemma is true for all $1 \leq n < N.$ Card $N$ gets flipped when and only when some card $n$ is selected where $1 \leq n \leq N.$ So, it's always been flipped $\sum_{n=1}^N S(n)$ times. In the winning configuration, this must be odd since it's blue in such configurations. By the inductive hypothesis, in a winning configuration, $S(1)$ is odd and $S(n)$ is even for all $1 < n < N.$ Since $\sum_{n=1}^N S(n)$ is odd, it must be that $S(N)$ is even. This proves the lemma for $n=N.$

Finally, suppose $50 < N \leq 1960,$ and the lemma is true for all $1 \leq n < N.$ Card $N$ gets flipped when and only when some card $n$ is selected where $N-50 < n \leq N.$ So, it's always been flipped $\sum_{n=N-49}^N S(n)$ times. In the winning configuration, this must be odd. By the inductive hypothesis, in a winning configuration, if $N \equiv 1 \pmod{50},$ then each $S(n)$ where $N-50 < n \leq N$ must be even since each such $n \not\equiv 1 \pmod{50}.$ This means that $S(N)$ must be odd. On the other hand, if $N \not\equiv 1 \pmod{50},$ then exactly one $S(n)$ where $N - 50 < n \leq N$ satisfies $n \equiv 1 \pmod{50},$ and so exactly one such $S(n)$ is odd. This means that $S(N)$ must be even. This proves the lemma for $n=N.$

The only cards that can be selected are cards 1 through 1960, since any other card doesn't have 49 cards to its right. So, the total number of selections that have happened is always $\sum_{n=1}^{1960} S(n).$ In a winning configuration, $S(n)$ is odd only for $n=1, 51, 101, 151, \ldots, 1951.$ There are an even number of such $n$ (40 such $n$, to be precise), so the total $\sum_{n=1}^{1960} S(n)$ must be even. In other words, at the time of a winning configuration, an even number of selections have happened. This means that, if you go first, it's impossible to win: at the end of your turn, the number of selections will always be odd.

We've thus shown that the first player can never win. To prove that the
second player *can* win, we now show that the second player can force
the game to end in a finite number of turns.

A simple way to force the game to end in finite turns is to always select the left-most red card on your turn. This will cause that card to turn blue and remain that way until the end of the game. Since each of your turns reduces the number of red cards in the range 1 through 1960 by at least one, the game will end after at most 1960 of your turns.

Interestingly, *any* strategy you choose will cause the game to end in
a finite number of turns, though the proof of this is a little less
straightforward. One can show, by induction, that the number of times card
$n$ can ever be selected is bounded above by $2^{n-1}.$ So, there's no way
for the game to last more than $2^{1960}$ turns.