Two people start with a slab of chocolates with M rows
and N columns and play the following game (with M,N ≤
10^{8}). The players take turns breaking the
piece of chocolate. Each person can cut the rectangle
into two pieces, using either a single vertical or single
horizontal line. After each cut, the piece with smaller
area is discarded and the game continues with the bigger
piece. Eventually, the slab will reduce to a 1×1
rectangle. The player who has to play with a 1×1
rectangle loses the game.

Develop a winning strategy.

Some positions are winning, some are losing.

Losing positions:

- In one dimension, 1×3 is losing because we have to leave 1×2 which will return to us as 1×1. Since 1×3 is losing, positions 1×4,..,1×6 are winning since we can leave the opponent with 1×3. The next losing position is 1×7, because we have to leave the opponent with 1×4,...,1×6 which are winning. Similarly, positions 1×7, 1×15, 1×31, ... are losing.
- A square slab is always a losing position. However we cut, the opponent can reduce it back to a square. Eventually, the square will reduce to 1×1 which is losing.
- A rectangle of size n×m, n+1 ≤ m ≤ 2n, is winning, since we can reduce it to a square of size n×n.

m ------------ | | n | | | | ------------

Generalizing the 1-D case, n×(2n+1) loses,
n×(4n+3) is losing etc. In general, n×m is
losing if m = 2^{k(n+1)} - 1.

What if the rectangle is n×(2n+1) and the opponent reduces n to n'? Then, you can always reduce 2n+1 to 2n'+1 and leave a similar losing situation of n'×(2n'+1).

A losing position is a "trap" — once a player enters a losing position, no matter how he moves, the opponent wins.

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky