Two friends are playing a game where they break of pieces from a rectangular 10 x 15 candy bar. The game continues until either player gets a 1 x 1 piece. In the first move player A breaks the bar along a line. The second move is that player B chooses one of the two pieces and breaks it along a line (creating 3 total pieces). Third move is that player A can choose any of the three pieces (not just the latest two), and breaks it along a line. The game continues until either player breaks a piece leaving a 1 x 1 piece.

The question is if either of the players have a winning strategy if i) the loser is the player that creates a 1 x 1 piece ii) the winner is the player that creates a 1 x 1 piece

My reasoning is that after move $n$ there will be $n + 1$ pieces. Assuming optimal play there will be only 1 x 2 pieces left when either player is forced into losing in (i). That's exactly 75 pieces, so that's after move 74 which player B makes. That means that player A loses?

I don't really have a good idea of coming up with a strategy for (ii) though, any help of clue would be very much helpful!

  • $\begingroup$ I don't see how "assuming optimal play" would lead to there never being any 1×3 pieces. $\endgroup$ – hmakholm left over Monica Aug 12 '19 at 10:37
  • 1
    $\begingroup$ In (i) note that both 1x2 and 1x3 pieces are "dead," so the strategies will be driven by creating the right number of 1x3 pieces. For instance, if we started with a 1x6 piece and I went first, I would split it in half and make two 1x3s in order to win. All other moves would make me lose. $\endgroup$ – Brian Moehring Aug 12 '19 at 10:39
  • 1
    $\begingroup$ For (ii) the Sprague-Grundy theorem still applies if we declare that any move that creates a $1\times n$ piece is forbidden (it would be an immediately losing move anyway). So for a complete analysis there would be less that $9\times 14$ positions (i.e. piece sizes) to consider, and then combine them as nimbers. $\endgroup$ – hmakholm left over Monica Aug 12 '19 at 10:50

For both variants, $A$ has the winning strategy:

$A$'s first move will always be to break the bar in half, into two $5 \times 15$ pieces. Then $A$ will mirror $B$'s moves, so that at the end of $A$'s turn, there will always be an even number of pieces of size $m \times n,$ for every applicable $m,n,$ until $B$ makes a losing move.

For variant $(i),$ we define a losing move to be when $B$ makes a $1 \times 1$ piece. Obviously, at this point, $B$ will have lost with no more input from $A$.

For variant $(ii),$ we define a losing move to be when $B$ makes a $n \times 1$ (or $1\times n$) piece. It's easy to argue that the first time this occurs will happen on $B$'s turn and also that $n > 1$. Therefore, $A$ can break off the end and be the first to create a $1 \times 1$ piece, winning the game.

  • $\begingroup$ Cleaver! Just thought of this too, i.e. playing symetrically (mirroring) until player B is forced to make a "losing" move! Thanks! $\endgroup$ – user690277 Aug 12 '19 at 10:54

Your Answer

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