In an $n\times n$ table, initially there is a $1\times n$ tile in each row. A swap is an operation that involves choosing two tiles, move one square from the first to the second tile, and simultaneously move one square from the second to the first tile. Tiles can change shapes arbitrarily - the only constraint is that each tile must remain (edge-)connected throughout and does not have a hole in it. Is it possible to perform swaps and end up with an $n\times 1$ tile in each column?

For $n=2,3,4$ it can be easily checked that this is possible. $n=5$ is also possible but the sequence is much more complicated, and it is not clear there is a pattern.

  • $\begingroup$ You didn't forbid tiles with holes so I guess they are allowed. Correct? $\endgroup$ – Brendan McKay Sep 26 '19 at 6:54
  • $\begingroup$ @BrendanMcKay Good point. They are not allowed. $\endgroup$ – pi66 Sep 26 '19 at 7:14
  • $\begingroup$ Are there any two configurations that cannot be converted into each other by a series of swaps? $\endgroup$ – domotorp Sep 26 '19 at 8:18
  • $\begingroup$ Does "choosing two tiles" refer to "distinct" tiles? Meaning we can't swap two squares of the same tile; Meaning we can't modify an individual tile by itself, to change (reconnect differently) its border structure. - Or is choosing tiles not distinct, and we can do this? $\endgroup$ – Vepir Sep 26 '19 at 11:28
  • $\begingroup$ @Vepir The tiles must fill in the table exactly, so there's no way to do a swap within a tile. $\endgroup$ – pi66 Sep 26 '19 at 12:42

Yes, it is possible. The procedure I came up with is really tedious to describe in detail, but I'm attaching a sketch that hopefully should make things clear.

For $k \leq n$ denote by $T_{n,k}$ the following tiling of a $k \times n$ grid. The first tile uses all $k$ squares of the leftmost column, and the leftmost $n-k+1$ squares of the bottom row. The $i$-th tile for $i > 1$ consists of all squares that are incident (vertically, horizontally, or diagonally) to squares of the $(i-1)$-th tile, but have not been used in any other tile.

In particular, $T_{n,n}$ is the tiling where each column is a tile, and $T_{n,1}$ consists of a single tile containing all squares. It's not hard to check that each tile of $T_{n,k}$ consists of exactly $n$ squares. The top left sketch in the attached picture shows $T_{n,k}$ for $n=8$, $k=5$.

I claim that there is a sequence of swaps taking us from $T_{n,k}$ to a tiling where one tile occupies the top row, and the remaining rows form a tiling $T_{n,k-1}$. Applied inductively, this allows us to go from $T_{n,n}$ (all columns) to the tiling where every row is its own tile.

As I mentioned, this sequence is a bit tedious to describe, but I hope that it is clear from the attached picture: in every step, each tile is a path. We swap the green initial piece of one of the paths for the red final piece of the path starting in the top left corner (the tiles stay connected, if we do the swaps in the order indicated by the arrows).

After such a sequence of swaps, the last square of the path starting at the top left corner will be incident to the next path we'd like to perform swaps on. Conversely, the first square of that next path will be incident to the path starting at the top left corner, so we can keep going until one of the tiles occupies the top row. Note that in the $i$-th step we are transforming the $(i+1)$-th path of $T_{n,k}$ into the $i$-th path of $T_{n,k-1}$ on the bottom $k-1$ rows, so the result of our swap sequence is as claimed.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.