17
$\begingroup$

(Special thanks to greenturtle3141 for providing an intriguing narrative backstory to my puzzle.)

To aesthetically appeal to his customers, Hilbert has recently redesigned his hotel. You see, all rooms in the new building lay out on a plane infinitely extending in all directions, in the pattern of a hexagonal grid, the bestest geometry of all:

         ...
   * * * * * * * *
    * * * * * * *
   * * * * * * * *
... * * * # * * * ...
   * * * * * * * *
    * * * * * * *
   * * * * * * * *
         ...
---------------------
(The rooms are labeled by * and # signs.)
(The # sign labels Room 0, one of the rooms of all time.)

Proving Hilbert a success, guests soon filled out each room available, until one day, a one-headed hydra appeared, invited itself into Room 0 and started antagonizing its guests. Hilbert has hired you, an expert on hydras, to try and move the hydra to another room (hopefully with less guests).

If you lop a hydra head in some room, then the hydra will grow three new heads in its neighboring rooms, depending on which hand you lop the head with. You have two choices. You may choose to regrow the hydra heads as such:

 . .      . @
. @ . => @ . .
 . .      . @
--------------
(The @ sign indicates a hydra head.)

Or as such:

 . .      @ .
. @ . => . . @
 . .      @ .
--------------
(The @ sign indicates a hydra head.)

The hydra, being benevolent to you, allows you to also reverse the process. That is, whenever you choose to simultaneously lop off three hydra heads in either of the formations above, a single new head will grow in the middle.

  • Note: A room may contain multiple hydra heads, but the number of hydra heads in a room at any time should always be a non-negative integer.

For which of Hilbert's rooms X, if any, can we move the hydra to room X, in the sense that after some finite sequence of hydra head-huntings, there could exist hydra head(s) only in room X?

$\endgroup$
1
  • 1
    $\begingroup$ Infinite hotel? I call that a beehive. $\endgroup$
    – Florian F
    Aug 23, 2022 at 9:15

2 Answers 2

10
$\begingroup$

Hilbert realized that,

for any direction of "up" he chose, splitting (resp. rejoining) a hydra head on a given floor added (resp. removed) a head on the adjacent floors and left the number of heads on all other floors unchanged. Thus, floors two apart needed to cancel one another if there was to be some sort of invariant that the hydra needed to obey.
Applying this criterion to all floors at a given parity revealed that the sum of all heads at distances $k$ modulo $4$ needed to balance all the heads at distances $k+2$ modulo $4$.
This means that a lone head can only travel in steps of length $4$.
"You could weight floors with the powers of $i$!" he proclaimed to a tenant, who was far too busy moving his belongings to appreciate the mathematics of the situation.

"But how to move the hydra?", Hilbert pondered.

He figured that the best approach was to generalize - allow headcounts to be negative, and interpret moves as simply decrementing one room and incrementing three others.
Filching some scratch paper from a passerby, he scrawled a diagram (of which the below is only a crude reproduction): enter image description here
This sequence of four moves (which could be done in any order, akin to a Lights-Out puzzle) was precisely the $4$-step Hilbert had just proven to be fundamental!
All that was required was a sequence of moves that would place hydra heads in the rooms that were marked red (just one would do; all marked rooms in the above have a headcount of $\pm 1$) to ensure that the moves could be carried out with a real hydra.

Unfortunately for Hilbert, this wasn't quite enough.

He realized that every move that would fill up the auxiliary rooms would need to be carried out in reverse - with one fewer head in Room $0$. This would require Room $0$ to always have a head in it, and so the first split could never happen! (None of the moves in the basic $4$-step occur on the starting space.)

A more complicated approach was going to be required...

Like this one, perhaps:
enter image description here

$\endgroup$
1
  • $\begingroup$ Both solutions look good to me; I'm accepting this one since it has a better proof of necessity. Good work! $\endgroup$
    – Edward H
    Aug 22, 2022 at 22:20
6
$\begingroup$

I claim that we can reach the following subset of rooms:

     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . X . . . X . . . X . . . X .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . X . . . # . . . x . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . X . . . X . . . X . . . X .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
 

Proof:

  1. These are reachable:

Building block 1: the marching pair

     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . 1 . 1 . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . 2 . . . . . . . . . .
     . . . 2 . . 2 . . . . . . . .
      . . . . 2 . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . 3 . 3 . . . . . . . .
      . . . . . . . . . . . . . . .
 

Hope it is clear how to read the figure.

Building block 2: square out of thin air

      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . 1 . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . 2 . . . . . . . . . . .
      . . . . 2 . . . . . . . . . .
     . . . 2 . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . 3 . 3 . . . . . . . . .
      . . . 3 . . . . . . . . . . .
     . . . 3 . 3 . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
 

Ok, not really a square nor out of thin air but note that the "seed" stays effectively put.

Combining the two:

      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . # . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . * . * . . . . . . . . .
      . . . # . . . . . . . . . . .
     . . . * . * . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . * . * . . . . . . . . .
      . . . 2 . * . . . . . . . . .
     . . . * . * . . . . . . . . .
      . . . * . * . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . * . * . . . . . . . . .
      . . . # . * . ! . . . . . . .
     . . . * . * . . . . . . . . .
      . . . * . * . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . * . * . . . . . . . . .
      . . . . . . . ! . . . . . . .
     . . . * . * . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . * . * . . . . . .
      . . . . . . . ! . . . . . . .
     . . . . . . * . * . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . ! . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
 

Here # is the starting room, ! the destination and 2 means two heads in that room.

  1. others cannot be reached: Tile the grid and colour with colours 0,1,2,3:

      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . 0 1 2 3 . . . .
      . . . . . . 0 1 2 3 . . . . .
     . . . . . . 0 1 2 3 . . . . .
      . . . . . 0 1 2 3 . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
      . . . . . . . . . . . . . . .
     . . . . . . . . . . . . . . .
 

We can use this colouring in three orientations.

Now observe:

  1. The total number of hydra heads changes by 2 every move. The total number of moves must therefore be even.

  2. The total number of heads weighted with room colour changes to its negative modulo 4 each step and stays the same modulo 4 every other step.

As 2 holds for all three main orientations the claim follows.

Note: there is a small gap in this proof. OP allows in principle for multiple heads in the destination room, which would invalidate much of my reasoning.

$\endgroup$
6
  • $\begingroup$ I really need to spend less time writing answers... $\endgroup$ Aug 22, 2022 at 21:44
  • $\begingroup$ @AxiomaticSystem Well, yours looks a bit cleaner than mine. Does your argument deal with the possibility of multiple heads in the destination room (mine doesn't)? $\endgroup$
    – loopy walt
    Aug 22, 2022 at 21:54
  • 1
    $\begingroup$ I believe I have: Using the powers of i, the sums across heads have to be 1 in all directions. If all heads are in the same room, this only holds if the room has value 1 in every direction and there is exactly one head in it. $\endgroup$ Aug 22, 2022 at 21:59
  • $\begingroup$ @AxiomaticSystem not sure I follow. What is i? $\endgroup$
    – loopy walt
    Aug 22, 2022 at 22:06
  • 1
    $\begingroup$ The imaginary unit, raised to the (signed) number of rows from Room 0. $\endgroup$ Aug 22, 2022 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.