Jul 26, 2006



  1. Basic chess rules apply, except:
  2. When a piece makes a capture, it reduces rank and buds off
     a piece one rank lower, leaving this behind on the exit square.
     Ranks: KQRBNP-.


The Hydra game is a one-person game.

You start with a rooted tree, and at any move, you may remove one
leaf, and then duplicate (later triplicate, quadruplicate etc)
the whole remaining subtree it leaves, right down to the root.
The "n" in the n-plicate goes up one on every move, starting at 2.

                    *   *                         * *   * *
                     \ /                           \|   |/
So e.g. if we     *   *   *  ...it goes             *   *   *
delete the left    \ /   /      to this one,         \  |  /
leaf from this      *   *       when n=2.             * * *
tree...              \ /                               \|/
                      R                                 R

The number of nodes increases dramatically every time, but... the theorem is, no matter what you start with, and how you choose your leaf cuttings, IT WILL ALWAYS REDUCE to the empty tree, eventually !!

In fact, you don't even have to restrict yourself to increasing the n by one every time, you can up it in squares or powers of two or anything you like!

And it's one of those things that can be easily stated in basic number theory, (PA), but not proved there.  To prove it requires knowing about infinite ordinal numbers up to epsilon_0, if that means anything to you, which is the first ordinal that PA "can't handle".  i.e. can't prove that it is an ordinal, i.e. that
the above process must halt, (as it executes a decreasing series of ordinals, which therefore must always terminate).

You can see how the newly proposed budding chess emulates this slightly; there is an increasing number of pieces, but the total metric (in an appropriate sense) is always decreasing... i.e. the "top value".

1 comment:

JNS said...

LIM comes to mind...