Prove that
Prove that
be an odd prime number. How many 
of 
are there, the sum of whose elements is divisible by 
Y by Davi-8191, cookie112, itslumi, AwesomeYRY, HWenslawski, megarnie, michchess, Adventure10, Mango247, bowenying24, CheckeredPenguin10, GA34-261, and 1 other user
Consider 
cards, each having one gold side and one black side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of 
consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins.
(a) Does the game necessarily end?
(b) Does there exist a winning strategy for the starting player?
Proposed by Michael Albert, Richard Guy, New Zealand
cards, each having one gold side and one black side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of 
consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins.(a) Does the game necessarily end?
(b) Does there exist a winning strategy for the starting player?
Proposed by Michael Albert, Richard Guy, New Zealand
,
if we choose the block of 
.
of cards, regardless of how may are initially with their golden side up:
or 
and the first card is initially black side up, the game ends before it can begin because no move is possible. If 
cards, and consider a game with 
,
cards, and the game finishes. If the first one is golden side up and it is never chosen, then it is also equivalent to playing with 
must be black side up, hence since no card may be chosen to turn card 
black, or cards 
will be chosen an even number of times (zero in the case of the "equivalent" game). Now, card 
must be made to turn black, but not by a lower card, hence it must be chosen once (or an odd number of times), and so on. We conclude that, for the game to finish, cards 
must be chosen an odd number of times (adding up to an even number of choices since there is an even number of such cards), and all other cards must be chosen an even number of times. Hence the game always finishes after an even number of moves, ie the first player is always the one that runs out of possible moves, and the first player always looses, independently on how the game is played.
moves.
are opposite to the first 
terms in the 
moves. (i.e. first move flip card 
must be odd
black. Play 
,
are always unplayable (even if they're gold).
and then by a little analysis on parity we can get it!
.
in the cards numbered 
(Now the cards are numbered serially from left to right).Initially 
.
.
,
instead.
.
representation of a natural number! Also, we have only two possible sides (gold/black) so we denote them by 
respectively.
Consider these cards to be forming the binary representation of a positive integer 
Then the value of 
.
shows gold and hence a player who goes after can make a move. No winning strategy
.
moves). Also, each move changes 
[number of gold cards with 
] by 
)
,
.
,
)
)
,
,
,
,
instead of ![$c \in [10, 49]$](http://latex.artofproblemsolving.com/0/f/2/0f2d93ce3f28aa4af6fdba32ca5c22e31f61962f.png)
but that doesn't work because then you would not be able to pick one of 
if that's the only gold card left(depending on the arrangement of the cards).
in which 
is 
t
valid moves are possible.
.
from left to right.
cards, we will prove a stronger statement: That any row of 
case is resolved as the first card must be black at some point. Now assume the claim is true for 
,
.
,
and all cards gold finishes.
denote the number of cards out of 
that are gold at any state. Note that if the game ends we have 
.
.
.
if it is gold and 
.
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:
cards. Otherwise, if it is not used, the problem also reduces to the remaining 
cards(numbers interpreted as cardinality here), and after that, we are left with only 
cards, they cannot be used, because in that specific case we “chose” not to use them. Therefore, the game ends.
(from left to right). Clearly every move alters the state of exactly one of these cards. There are 
for 
.
,
,
changes by 
,
The game always end.
to the 
be the sum of the numbers of the cards showing its gold side after 
but it will necessarily decrease in at least 
,
is descending, therefore, since it can't be negative, sometime we'll not be able to operate anymore 
to be movement where the 
of positive integer whose elements are less than 
, let 
to be the operation of performing all movements 
,
and when 
,
.
be the set of all possible moves.
as 
,
be a game that ended. Note that if we delete all the movements that appeared an even number of times in 
and make all the moves that appeared an odd number to appear just one time, the winner will be preserved and we'll get into a new set of moves 
that will have the same ending position. Finally, note that necessarilly 
,
it'll need to appear more than one time in 
and, once the winner is preserved from 
,
of the times and the game will always end with the same cards showing their gold faces. 
This generalization is inspired by @jonh_malkovich 's generalization for the 
