Problem of the Week 871

Passing Pebbles

Alice has a bucket of 900 pebbles. She wishes to pass them all to Bob. Each stone must sit on a infinite checkerboard before Bob can take it. Here are the rules:

1. At most 36 pebbles can be on the board at any time.
2. There are two types of moves:
   • Row move: Alice chooses a row of the board. She places as many pebbles as desired (subject to rule 1) from her bucket to that row, in any positions (but only one pebble per position).
   • Column move: Bob chooses any column of the board. He takes as many pebbles as he likes from that column to his bucket.
3. The game is over when Bob has all the pebbles, and the score is the number of moves.

Alice and Bob are working together here, and their moves need not alternate.

Find a strategy that allows the transfer of all the stones using fewer than 300 moves? How low can you go?

Source: Larry Carter, Dept. of Computer Science, Univ. of California. San Diego

© Copyright 1998 Stan Wagon. Reproduced with permission.