Newsgroups: rec.puzzles
From: haoyuep@aol.com (Dan Hoey)
Date: 29 Jun 2003 03:10:22 GMT
Subject: Re: four bottles

Duncan Booth writes:
> Not a proof that this is the shortest, but my
> reasoning why I believe that five is the shortest:
> ...

Out of curiosity, I decided to find the shortest
solution by exhaustive search.  Call the
possible nonfinal bottle positions (up to
rotation)
 1: D D D U
 3: D D U U
 5: D U D U
 7: D U U U .
The state of the player's knowledge is what
subset of the four positions is still possible.
My program finds that from the initial state
(1357), the first two moves must reduce the
possibilities to (1) or (7) with two probes.
The use of one opposite and one adjacent
probe has already been seen.  Another way
is to use two opposite probes, e.g.:
  1. Turn both opposite bottles up.
  2. If both opposite bottles are up, turn them
     both down.  Otherwise turn both up.
This ensures that only one bottle is up, because
otherwise the game would be over.

The next three moves must be an opposite probe
yielding (3), an adjacent probe yielding (5), and
an opposite probe yielding ().

It might be interesting to see what strategy
minimizes the expected length of the game.

Dan Hoey
haoyuep@aol.com