# Variation to Chomp game

I am re-posting this which I had originally posted to MathOverflow (not knowing it is intended only for Mathematics research and developing ideas):

Anna and Brian have a chocolate bar, which is scored into an 11 by 10 array of squares (11 columns x 10 rows). They alternate turns to eat 1 to 3 squares at a time. Anna plays first and in each move she can eat squares only from one column, while Brian can eat squares from different columns, but at most one from each column. The one who eats the last square is the winner. If both players play perfectly, is there a winning strategy for any of the two? If yes, describe it!

Suppose I am Brian; in order to win, I must leave Anna with 1+1+1 (in 3 different columns) or 1+1 squares (in 2 different columns). I can also leave her with 2+1+1. No matter what she "plays", playing perfectly, I can always win. I have tried simulating the game with fewer columns and rows but I don't see any clear pattern.

• What is the source/context of this problem? Is this an exercise in a programming context, in a combinatorial game theory class, cleverness to see some simple strategy for a math competition? Can you post your partial results and how you got to them? All of this information would help someone guess what sort of approach to expect/you're looking for, and what level to respond at. – Mark S. Jun 24 '17 at 23:11
• @Mark S.: I don't know the source of the problem; it was given to me by a friend (we both exchange riddles & puzzles very frequently) and we are both working on it. We are grown ups and not students. My partial results are listed above and I have also tried 3+1+1 where I see that A wins in this case. I can roughly see a strategy that when B plays, he must eat squares from a column that has multiple squares left, whereas A must eat single squares (so as to leave the multiple squares that B cannot eat all together). – Samuel Jun 25 '17 at 10:52

Brian always wins $n+1$ by $n$ with Anna going first.
Anna must eventually reduce the game to one column if she is to ultimately win. The best way for her to do this is to focus on one column on a time. (Alternatives are given some consideration later.) It takes her $\text{ceil}(n/3)$ moves to eliminate a column of size $n$. That's the same number of moves it takes Brian to remove one piece from each remaining column. (Brian can avoid dealing with the column that Anna is eliminating because Anna has to go first.) Thus, if Anna follows this strategy, Brian can ensure that the game is reduced to $n$ by $n-1$. If this process repeats, it will eventually by $2$ by $1$ which Brian wins.
What if Anna doesn't focus on one column? Regardless, Anna must still eliminate every column but one before the last column gets too small. If Anna switches to a different column, then Brian can ignore both columns that Anna has made progress on, at least until the max column size catches up to one or the other. This is helpful to Brian if anyone, not Anna. Brian can't necessarily rely on hitting $n$ by $n-1$ in this case, but if Anna is working on two columns, Brian can ensure the game reduces to $n-1$ by $n-2$, before both columns are reduced to 0, or similar for working on more columns. If Anna is working on all the columns, then it's even worse for her.