A372478 Number of steps required to kill a Kirby-Paris hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new subtrees sprout from the head's grandparent node (see comments).

0, 1, 3, 37

Offset: 0

Author

Paolo Xausa, May 02 2024

Keywords

• nonn
• hard

Comments

This is a variation of A372101 in which the hydra grows new subtrees instead of new heads. See Kirby and Paris (1982), p. 286, for a detailed explanation (with diagrams) of this process, for a generic hydra.

Similar to A372101, the initial configuration of this specific hydra is a path with n segments. The rightmost head is the next to be chopped off. When this happens at step s, s new replicas of the subtree above the removed head's grandparent node (which includes the segment connecting the head's parent and grandparent) sprout to the right of the grandparent node. If the chopped head has no grandparent, no subtrees are added.

As an example, here's how the following hypothetical portion of the hydra evolves, assuming we are at step 2 (H = head, o = node, X is chopped head, P = parent node, G = grandparent node):

.

H H H H H H H H

\ | \ | | | | |

o o X o o o o o o 2 new replicas (excluding the removed segment)

\|/ \| |/ |/ of the subtree "above" (and including) the

P ---> o o o G-P segment grow at the right of node G

| |/ /

H--o--G H--o--G----

| |

.

According to the Wikipedia article, a(4) >> Graham's number.

In their paper, Kirby and Paris prove that no matter what the starting configuration of the hydra is--as long as it's a finite tree--and no matter which head is chosen to be chopped off next, the hydra will eventually be defeated.

See A180368 for a variation in which only one new subtree grows after each chopping.

Examples

			In the following tree diagrams R is the root, o is a node and H is a head (leaf). Head chopping (leaf removal) is denoted by X.
For n = 2, the sequence of the 3 choppings is:
.
  H        X
   \        \
    o        o   H    H   X    X
     \        \ /      \ /      \
      R        R        R        R
.
For n = 3, the sequence of the 37 choppings is:
.
  H        X
   \        \
    o        o   H    H X H   H   H   H   X      H   H
     \        \ /      \| |  /     \  |  /        \  |
      o        o        o o o       o o o H H H    o o X X X X
       \        \        \|/         \|/ / / /      \|/ / / /
        R        R        R           R------        R------
.
  H   X          H              X
   \  |           \              \
    o o H (8) H    o   X (9) X    o   H  (18)  H   X   (19)  X
     \|/ ... /      \ / ... /      \ /  ...   /     \  ...  /
      R------        R------        R---------       ---R---
.
		

Links

• Laurie Kirby and Jeff Paris, Accessible Independence Results for Peano Arithmetic, Bulletin of The London Mathematical Society, 14, 1982, pp. 285-293.
• PBS Infinite Series, Kill the Mathematical Hydra, YouTube video, 2017.
• Wikipedia, Hydra game.

Crossrefs

Cf. A180368, A372101, A372421.

Last element in each row of A372595.