proof by contradiction puzzle Consider the following game between two players:
• There is an initially rectangular grid of cookies.
• The cookie in the upper left corner is poisoned.
• The players take turns. On a player’s turn, he or she must eat some cookie,
along with every cookie to the right and/or below it. (See the diagram for a
sample legal move.)
• The losing player is the one who is forced to eat the poisoned cookie.
2
Prove that the player who goes first can always win.

Here is my proof
By the way of contradiction assume the player who goes first does not always win.  Lets say the first player eats the lower right cookie in the first try(i.e 4,5).  Then in the next turn second player takes turn and ets the cookie at place (3,4). In third round, first player eats the cookie at place (2,3).  Then second player eats cookie at place (1,2).  Then the first player takes turns and lands on (1,1).  SO he loses.  So this is contradiction because the second player can force a win.  Thus statement is always true.
Can someone please help me on this.  Thanks in advance
 A: Assume that the second player (B) has a winning strategy.  Then she must have a winning move, $M$, in the event that the first player (A) eats just the lower-right cookie on his first move.  The result of B's supposed winning move in that case is that a rectangle of cookies has been eaten.  But A could've eaten that same rectangle of cookies on his first move, leaving B in the same (losing!) position that A is now in.  This contradicts the assumption that B has a winning strategy and $M$ was a winning move.  (This is called a "strategy-stealing" argument.  It shows that A has a winning strategy, but gives no hint as to what it might be.)
A: First this is a finite two-player game with perfect information and with no draws. So either the first player or the second player must have winning strategy.
Suppose on the contrary that the second player has winning strategy. The strategy must be like this :

*

*if first player takes $(a_1,b_1)$ then I take $(x_1,y_1)$,


*if first player takes $(a_2,b_2)$ then I take $(x_2,y_2)$,
...


*if first player takes $(a_N,b_N)$ then I take $(x_N,y_N)$.


*if first player takes$(1,1)$ then I win.
Let $f$ be the function that describes this strategy:
$$ f(a_1,b_1) = (x_1,y_1), \, \, f(a_2,b_2) = (x_2,y_2) , \,\, \cdots $$
Notice that

*

*By the rules of the game, $a_1 \le x_1 , b_1 \le y_1$ and $a_1 + b_1  \le x_1 +y_1 - 1$.

*There is no $(a,b)$ such that $f(a,b) = (1,1)$. Because in this strategy the second player always wins.

So consider the following sequence:
$$ (n,m), f(n,m), f^{(2)}(n,m) , \cdots$$
This sequence is finite since if $(a,b) = f^{(k)}(n,m)$ then $a+b \le n+m -k$. And it must end at $(1,1)$ because if $(a,b) = f^{(n+m-2)}(n,m) $ then $a+b\le 2$. However $(1,1)$ cannot be in the image of $f$ since this is a winning strategy. Thus we have a contradiction.
