5

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. enter image description here

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

Abhi
  • 237
  • 3
    Isn't this just https://en.wikipedia.org/wiki/Chomp ? – Fixee Jul 02 '15 at 04:18
  • In order to prove by contradiction that the first player always wins, you must assume that the second player can prevent the first player from winning, and then show that this leads to a contradiction. Showing that the second player can force a win is simply reaffirming the assumption that she can prevent the first player from winning, and is not a contradiction. – David K Jul 02 '15 at 10:33

2 Answers2

8

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.)

mjqxxxx
  • 41,358
  • (+1) Beat me to it. I have no idea what mental hiccup led me to post that first answer of mine. – Brian M. Scott Jul 02 '15 at 03:48
  • This argument is weird because the second player reacts to the first player's move. So it is not always necessary that the second player have a "winning move" to ensure a winning strategy (I can understand the first player to have a "winning move" for his winning strategy). A winning strategy can consist of many winning reaction moves but not always one to react to all. – corindo Jul 02 '15 at 04:01
  • 4
    We would not expect the second player to have a single "winning move." Rather, for each possible first move the first player might make, the second player wants to have a winning move--possibly a different winning move for each move the first player can make. Call it a "winning response" if you like. Now we name a particular first move by the first player. If the second player has no winning response to that move, the first player's move is a winning move for the first player. – David K Jul 02 '15 at 10:23
2

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

  1. 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$.
  2. 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.

Community
  • 1
corindo
  • 3,752