# You dig a hole in Minecraft straight down $n$ blocks, how many blocks must you dig to get out?

I was thinking on this question and came to the solution $$3(x-2)$$ (where $$x$$ is the depth of the hole and $$x\ge3$$) which I am fairly confident in. Although, I wanted to prove it for any hole that is $$n$$ blocks deep, could anyone illustrate how I could formally do this using something like induction?

• As someone who hasn't really played Minceraft at all, an explanation of the relevant game mechanics would be useful Commented Apr 5, 2023 at 21:19
• Yes, I suppose that would be helpful. So your character has a height of two blocks. Say you are in a deep hole. To get out you must break a block in front of you to form a step up, a second block above that one so your player will fit, and finally the block directly above your head to jump to the first step of your stair. This would continue in all cases but a 2 deep hole (where you just need to break the block in front of you as the surface is above you and not blocking you) and a 1 block hole which you can just jump out of. Commented Apr 5, 2023 at 21:25
• Let me know if that helped at all. Commented Apr 5, 2023 at 21:26
• Can't you do it in about $2n$? (Maybe I'm not clear enough on how jumping works.) Let's say the blocks one layer above the block you're standing on (i.e. the ones you can kick) are at height $1$. Dig out the blocks at heights $2$ and $3$ in front of you. Jump into the resulting hole. Now turn $180^\circ$; dig out the blocks at heights $3$ and $4$ and then jump into the resulting hole. Repeat until you exit. We dig out two block for every one block of height we gain, so we get $2n$ plus change. Commented Apr 5, 2023 at 23:13
• @NicholasTodoroff Maybe I'm misunderstanding what you are describing, but that doesn't seem possible since the player's head needs to be able to clear height $4$ in the first dig to be able to make the jump. Commented Apr 5, 2023 at 23:52

You are correct, and you can prove this by induction. Let's do it!

Let $$a_n$$ be this sequence, and let $$A$$ be the subset of elements in $$\{ 3, 4, ... \}$$ for which the statement $$a_n = 3 (n - 2)$$ holds.

Base Case

We first show that it holds for $$n = 3$$. In this case, you need to dig $$2$$ blocks in the column directly in front of the hole, and $$1$$ block in the next column. The total is $$3$$, which is equal to $$3 (3 - 2) = 3 (1)$$.

Inductive Step

Suppose the statement is true for $$n$$; we show it is true for $$n + 1$$. Since we have already shown it to be true for $$n = 3$$, we will assume that $$n \ge 4$$. In this case, one must again dig $$2$$ blocks in the column in front of the hole. But in order to continue moving upwards (assuming no other paths, of course), an additional block above those $$2$$ must be removed. Now, the player moves to the new column and her elevation increases by $$1$$. The situation at this point is the same as if the player had started in a hole with depth $$n$$ (you should convince yourself of why this is true). Therefore, the total number should be $$a_{n + 1} = 3 + a_n = 3 + 3 (n - 2) = 3 n - 3 = 3 ((n + 1) - 2)$$, as desired.

Therefore, we have shown that $$A = \{ 3, 4, ... \}$$; i.e., $$a_n = 3 (n - 2)$$ holds for all $$n \ge 3$$.

It might be worth extending the sequence to include $$0, 1, 2$$. For $$n = 0$$, $$a_n = 0$$ obviously. For $$n = 1$$, $$a_n = 0$$ too, since you mentioned that the player can simply jump out of $$1$$-high holes. For $$n = 2$$, $$a_n = 1$$. It turns out to be this sequence, for what it's worth.

• It was really cool to see it formally proven, thank you for taking the time to write this! :) Commented Apr 6, 2023 at 0:59