Cute little problem! We number the cards left to right $1,2,\dots$, and say that we choose card $n$ if we choose the block of $50$ cards from $n$ to $n+49$. a) We show that the game necessarily ends for any positive number $N$ of cards, regardless of how may are initially with their golden side up:

b) We show now that the first player ALWAYS looses, independently on how each player ends, when the game has $2009$ cards:

daniel73 wrote: We show now that the first player ALWAYS looses, independently on how each player ends, when the game has $2009$ cards: This doesn't follow from your inductive proof. Suppose a game using $N-1$ cards can be finished in $m$ moves. 1) The $N$ card sequence where the first card is black and the other $N-1$ cards are the same as the previous sequence can be finished in $m$ moves. 2) The $N$ card sequence where the first card is gold, the cards $2,3,...,50$ are opposite to the first $49$ terms in the $N-1$ sequence, and the rest are the same, can be ended in $m+1$ moves. (i.e. first move flip card $1$, and you are left with the previous sequence.) And one of $m,m+1$ must be odd Also consider $2009$ cards with the first 50 cards gold and the ramaining $1959$ black. Play $1$ can win in one move.

Sorry, ocha, I was not clear enough. Parts (a) and (b) are solved independently and separately; induction is used in part (a) only to show that the game ends, independently on which sides the cards are showing. Part (b) is solved only when the $2009$ cards are initially golden-side up, hence induction is not an issue in this part of the solution... Maybe this will answer your question...

(a) Denote by 1 the golden faced coin and by 0 the black faced one. Than there is a bijection between each position of coins and a 2009-digit number. It's quite easy to note that this number DECREASES after each move, but as it must be a positive integer, the process will necessarily end.

lasha wrote: (a) Denote by 1 the golden faced coin and by 0 the black faced one. Than there is a bijection between each position of coins and a 2009-digit number. It's quite easy to note that this number DECREASES after each move, but as it must be a positive integer, the process will necessarily end. Good one Lasha!

Hmm... a trivial point, but it seems that we have to consider the cards $n\equiv10\equiv2009-50+1\pmod{50}$, since $1961,\ldots,2009$ are always unplayable (even if they're gold).

just by induction the first problem is trivial.as for the second one,let us consider the cards $10,60,...,1960$ and then by a little analysis on parity we can get it!

For part a) just induct on N,where denotes the number of cards.Now,if N<50 or N=50 it is obvios(for every combination of blacks and golds).Now,suppose this is true for N,we will prove that it is true for N+1.If we pick 1,2...50,we will never again pick 1,so induction on N-1.If we never pick 1,again induct. b)Just consider cards 10,60,...1960 and by parity we have that player can never end the game,but cause the game finishes,B will always win,so we are finished.

This problem was nice. (a) Label the gold cards with $1$ and the black cards with $0$.Then consider the number so formed with $0$'s and $1$'s.Each move decreases this number,so the game has to end. (b)Consider the number of gold cards $f$ in the cards numbered $10,60,110,\cdots,1960$ (Now the cards are numbered serially from left to right).Initially $f=40$.It is easy two note that after every move $f$ either increases or decreases by $1$.So after odd number of moves $f$ is always odd and consequently $\ge 1$.The second player always takes a turn after an odd number of moves,so he always finds a gold card among the set,and consequently,always has a move.Since the game has to end necessarily,the second player has a winning strategy. EDIT: I was really silly here.Thanks for pointing out my mistake.

Wrong; if the only gold card is card $2000$, Player 2 has no move. You should have observed the cards $10, 60, 110, \ldots, 1960$ instead.

So here is my solution for part (a) with a bit of intuition. I have tried (b) before, but it seems that I have the same solution as daniel73, so I'd better not include it . Part (a). The intuition. All the information we have is about the starting card of the block. How can we make use of this? Surely by the base $k$ representation of a natural number! Also, we have only two possible sides (gold/black) so we denote them by $1,0$ respectively. The solution. As stated above, we denote a gold card by $1$ and a black card by $0.$ Consider these cards to be forming the binary representation of a positive integer $N.$ Then the value of $N$ strictly decreases after each move. As $N$ must always remain a positive integer, yes, the game must end.

Label the cards from right to left $1,2,\dots,2009$. Then if we always write the labels of the gold cards in decreasing order, the resulting sequence of sequences is lexicographically decreasing, so the game is finite (in fact, it ends in $\le 2^{2009}$ moves). Also, each move changes $N:=$[number of gold cards with $50|\text{label}$] by $1$, and so $N$ is odd after each move of the first player, implying that the second player can always make a move (as then $N>0$). As the game is finite, some player will eventually not be able to make a move; since this is not the second player, the first player always loses.

And I'd like to point this out once more, @2 above:

.........

(a) The game necessarily ends. We can imagine a binary number of $2009$ digits corresponding to the cards on the desk(left most digit corerspond with the left most card, and so on), with a $1$ if the card is red and $0$ if the card is black. Check that each move makes this number smaller. (b) There does not exist a winning strategy for player one. Let $T_1, T_2, \cdots ,T_i, \cdots T_{1960}$ be the number of times that the block of $50$ consecutive cards starting at $i$ is turned over. When either player wins, it means that the first $1960$ cards have to be black. So we start with $T_1$, this must be odd for the first card to be black, then $T_2$ must be even, $\cdots$, $T_{50}$ must be even; then $T_{51}$ must be odd, $\cdots$. Continuing this process we see that $T_1, T_{51}, T_{101}, \cdots T_{1951}$ must all be odd while the others are even. Let $S = T_1+T_2 +\cdots +T_{1960}$. When any of them wins, the number of $T_i$'s that must be odd is even, so $S$ must be even. Whenever a player make a move, this sum's parity is toggled. Since the sum starts with beign even ($0$), the player who starts second always wins.

Solution from Twitch Solves ISL: Interpret gold as $1$ and black as $0$. The answer to (a) is obviously yes, since viewing the number as a binary string of length $2009$ we find that it decreases at each step. As for (b), we claim that Claim: The second player must win regardless of what moves occur. Proof. Consider the $50$th, $100$th, $150$th card, and so on, up to the $2000$th card from the right (which is the $10$th card from the left). Denote the set of these $40$ cards by $C$. The number of $1$'s in $C$ must change by exactly $1$ every turn, and it is initially $40$. The game could only end when all cards in $C$ are zero. So this can only occur on the first player's turn. $\blacksquare$

The game must end. Represent it in binary; let the gold cards be $1$ and the black ones be $0.$ Note each move decreases the value of the binary string, so the game must terminate. We claim that player 2 has the winning strategy. Let the card in the $ith$ position from left to right be $a_i.$ Note that every move touches exactly one card of the form $a_{50n}.$ We claim that if any of these cards are gold, then the game is not over. Since at least one of the cards must be gold when it is player 2's turn, he cannot lose. The proof is obvious if any of these cards are not $a_{2000},$ because then $a_{50n}$ can be played, so we just need to prove this when $a_{2000}$ is the only gold multiple of $50.$ We prove this by contradiction. The number of gold cards never changes parity, it is always odd. Also if $a_{1}$ to $a_{1959}$ are all covered this implies that $a_{1}$ to $a_{1950}$ are all covered, implying that $a_{1951}$ to $a_{2000}$ are all covered, contradiction.

Denote the sequence in binary, with $1$ representing a gold card and $0$ representing a black card. Now any move decreases this number, so it eventually must get to a point where no moves are available. b) Consider the cards at position $50k+10$ for $0\leq k \leq 39$. The game stops when the first $1960$ cards are black. Each move changes one of these cards from gold to black or black to gold. We need them to change an even number of times, so there were an even number of moves. This means player 2 had to win.

a) Consider the cards as a binary number, with $1$ gold and $0$ black. A move must decrease the value of this number, but it cannot keep decreasing forever, hence the game must end. b) No; we show that the first player will always lose the game. Consider the cards $10, 60, \cdots, 1960$. On each turn, exactly one card has its status changed, but there are an even number of cards, hence there have to be an even number of turns before all these cards are changed from gold to black. This means that player 2 must win.

pronouns are used WLOG. The answer to a and b is that it must always end and player 2 will always win. For a), let each of the cards represent their respective place in a digit of the binary number with 2009 digits, with 1 as gold and 0 as black; it's obvious that each time the number strictly decreases. For b), we look at the 10th, 60th, ..., 1960th cards; exactly one of the 40 must be flipped each turn; in particular, since there are 40 cards, the 2nd player gets the 40th ``removal" of the card. Then, if the 10th card is left, the second player takes the first card which leaves no gold cards, so he wins. On the other hand, if some other card is left, he takes that one and finishes, since by size reasons we know the union of them have all been covered. $\blacksquare$

Well let me say the more essential thing. The winner is fixed even if the "block" is not a cluster of consecutive cards, as long as it has a fixed "pattern", for example, the cards are numbered from right to left 0, 1, 2, ..., each player can choose an integer N and flip the cards numbered N, N+2, N+5 if the card N+5 has gold side up. This is just polynomial division with coefficients in Z[2]. In this case the divisor is x^5+x^2+1. After each move, the remainder polynomial remains unchanged, but the amount of coefficients that are 1 in quotient polynomial changes by 1. So the parity of the amount of 1's in the quotient polynomial determines the winner.

($a$) Yes, the game does end eventually. We can encode the cards in binary by interpreting gold cards as $1$ and black as $0$(reading left to right). Notice that each legal move decreases the value of the binary interpretation of the current configuration, so we must get to a binary value of $0$ which corresponds to all $2009$ cards being black. ($b$). Consider cards in positions $10$, $60$, $110$, $\dots$, $1960$. Any valid move swaps the color of exactly one of these cards. Since each move changes the number of gold cards in this collection of $40$ cards by $1$, and the second player must have an even number of cards on the turn they lose, this is impossible since by parity the number of gold cards at the beginning of the second player's turn is odd. (hopefully this is correct now)

(a) Yes. Consider the binary number $a_1 a_2 \dots a_{2009}$ in which $a_i$ is $1$ if the $i$th card from left to right is gold, and $0$ otherwise. It is easy to observe that every move causes this binary number to decrease; as a result, at most $2^{2009} - 1$ valid moves are possible. (b) No; in fact, the starting player loses even if the second player plays randomly. Consider the cards $a_{10}, a_{60}, \dots, a_{1960}$. We note that every move flips exactly one of these cards, and there is always a valid move if at least one of these cards are facing up, or that there is no longer a valid move only when (though not always when) none of these cards are still facing up. Combined with the fact that the game always reaches an end, since there are $40$ such cards, the game only ends when the second player finishes their move. @above consider a position where there are only 49 cards; the first player obviously loses, but the 24th/34th card still exists.

scannose wrote: @above consider a position where there are only 49 cards; the first player obviously loses, but the 24th/34th card still exists. thanks, i think i fixed it and figured out my error

For the first mark gold as 1 and black cards as 0 then you would see that the value of binary decreases so we can comment that at some point the game would obviously end leading to all cards as black And for second part consider the cards 10,60,110.....1960 and when the moves reach 1960th card then the game would stop and for even turns it would lead to the winning condition for the second player Hence irrespective of the winning strategy the second player is always going to win

Wow, binary is so clever Number the cards $1, 2, \dots, n$ from left to right. (a) Let there be $n \ge 50$ cards, we will prove a stronger statement: That any row of $n$ cards, gold or black face showing, the game must terminate. We induct on $n$, clearly the $n = 50$ case is resolved as the first card must be black at some point. Now assume the claim is true for $n = k$, we will prove for $n = k + 1$. Clearly if the first card is black, the problem reduces to the $n = k$ case. Assume it is gold instead. For the sake of contradiction, assume it is possible that the game continues forever. Then we never change the block of $50$ consecutive cards starting with card $1$ as then it reduces to the $n = k$ problem. But this implies the game continues forever with the cards $2, 3, \dots, k + 1$, which is a contradiction of the $n = k$ problem as well. Hence, the induction is complete and the claim holds. Now $n = 2009$ and all cards gold finishes. (b) Consider the original problem. We claim the second player always wins. Let $K$ denote the number of cards out of $10, 60, 110, \dots, 2010$ that are gold at any state. Note that if the game ends we have $K=0$. At the beginning of the game, we have $K = 40$. Now any move changes exactly one of the cards mentioned above, so $K$ toggles parity every move. Then clearly the second player wins no matter what moves they make, and we are done.

Falls easily by induction, but a better idea might be to consider the binary string of $1$ and $0$ ( resp. $1$ for gold $0$ for black ) and the decimal equivalent keeps on decreasing so the game ends of course. Another idea to induct on gold cards and when they turn black. Second part comes from considering blocks of $50$ cards starting from the right-most one, and considering the first card of each block as representing card and keeping the count of gold representing cards which changes parity everytime which follows a winning strategy for second player.

a) Yes, use the standard binary weighting trick, clearly we are always decreasing in value and done. b) No, the second player always wins. Consider the number of moves that have leftmost cards 50-99 (where cards are in decreasing order from left to right), then the number of moves that have leftmost cards 100-149, so and so forth. Clearly each of these numbers is just the exactly number of moves that affect cards 50, 100, and so on. Each of these must be odd (since we end on all black cards for 50, 100, etc), so summing this quantity for all multiples of 50 grants an even number, so there are an even number of moves total and thus the second player wins.

Considering numbering the cards from left to right as $2008, 2007, \dots 1, 0$. a) Letting card $n$ have value $2^n$ if it is gold and $0$ if it is not, we can see that the sum of the values of the cards is strictly decreasing after every move. Done. b) Consider all cards numbered $49 \pmod{50}$. Every move must turn exactly one of these over, and in order for there to be no moves remaining they all must become black. (If any are gold, simply move the fifty to the right starting with that one). But by parity reasons it is impossible for all of them to become black after the first persons turn. Done.

JustKeepRunning wrote: Just a quick note: I am pretty sure @daniel73’s sol is incorrect for part (a) because for his induction, he only showed that it doesn’t work in the configuration where they all start as golden numbers, while when he inducts upwards, he assumes it hold for all possible configurations of $n-1$ numbers, regardless of whether they are all gold or not. This issue can either be resolved using the strictly decreasing argument, or another way to fix it is to use the following: Call a card “used” if it serves as the first card in one of the moves. Suppose that the first card is (ever) used. Then this means that the first card can never be used again, so we can effectively ignore it and reduce the problem to the other $2008$ cards. Otherwise, if it is not used, the problem also reduces to the remaining $2008$ cards. Notice that we can make this choice at the $2,3,\cdots, 1969$ cards(numbers interpreted as cardinality here), and after that, we are left with only $50$ cards, which is obviously not possible. Notice that even if there are gold cards remaining in the first $1969$ cards, they cannot be used, because in that specific case we “chose” not to use them. Therefore, the game ends. Can someone make sure my argument acutally works because none of the other posts in the thread seem to use my approach? This proof is correct iff you remember to mention that you are not inducting on all the winning states but rather on all game states which would most likely turn into a task in itself so rather you could just use the induction technique to proof for bijection between winning states and loosing states

a) Let the $n$th card from the right have value $2^n$ if it is gold and $0$ otherwise. Note that the sum of the values of the cards will then be strictly decreasing, but this sum of always positive, so the game will eventually terminate. b) Now, consider the cards $50, 100, \cdots, 2000$ (from left to right). Clearly every move alters the state of exactly one of these cards. There are $40$ of these cards, so by parity no matter what the second player can always find a move. Therefore since the game terminates eventually the first player will lose. QED

(a) Interpret the cards as a binary number, where black translates into $0$ and gold translates into $1$. Since the number formed is strictly decreasing, we are done. (b) Assume FTSoC that the starting player has a winning strategy. Consider the cards at positions $50k+1$ for $k\in \{0,1,\dots,39\}$. Notice that the number of these cards that are gold starts at $40$, and it also changes by exactly $1$ every move (since exactly one of these cards is flipped every move). Therefore, after the starting player moves, there are an odd number of these cards (at least one), which the second player can flip. Since the game ends and the starting player cannot win, the second player wins.