We show that each of the 5 possible cheats fulfills the claim.

1.

:   If it makes a non-counting cheat, $q_0$ will go to $q_2$ over $\#$, and will reach $heaven$. (This is also the case if it has additional letters different from $\#$ after the letter.)

2.

:   If it makes a positive cheat on $x$, $q_0$ will go to $q_3$ upon reading the next $\#$. When the cheat occurs, the value of $x$ is positive, while reading the letter . Notice that the value of $\A$’s counter is accordingly bigger than its value when entering $q_3$ (and by the inductive assumption bigger than $n$). Then, $q_3$ goes to $q_0$ with weight $-1$, guaranteeing that $\A$’s counter value is at least $n$. Notice that the counter value cannot go below $n$ at any point, since $\M$ cannot make the value of $x$ negative without a counting cheat. (We equipped $\M$ with a counter check before every decrement.)

3.

:   If it makes a negative cheat on $x$, $q_0$ will go to $q_4$. Then, when the cheat occurs, the value of $x$ is $0$, while there is the letter . Notice that the value of $\A$’s counter is accordingly exactly 