Finite and transfinite variations of Escape!

Can you win the Escape! game with transfinite play? Can you win a finite-board variation of the game?

Last week I had made a post about the game Escape! It was an excerpt from my book Proof and the Art of Mathematics, which aims to teach aspiring mathematicians how to write proofs in the context of compelling mathematical assertions having interesting, elementary proofs. In the post, I had introduced the game Escape! and proved the impossibility theorem.

This week, in this post I should like to consider several natural variations of the game, including some finite variants and also some transfinite ordinal-time variants.

Let’s have some fun!

Quick review of the Escape! game

Let me quickly review the game and the impossibility theorem, which was covered in last week’s post on the Escape! game.

In the Escape! game, we begin with three stones in the corner of an infinite board, a quarter plane of squares. The rule of movement is that you can select any stone you like, and it will split into two stones, one moving to the square above and one moving to the square to the right of where it had been. The move is allowed only when both of those squares are empty, so that they may accept the new stones. The goal is to vacate the shaded L-shaped region at the origin.

Can you vacate the shaded corner area? Please give it a try.

One can easily make a good start, but then you will find that the outer stones begin to block one's path. You have to move these other stones out of the way to make room. Is it possible to get all three stones out of the corner?

I have provided an online interactive version of the game for trying out strategies and ideas at https://scratch.mit.edu/projects/195391196, and see also my blog post at http://jdh.hamkins.org/escape.

Interlude

Did you succeed? Perhaps one begins to think that it is impossible. But how could one ever prove such a thing?

The impossibility theorem

In fact, there is no way to win this game.

Theorem. It is impossible to make moves in the Escape! game so as to vacate the shaded corner region.

Proof. Let us assign weights to the squares in the lattice according to the following pattern: We give the corner square weight ½, the next diagonal of squares ¼ each, and then ⅛, and so on throughout the whole playing board. Every square gets a corresponding weight according to the indicated pattern.

The weights are specifically arranged so that making a move in the game preserves the total weight of the occupied squares. That is, the total weight of the occupied squares is invariant as one makes moves, because moving a stone with weight 1 / 2ⁿ will create two stones of weight 1 / 2ⁿ⁺¹, which adds up to the same. Since the original three stones have total weight ½ + ¼ + ¼ = 1, it follows that the total weight remains 1 after every move in the game.

Meanwhile, let us consider the total weight of all the squares on the board. If you consider the bottom row only, the weights add to ½ + ¼ + ⅛ + ⋯, which is the geometric series with sum 1. The next row has total weight ¼ + ⅛ + 1/16 + ⋯, which adds to ½. And the next adds to ¼, and so on. So the total weight of all the squares on the board is 1 + ½ + ¼ + ⋯, which is 2. This leaves a total weight of 1 for the unshaded squares.

The subtle conclusion is that after any finite number of moves, only finitely many of those other squares are occupied, and so some of them remain empty. So after only finitely many moves, the total weight of the occupied squares off the original L-shape is strictly less than 1. Since the total weight of all the occupied squares is exactly 1, this means that the L-shape has not been vacated. So it is impossible to vacate the original L-shape in finitely many moves. □

A Finite Escape! Variation

Let us now begin in earnest with the new ideas of this post.

Suppose we try to play the game of Escape! on a finite n × n board, such as the 30 × 30 board pictured here.

Play will proceed just as in the infinite game, but modified in the natural way that might be expected for moves made on the outer edges at right and top. Namely, when moving on these edges, we implement the rule as well as we are able on the n × n board, but any stones that would have appeared outside the given region are simply not placed—they are imagined as having fallen off the board and out of play.

If you have spent much time playing Escape! on the infinite board, you have surely experienced its central irritating feature—the stones steadily accumulate during play, getting more and more in the way as play progresses. The board inevitably becomes crowded with stones, which stand as obstacles and as further obstacles behind those obstacles, preventing the critical moves that one would really prefer to be making instead. One is never able to clear away the clutter and have the space near the shaded corner that would enable one to escape the corner with the third stone.

Shouldn't we expect this irritating crowding feature to be just as much present on the finite board? Can we hope to escape the shaded corner? Will this depend on the size of the board?

Interlude