Tree-pruning game with the devil

Question

You won the coin-flipping game against Satan, but being the devil he is, he decided that that game was much too easy, and reneges on his promise to let you go. Instead, he gives you a new, more difficult game, this time promising by crossing his heart and hoping to die that he will let you go if you can finish this game.

The game starts with a single spindly tree, like this:

The tree is only a single branch, with seven segments.

Every turn, the following happens:

1. You can cut off one segment of the tree that doesn't have anything branching off of it. (For the first turn, only the top segment can be cut off.)

2. Satan can then make $N$ copies of the branch system just below the base of the branch you just cut off, where $N$ is as large an integer as he wants. However, if you cut off a branch next to the root, then Satan can't do anything as there's nothing below the root.

The first few steps of the game might go like this:

After your first move, Satan decides to make two copies. And after your second move, Satan makes three copies of the tree below it. He's being nice here — he could make a thousand copies, or even a googolplex copies!

---

Satan promises that he will release you if you can prune the tree down to its root. Do you have a winning strategy? Or will Satan manage to keep you in hell forever?

Answer 1

All the segments will eventually vanish. We can even inductively demonstrate it.

First, terminology.

• Let's call the segment just before the first fork the base.
• Let's call the sequence of segments terminating at the base the trunk.
• Let's call each fork off of the base a branch.

First, let's do some pre-validation. Let's assume there's a way to remove an entire branch. (This will be shown later.) Then, Satan has to copy the base, which means it becomes a branch off the segment before it. Thus, the base moves one step down the trunk.

However, eventually, there won't be any trunk to move down. At this point, you can remove the remaining branches (as Satan can't copy them anymore), and you win.

From this, we can show that it's irrelevant how many branches Satan makes. It just makes the execution annoyingly long. Suppose Satan makes $n$ copies of a branch. The winning strategy above only requires moving one branch, which we've assumed we can do. Therefore, no matter what $n$ Satan chooses, we have one branch to remove. The other $n-1$ branches become part of each individual new branch when Satan copies the base.

---

As concluded, if you have a way to remove an entire branch, you win. So let's do it.

Let's say a branch has a base segment and $n$ $1$-length branches each called $B_1$. There are a finite number of these branches. If we prune one of the one-length branches, we end up with a finite number ($x_1$) of bases with $n-1$ one-length branches. We've removed one branch, and Satan gets to copy this a finite number of times. We can prune all $n$ branches, and end up with $x_1+\ldots+x_n$ bases with $n-1$ one-length branches. This process can be repeated until the number of one-length branches is zero. Therefore, a $B_1$ branch is removable.

Let's say a branch has a base segment and $n$ $2$-length branches each called $B_2$. Because these branch off, each branch can be expressed as its own $B_1$. Since we know $B_1$ branches are removable, we can remove them, resulting in the removal of $B_2$ branches.

Let's say a branch has a base segment and $n$ $w$-length branches, each called $B_w$. Each of $B_w$ can be split into unique $B_{w-1}$ branches. These can each be split into $B_{w-2}$ branches. Each of these can be split into $B_{w-3}$ branches, which can be split... until we have $B_{w-(w-1)}=B_1$ branches. Example for $B_3$:

Since $B_1$ branches are removable, we can remove them. This implies that $B_2$ branches are removable. Since all $B_{n+1}$ branches can be split into $B_{n}$ branches, and $B_n$ branches are removable, so are $B_{n+1}$ branches.

Consequently, by inductive reasoning, any branch can be removed.

Since any branch can be removed, by the above, you win the game.

Answer 2

A proof via ordinals. Probably overkill. I'm not well-versed in ordinal arithmetic, so I hope I haven't made any unwarranted assumptions.

Assign a tree an ordinal value inductively:

• The empty tree is $1$
• Two trees of value $s$ and $t$ have value $s+t$ if joined at their roots. So, $n$ copies of a tree $s$ joined this way have value $\underbrace{s + \dots + s}_{n \text{ times}} = ns$.
• A tree of value $s$ on top of an additional segment has value $\omega ^s$, where $\omega$ is the first infinite ordinal.

We use the "natural" arithmetic defined by transfinite recursion, not the one based on combining order types. In particular, this means addition and multiplication commute.

For example, in this process, restricting to just the top three levels in the first picture (ignoring the bottom four), the trees have values

$$\omega ^ {\omega ^ \omega}, \omega^{3\omega}, 4 \omega^{2\omega}$$

We argue that each step decreases the value, and so since ordinals are well-ordered, any strictly decreasing sequence must terminate.

Since ordinal (natural) sum and exponent are strictly monotonic, it suffices to argue that the sub-tree affected decrease in value. This sub-tree consists of the deleted segment, the segment below it, and the segment's "siblings" above that segment, whose value we call $s$.

So, the original value is

$$\omega ^ {\omega + s}$$

which changes to $$n \omega ^ {s},$$ when the segment is deleted and the branch is duplicated $n$ times. Using the exponent distributive property,

$$ \omega ^ {\omega + s} > \omega ^ {1 + s} = \omega \times \omega ^ s > n \omega ^ s, $$

where we used the fact the multiplication is strictly monotonic. So, the cutting process decreased the ordinal value, and so only a finite number of cuts are possible.

(I'm unclear on whether exponentiation distributes for ordinals, but the $\omega ^ {1 + s}$ case holds by definition.)

Answer 3

We can think of this tree as a directed graph, by directing edges to point away from the bottommost vertex. The degree of a vertex is the number of outward pointing edges out of it.

At any time, let $h$ be the height of the second highest vertex (so the height of the tree is $h+1$, but every vertex at height $h+1$ has no branches). Let $d$ be the highest degree among the vertices at height $h$. In your pictures, the pairs $(h,d)$ are $(6,1)$, $(5,3)$ and $(5,2)$, from left to right.

Let's say you cut a branch from a vertex of degree $d$, at height $h$. Then the vertex you chopped now has degree $d-1$. Furthermore, the vertices Satan creates at height $h$ will only have degree $d-1$, since they are copies of the vertex you mutilated. This means the number of degree $d$ vertices at height $h$ decreased, while no vertices of greater degree were created at that height.

Thus, if you keep chopping from vertices of height $h$ and degree $d$, you will eventually remove all of them, so that the maximum degree at height $h$ becomes $d-1$. Repeating this, we can decrease the maximum degree of any vertex at height $h$ all the way down to 0, at which point there can be no vertices at height $h+1$, so that the height of the entire tree decreased.

Thus, at any time we can decrease the height of the tree. Doing so seven times destroys the tree. Of course, the time you must remain in Hell is unbounded.

Alternatively: To each a tree whose height is $h+1$, where the highest degree node at height $h$ is of degree $d$, and where there are $n$ vertices of degree $d$ at height $h$, assign the ordinal $$ h\omega^2+d\omega+n $$ By the same argument as before, chopping any of the maximal degree vertices at height $h$ will leave a smaller ordinal. This is beacuse there were three possibilities: either $h$ decreased, or $h$ stayed the same while $d$ dropped, or both $h$ and $d$ stayed while $n$ dropped. Ordinals are well-ordered, so there can't be an infinite decreasing chain of ordinals, so this process must stop.

Answer 4

Assign each tree a tuple $(a,b,c)$ where $a$ is the number of branch-points on the longest path, $b$ is the maximum multiplicity of branches at the highest branch point, and $c$ is the number of branches at the highest branch point with multiplicity $b$.

The initial tree is defined to have 6 branch points, each with multiplicity 1. Thus, the original tree has tuple (6,1,1), and your goal is to reduce $a$ to 0.

You can cut at any branch point that does not have a branch point above it. Thus, if you make a cut at a branch with multiplicity 2, you have effectively removed that branch point, since on your next turn you may cut at the next branch point lower.

If you order the set of all possible trees by sorting on $a$, then $b$, then $c$, you can always reduce the tree to one of a lower order: find one of the highest branch points of maximum multiplicity and cut a branch off it. This will reduce $c$ by 1. Unless $c$ was already 1, in which case it would reduce $b$ by 1. Unless $b$ were 2, in which case it would reduce $a$ by 1.

When Satan adds branches, he can only add branches with lower multiplicity than the branch you cut. In other words:

1. If $c>1$ before your cut, you reduce the tree to $(a,b,c-1)$ and Satan adds branches at depth $a$, but with multiplicity $b-1$, so the sort order does not change.

2. If $b>2$ and $c=1$ before your cut, you reduce the tree from $(a,b,c)$ to $(a,b-1,X)$. Satan can then increase that to $(a,b-1,X+Y)$, but that is still lower order than what you started with.

3. If $b=2$ and $c=1$ before your cut, you reduce the tree from $(a,b,c)$ to $(a-1,X,1)$, which Satan can increase to $(a-1,X+Y,1)$, but that is still less than what you started with.

In the example given, the tree goes from (6,1,1) to (5,1,1) to (5,3,1) to (5,2,1) to (5,2,4). Your next cut would reduce it to (5,2,3), and 3 further of your cuts, the tree would be down to $(4,X,1)$.

He can make it take an arbitrarily long time, but each branch you cut will bring the tree closer to $a=0$.