previous page: 123 competition/games/jeopardy.p
page up: Puzzles FAQ
next page: 125 competition/games/online/unlimited.adventures.p

124 competition/games/nim.p


This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

124 competition/games/nim.p

Place 10 piles of 10 $1 bills in a row. A valid move is to reduce
the last i>0 piles by the same amount j>0 for some i and j; a pile
reduced to nothing is considered to have been removed. The loser
is the player who picks up the last dollar, and they must forfeit
half of what they picked up to the winner.

1) Who is the winner in Waldo Nim, the first or the second player?

2) How much more money than the loser can the winner obtain with best
play on both parties?


For the particular game described we only need to consider positions for
which the following condition holds for each pile:

(number of bills in pile k) + k >= (number of piles) + 1

A GOOD position is defined as one in which this condition holds,
with equality applying only to one pile P, and all piles following P
having the same number of bills as P.
( So the initial position is GOOD, the special pile being the first. )
I now claim that if I leave you a GOOD position, and you make any move,
I can move back to a GOOD position.

Suppose there are n piles and the special pile is numbered (n-p+1)
(so that the last p piles each contain p bills).
(1) You take p bills from p or more piles;
(a) If p = n, you have just taken the last bill and lost.
(b) Otherwise I reduce pile (n-p) (which is now the last) to 1 bill.
(2) You take p bills from r(<p) piles;
I take r bills from (p-r) piles.
(3) You take q(<p) bills from p or more piles;
I take (p-q) bills from q piles.
(4) You take q(<p) bills from r(<p) piles;
(a) q+r>p; I take (p-q) bills from (q+r-p) piles
(b) q+r<=p; I take (p-q) bills from (q+r) piles

Verifying that each of the resulting positions is GOOD is tedious
but straightforward. It is left as an exercise for the reader.

-- RobH


How can I play Scrabble online on the Internet?


Announcing ScrabbleMOO, a server running at, port 7777
(nextsrv.cas.muohio.edu 7777). The server software is version 1.7.0
of the LambdaMOO server code.

To reach it, you can use "telnet 7777", and sign on. You
will have a unique name and password on the server, and directions are
provided in the opening screen on how to accomplish signing on. The
first time, you will need to type "create YourName YourPassword", and
each time thereafter, "connect YourName YourPassword".

There are currently 5 Scrabble boards set up, with global individual
high score and game-cumulative high score lists. Games can be saved,
and restored at a later time. There are complete command instructions
at each board (via the command "instructions"); usage is simple and
intuitive. There are commands to undo turns, exchange tiles, and pass,
and there are a variety of options available to change the way the
board and rack are displayed.

We do not yet have a dictionary for challenges installed on-line, and
that is coming very soon. I am seriously contemplating using the
OSPD.shar wordlist that Ross Beresford listed in a recent Usenet
article. It seems to have the full wordlist from the 1st edition
of the OSPD, plus longer words from some other source. I have
personal wordlists updating the OSPD to the 2nd edition, for words
up to 4 letters long, and will have the longer words in the near

Usage of a certain dictionary for challenges is not enforced, and
really can't be. Many of the regular players there have their
personal copy of the OSPD. It's all informal, and for fun. Players
agree what dictionary to use on a game-by-game basis, though the
OSPD is encouraged. There are even commands to enable kibitzing,
if watching rather than playing is what you're into.

Come by and try it out. We have all skill levels of players, and
we welcome more!


Continue to:

previous page: 123 competition/games/jeopardy.p
page up: Puzzles FAQ
next page: 125 competition/games/online/unlimited.adventures.p