Game Of Nim

This can be considered as a $\color{#20A900}{\text{Game Of Nim}}$ . In Game of Nim, if there are $n$ - stacks with $a_1, a_2, a_3 \ldots a_n$ rocks respectively. In each turn, a player can choose any stack and remove any number of rocks from it $(\gt 0)$ . If at any turn, a player has no moves left, then that player loses. $\color{grey}{\text{A visualisation of Game of Nim}}$

---

Now, in the game, if the players play optimally, then the condition for player who starts the game to win is $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_{n-1} \oplus a_n \neq 0$ $\text{Where } \oplus \text{ is }$ $\text{XOR operator}$

---

Here, we can consider it as two stacks with $m$ and $n$ number of chocolate squares. Now, as $m \neq n$ , so $m \oplus n \neq 0$

So, Player 1 , i.e. Sierra can $\color{#3D99F6}{\boxed{\text{Always Win}}}$

$\text{Proof by induction}$

$\text{It is not possible for } m=n \text{ Actually, it is stated that } m>n. \text{ from beginning, so Sierra can eat that many pieces}$ $\text{ in her first move, so that for Caleb's first move,}$ $m=n,$ $\text{ then this procedure follows.}$

$\Large{\text{So, no matter what, }\color{#D61F06}\text{there is a strategy for Sierra, since she is the first player.}}$

Sierra has a killer strategy to win

Since Sierra is moving first, she must try to make the bar symmetric like this -

Once she eats $\color{#EC7300}m-n$ squares from the leg with $\color{#EC7300}m$ squares, both legs will have $\color{#EC7300}n$ number of squares and the bar will be symmetric like this -

Then the winning strategy for Sierra becomes simple - She just has to copy Caleb. Copying Caleb will make the bar retain its symmetry like this -

Caleb eats $\color{#3D99F6}Y$ squares, and Sierra copies him. This will continue until Caleb eats a square next to the $\color{#D61F06}X$ square. When Caleb eats a square that is next to the $\color{#D61F06}X$ square, Sierra can copy him like this -

$\underline {\color{#D61F06}Leaving \ the \ X \ square \ for \ Caleb.}$

( This is all true, assuming they are both at optimal play, as it was mentioned in the question )

$$

Chomp Game Explained - I learnt about Chomp today from this place, so you can too!

Sierra's Strategy

On her first turn, Sierra should eat $m - n$ squares on the $m$ leg so that it becomes the same length as the $n$ leg:

Then for all her turns after that, if Caleb eats $x_k$ squares of one leg on his $k^{\text{th}}$ turn, then Sierra should eat $x_k$ squares of the other leg on her $(k + 1)^{\text{th}}$ turn:

Example

Here is one example of a game where Sierra uses her winning strategy:

Analysis

By eating $m - n$ squares on her first turn, Sierra makes both chocolate legs have the same length of $n$ . Then by matching Caleb's squares for all her turns after that, Sierra can keep both chocolate legs the same length of

$\displaystyle n - \sum_{k=1}^{t} x_k$

(after Caleb has had a total of $t$ turns). By keeping both chocolate legs the same length, Sierra is guaranteed that there will always be $x_k$ matching squares for her to eat that will not include the lower left square.

In other words, no matter what Caleb does, Sierra can counter, so eventually Caleb will be left with the last square, making Sierra the winner!

We've a column of n squares and a row of m squares and m>n

Step - 1

Sierra chops off $m-n$ squares from the row so we have same numbers of square in row and column.

Step - 2 & 3

Now, let x be the no. of squares Caleb takes away,so Sierra will also chop off same amount

Step - 4 & 5

Repeating steps 2 & 3 till the last square remaining, Sierra (Player-1) will always be the winner.

By this Startegy, Players 1 will always win.

However, if we start with m=n, then Caleb is advantageous cause he becomes the Pseudo-Player-1

This is equivalent to a game of Nim . Think of the straight column(except for the bottom-left corner) as stack 1, and the horizontal one(also except for the bottom-left) as stack 2. Now winning is equal to making the last move.
First, we note that $m\oplus n\neq 0$ where $\oplus$ stands for XOR or there is no optimal strategy.
Since Sierra moves first, she can reduce the number of elements in stack 1 so it is congruent to stack 2 by taking $(m-n)$ elements.
Then all we have to prove is that as long as Caleb can make a move, so can Sierra. This is simple—if Caleb takes elements ${a,b...n}$ from stack 1, Sierra can do the same to stack 2 since they are congruent, which keeps the congruency.
This works $\text{vice versa}$ and we see that Sierra has an optimal strategy to win as in Nim.
Done, @Siddharth Chakravarty

m>n , first movement is eat m-n squares , so the result is m=n , so on until result is m=n=1 and win.

This problem can be simplified as a Nim game :

Sierra and Celeb has two bags with $m$ and $n$ chocolate pieces respectively ( $m>n)$ . Each of them take turns picking a bag and taking some chocolate pieces from that bag. The person who takes the last piece will win. It's Sierra's turn. Assuming both of them play optimally, is there any strategy for one to win?

In the case of two bags, there's a really easy strategy for Sierra to win:

• First, take $m-n$ chocolate pieces from the bigger bag, leaving the two bags with equal pieces.
• If Celeb takes $a$ pieces from a bag, simply take $a$ pieces from the other bag.

So $\boxed{\textcolor{forestgreen}{\text{Sierra}}}$ have a strategy to win the game.

The picture below shows an example of the game.

$\text{The strategy}$

---

$\text{Sierra} = \text{ALICE}$ and $\text{Caleb} = \text{BOB}$ .

$\text{ALICE}$ makes the first move, as shown in the figure:

After $\text{ALICE}$ s move,

$\text{BOB}$ has now $6$ possible moves (from the way I see fit):

$\text{Case 1}$

$\text{Case 2}$

$\text{Case 3}$

Take the entire $m$ column, $OR$ to take $n$ row (except the $\boxed{\text{x}}$ ) (case 1),

Take almost all the $m$ column $OR$ $n$ row, leaving one box free (except the $\boxed{\text{x}}$ ) (case 2),

Take almost all the $m$ column $OR$ $n$ row, leaving two or more boxes free (except the $\boxed{\text{x}}$ ) (case 3),

If none of these options work, we have a guarantee that $\text{ALICE}$ wins if she plays optimally.

Try these on paper!

$\text{Case 1}$

• If $\text{BOB}$ takes all the $n$ row, $\text{ALICE}$ counteracts of taking all $m$ column. NOT FAVORABLE MOVE!
• If $\text{BOB}$ takes all the $m$ column, $\text{ALICE}$ counteracts of taking all $n$ row. NOT FAVORABLE MOVE!

$\text{Case 2}$

• If $\text{BOB}$ takes almost all the $m$ column leaving one box free, $\text{ALICE}$ counteracts by doing the same to the $n$ row (taking all the boxes leaving one free). $\text{BOB}$ is forced to take one of either free boxes . $\text{ALICE}$ takes the other free box. NOT FAVORABLE MOVE!
• If $\text{BOB}$ takes almost all the $n$ row leaving one box free, $\text{ALICE}$ counteracts by doing the same to the $m$ column (taking all the boxes leaving one free). $\text{BOB}$ is forced to take one of either free boxes. $\text{ALICE}$ takes the other free box. NOT FAVORABLE MOVE!

$\text{Case 3}$

• If $\text{BOB}$ takes almost all the $m$ column leaving two or more boxes free, $\text{ALICE}$ counteracts by taking almost all the $m$ column leaving one box free. By the figure:

$1$ and $4$ clearly lead to failure. $3$ In this case $\text{ALICE}$ will take almost all that's left of the $n$ row leaving one box free. $\text{BOB}$ is forced to take one of either free boxes . $\text{ALICE}$ takes the other free box. $2$ In this case $\text{ALICE}$ will take almost all on the $m$ row leaving one box free. $\text{BOB}$ is forced to take one of either free boxes . $\text{ALICE}$ takes the other free box.

Since all these cases of Case 3 lead to failure for poor $\text{BOB}$ NOT FAVORABLE MOVE!

Result:

Take the entire $m$ column, $OR$ to take $n$ row (except the $\boxed{\text{x}}$ ) (case 1), NOT FAVORABLE MOVE!

Take almost all the $m$ column $OR$ $n$ row, leaving one box free (except the $\boxed{\text{x}}$ ) (case 2), NOT FAVORABLE MOVE!

Take almost all the $m$ column $OR$ $n$ row, leaving two or more boxes free (except the $\boxed{\text{x}}$ ) (case 3), NOT FAVORABLE MOVE!

$\boxed{\text{If none of these options work, we have a guarantee that ALICE wins if she plays optimally.}}$

This took a LOT to make! Please upvote!

The game is a finite, impartial, combinatorial game. For such games every game state is either "winnable" (the first player has some winning strategy) or "unwinnable" (the second player has some winning strategy). In this setting, we can prove by induction that each "symmetric" state is "unwinnable", while all other states are "winnable".

• Theorem: all "symmetric" states (having the bottom left square with $m$ squares to the right and $m$ squares up) are unwinnable.

When $m=1$ , there are three possible first moves for the first player (Sierra) -- eat the top square, the right most square, or the whole thing.

1. If Sierra chooses to eat the top square, the second player (Caleb) can eat the right most square and win.
2. If Sierra chooses to eat the right most square, Caleb can eat the top square and win.
3. If Sierra chooses to eat the whole thing, Caleb wins straight away.

Therefore, this game state is "unwinnable", and the statement holds true when $m=1$ .

Suppose the statement holds true for any $m<k$ , now let's examine the game state of having the bottom left square with $k$ squares to the right and $k$ squares up.

there are $2k+1$ possible moves for Sierra -- eat the top $x$ squares, the right most $x$ squares, or the whole thing. ( $x=1,2,\ldots, k$ )

1. If Sierra chooses to eat the top $x$ squares, the Caleb can eat the right most $x$ squares and the state becomes "unwinnable", as now $m=k-x<k$ .
2. If Sierra chooses to eat the right most $x$ squares, Caleb can eat the top $x$ squares and the state becomes "unwinnable", as now $m=k-x<k$ .
3. If Sierra chooses to eat the whole thing, Caleb wins straight away.

Therefore, this game state is "unwinnable", and the statement holds true again. By induction, the theorem is proved.

Now that we know that all "symmetric" game states are "unwinnable", we can easily show that all other game states are "winnable". This is because the Sierra can simply eat the difference off of the longer side and make the game state "symmetric" in one move.

The winning strategy for Sierra is indeed to eat the difference off of the longer side and make the game state "symmetric" every single move. Note that this strategy is unique, because if Sierra strays away from this in any move, the game state will no longer be "symmetric", therefore "unwinnable" for Caleb. Caleb can now use the strategy instead and be guaranteed to win.

How to find a suitable stragegy for Sierra:

Let's start by considering a simple case:

Player 1 must remove one of the green squares. Player 2 can then remove the other block, securing a win.

We can generalize this case stating that if Sierra can make an equal number of blocks above and to the right (i.e. - m=n), she can win.

To win, Sierra has to maintain a condition where there are an equal number of blocks to the right and upwards until they reach the base case, with three blocks remaining, and Caleb to play.

Hence:

By taking $\boxed{(m-n)}$ blocks out of the horizontal row, Sierra can always win.