Question 55
Let $N$, $k$ be positive integers with $k \le N$. An $(N, k)$-Mountain Tetris mini-game is played on an $N \times N$ grid. An *ascending path contour* is any path on the grid made of horizontal and vertical segments, which starts at $(0, 0)$ and reaches $(N, N)$ without ever going down or back.
Every $(N, k)$-Mountain Tetris mini-game begins with a mountain having an *initial ascending path contour* which starts from $(0, 0)$ in horizontal direction, and has exactly $k$ horizontal and $k$ vertical segments. A $1 \times 1$-square rock drops vertically from a random slot on the grid ceiling. A *move* consists of shifting the rock 1 unit to the right. The game is won if the player performs the minimum number of moves needed so that when the rock settles on the mountain, the resulting shape is still an *ascending path contour*. The game is then reset and begins with a new initial ascending path contour.
Prove that the average number of moves played over all possible $(N, k)$-Mountain Tetris mini-games equals
$$
\frac{N-k}{k+1}.
$$
Here is an example of a $(6, 4)$ Mountain Tetris mini-game with an initial ascending path contour. The player needs one move to win.
Every $(N, k)$-Mountain Tetris mini-game begins with a mountain having an *initial ascending path contour* which starts from $(0, 0)$ in horizontal direction, and has exactly $k$ horizontal and $k$ vertical segments. A $1 \times 1$-square rock drops vertically from a random slot on the grid ceiling. A *move* consists of shifting the rock 1 unit to the right. The game is won if the player performs the minimum number of moves needed so that when the rock settles on the mountain, the resulting shape is still an *ascending path contour*. The game is then reset and begins with a new initial ascending path contour.
Prove that the average number of moves played over all possible $(N, k)$-Mountain Tetris mini-games equals
$$
\frac{N-k}{k+1}.
$$
Here is an example of a $(6, 4)$ Mountain Tetris mini-game with an initial ascending path contour. The player needs one move to win.