Indian Computing Olympiad

Games and strategies

Rectangle (IOI 2005)

Two people start with a slab of chocolates with M rows and N columns and play the following game (with M,N ≤ 10⁸). 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.

Solution

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.