4

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?

Kamal Saleh
  • 6,497
tothemax
  • 59
  • 3
    As someone who hasn't really played Minceraft at all, an explanation of the relevant game mechanics would be useful – gist076923 Apr 05 '23 at 21:19
  • 2
    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.

     – tothemax Apr 05 '23 at 21:25
  • Let me know if that helped at all. – tothemax Apr 05 '23 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. – Nicholas Todoroff Apr 05 '23 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. – K. Jiang Apr 05 '23 at 23:52
  • Why would you not place the blocks you have dug below you to get out? Or if there's nothing in inventory, dig a parallel hole and use those blocks to raise yourself up? – Macavity Apr 06 '23 at 13:24
  • @K.Jiang I'll have to try, I seem to remember you can jump out of a room with a ceiling into a room with no ceiling and gain the full height of the jump, but I could be wrong. – Nicholas Todoroff Apr 06 '23 at 15:43

1 Answers1

5

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.

K. Jiang
  • 7,210