Consider 2009 cards, each having one gold side and one black side,
lying in parallel on a long table.  Initially all cards show their gold sides.
Two players, standing by the same long side of the table, play a game with
alternating moves.  Each move consists of choosing a block of 50 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?

---------------------------------

(a)
Should be easily true.
In each move, we turn gold to black, in a left-most changed position.
So if gold < black, then the game states decrease in the lexicographical order.
(or, we can view it as binary sequence gold='1', black='0', and the entire number decreases)

(b)
Winning strategy: Let's try a game with smaller constants: n cards, turning blocks of k

k = 1
no matter what the moves are: n is odd => player1 wins, n is even => player2 wins

k = 2, n = 3
G G G -> B B G (1 wins) or G B B
player1 can win, out of curiosity what happens in the second case?
  G B B -> B G B -> B B G (again, 1 wins)

k = 2, n = 4
G G G G: only move that does not lose immediatelly in the next move is (1)-> G B B G
G B B G (2)-> B G B G (1)-> B B G G (2)-> B B B B
player 2 wins
Hm... does he again wins whatever he does?
G G G G (1)-> G G B B (2)-> G B G B (1)-> B G G B (2)-> B G B G (1)-> B B G G (2)-> B B B B
                      (2)-> B G G B (we have been at this position before)
           -> B B G G (2)-> B B B B               (2)-> B B B B
Yes, it appears so (I think I have checked all the options)

Conjecture: It is actually not a "game", the winner does not depend on the player's actions.

The first card must be turned at some point, exactly once.
Therefore, the second card must be turned even-number-times because it must be black in the end.
-> So we can ignore the second card for the purpose of the conjecture
  * (1) The turns of the second card does not influence the parity of the number of moves (the winner)
  * (2) The turns of the second card does not influence the final state

This should be possible to generalize for the general setup (arbitrary k, n):
* Consider a sequence of moves leading to a state in which a legal move cannot be done.
* We rearrange the moves so that
  * The end state will be the same
  * The parity of moves will be the same
  * We ignore for a while the "move-legality" condition
    * We allow moves turning a block of 'k' cards, the leftmost of which is black
* First, we sort the moves by the positions of the blocks, first the left-most moves.
  This does not change the outcome, the moves apparently commute.
* We remove all "doubles", pairs of identical moves next to each other
* Now we have a sequence of moves such that
  * The positions of the moves are strictly increasing.
  * After applying the moves, a legal move cannot be done.
  * The number of the moves in the new sequence is the same as the number of moves in the original one.
* Let's prove that the current sequence of moves is unique
  * The first move must turn the first card to black.
  * The next move cannot turn any of the first 'k' cards to gold, because it would remain gold,
    providing a legal move in the end.
    However, the second move must turn the (k+1)-th card (which is gold) to black.
  * In general, i-th move must not turn any of the black cards (i-1)k+1, ..., ik to gold
    but it must turn the card ik+1 to black.
  * This uniquely defines the moves until (i+1)k > n, which terminates the process.
QED conjecture

To determine the winning player, we just calculate the number of moves in the example
n=2009, k=50
number of moves = n // k = 2009 // 50 = 2000 / 50 = 400
The number of moves is even, therefore the second player wins, therefore the first player does not have
a winning strategy.

Problem solved!