Hosted by The Math Forum


Problem of the Week 871

Passing Pebbles

_____________________________________________
Fall 98 Archive || MacPOW Home || Math Forum POWs || Search MacPOW
_____________________________________________

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.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

The Math Forum

14 October 1998