(I have no idea how to simplify the title. You can change it to make it briefer.)
In this variant of Tower of Hanoi, we relax the restriction that no disk may be placed on top of a disk that is smaller than it.
Specifically, the three stacks each have $n$ slots whose sizes range from $n$ to $1$ from top to bottom. There are $n$ disks whose sizes are also range from $n$ to $1$.
The restrictions are:
- Only one disk can occupy a slot at a time, and its size must be smaller than the slot.
- Only one disk can be moved at a time.
- Each move consists of taking the top disk from one stack and placing it in a hole in another stack, if no higher slots are occupied.
- (optional) You can only move to adjacent stacks.
Here are some example moves.
| slot | stack 1 | stack 2 | stack 3 |
|---|---|---|---|
| 3 | 3 | ||
| 2 | 2 | ||
| 1 | 1 |
| slo | stack 1 | stack 2 | stack 3 |
|---|---|---|---|
| 3 | 3 | ||
| 2 | 2 | ||
| 1 | 1 |
| slot | stack 1 | stack 2 | stack 3 |
|---|---|---|---|
| 3 | 3 | ||
| 2 | 2 | ||
| 1 | 1 |
| slot | stack 1 | stack 2 | stack 3 |
|---|---|---|---|
| 3 | 3 | 1 | |
| 2 | 2 | ||
| 1 |
Starting from the last situation, these are two illegal moves:
This one violates the first rule:
| slot | stack 1 | stack 2 | stack 3 |
|---|---|---|---|
| 3 | 1 | ||
| 2 | 3 | 2 | |
| 1 |
And this one violates the third rule:
| slot | stack 1 | stack 2 | stack 3 |
|---|---|---|---|
| 3 | 3 | ||
| 2 | 2 | ||
| 1 | 1 |
At the beginning the discs are all in the slots of the left stack. (The discs must be ordered from $n$ to $1$ from top to bottom, otherwise the first rule will be violated. Note that this is the opposite of the original Tower of Hanoi rule.) What is the minimum step to move them to the right stack?
I think the answer is the same as the original version, which is $f(n)=2^n-1$, or $g(n)=3^n-1$ if the last constraint is valid, but I have no idea how to prove it.
Update: With $n=4$, It can be constructed that $f(n)=13$ instead of $15$, so the first formula doesn't hold. I wonder if it's the sequence A341579.