3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark S. Jun 24 '17 at 23:11
  • $\begingroup$ @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). $\endgroup$ – Samuel Jun 25 '17 at 10:52
0
$\begingroup$

Brian always wins $n+1$ by $n$ with Anna going first.

I don't have a fully formal proof, but I think I can give a somewhat convincing argument. I have also done some computer analysis, so I'm pretty it is actually true that Brian wins.

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.

A sufficiently efficient strategy for Brian seems to be removing pieces from the largest column except in the case where all columns are equal multiplies of three in which case the turn should be ended if possible. I'm not sure if this is optimal in every position, but I don't know of anything better. The other exception is when all columns have only 1 piece left, in which case Brian can easily win in any non-trivial position.

The best strategy for Anna seems to be eating as many pieces as possible from the smallest column. The exception is when there is only 1 column left, in which case Anna can easily win in any non-trivial position.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.