3
$\begingroup$

Suppose you have a $n$x$n$ grid, and you place $k$ tiles on it at random, such that it is possible to rearrange the tiles into a pattern symmetrical about every major axis of the square grid (diagonals, horizontals and verticals).

My question is, in general, what is the number $a$, in terms of $n$ and $k$, such that given any random tiling of the grid, it can be restored to symmetry in no more than $a$ moves. I should clarify that a single move consists of swapping an empty square with an edgewise adjacent tiled square.

An example of a sequence on a $3$x$3$ grid is shown below:

enter image description here

In this example, $n = 3$ and $k = 4$. I have verified by hand that $a = 4$ is the minimum needed for these values to ensure a grid can always be restored to symmetry.

I've attempted to solve this problem by analysing every possible symmetry, for a specific value of $n$ and $k, $ and trying to use them to generate the initial starting configurations, such that after $a$ iterations of the generation, every possible starting configuration would be available in the generated set. However, this didn't seem to lead anywhere useful.

The issue I'm facing is, for larger values of $n$, the number of possible symmetries the square can have grows pretty fast, and the issue becomes choosing the right one such that the choice minimizes the moves needed to reach it. Is this problem feasible to solve in the general case, or does it depend on too many factors?

$\endgroup$
2
  • 1
    $\begingroup$ Do the swapped squares need to be adjacent? This is suggested by your example but not mentioned in the post. $\endgroup$ Feb 8, 2022 at 13:21
  • $\begingroup$ @RavenclawPrefect Good point, I've amended my post. Yes the swapped squares need to be edgewise adjacent. $\endgroup$
    – egglog
    Feb 8, 2022 at 13:38

1 Answer 1

5
$\begingroup$

As a lower bound on $a$: Consider the pattern containing all squares below the diagonal of slope $-1$ on the square, and as many on the diagonal as we need to get a number of squares $k$ which is $0$ or $1$ mod $4$ (arranged symmetrically about the center of the square, for the sake of this argument - this can always be done).

Choose coordinates so that the center of the square is $(0,0)$. Then the center of mass of any symmetric pattern is $(0,0)$, while the center of mass of our chosen pattern is $(-1,-1)\cdot\frac{n^3-n}{12k}$. Since every move can bring the sum of the coordinates of the center of mass up by at most $0.5$, getting the pattern symmetric takes at least $\frac{n^3-n}6 = {n+1\choose 3}$ steps. This is attained by the example in the post.

As a trivial upper bound, moving any square to any other square takes at most $2n-1$ steps, and at most $n^2/2$ squares would need to be moved, so it can't take more than $n^3-\frac{n^2}2$ steps in total. Thus $a$ grows cubically. (I suspect the true value of $a$ is much closer to the lower bound here, and I wouldn't be surprised if it were exact.)

$\endgroup$
5
  • $\begingroup$ Cool trick using the centre of mass to simplify things, how did you get $\frac{n^3 - n}{12k}$? $\endgroup$
    – egglog
    Feb 8, 2022 at 14:07
  • $\begingroup$ Actually, my original calculation was slightly off - I've edited the post to clarify that the extra squares on the diagonal should be positioned symmetrically. I think the center of mass is actually a sort of indirect way to get at what we care about, which is the sum of the sums of the coordinates of our cells. This is $0$ for any extra cells we put on the main diagonal, $-1/2$ for $n-1$ of the squares, $-2/2$ for $n-2$ of the squares, ... and $(1-n)/2$ for one square in the corner. It's straightforward to check that the sum of these products is half the $(n-1)$st tetrahedral number. $\endgroup$ Feb 9, 2022 at 20:59
  • $\begingroup$ Why you choose to study the case "the pattern containing all squares below the diagonal of slope −1 on the square"? It is not the worst case scenario possible. A typical strategy to solve this problem is to move all the little squares to the center in such a way they are symmetrical. In this case the worst scenario is choosing $k$ squares that are the most far from the center, so the most near to one of the corners of the big square. Do you agree with this or am I missing something? When I'll have some time I'll try to make a complete answer to explain all my perplexities $\endgroup$
    – Gabrielek
    Feb 16, 2022 at 9:12
  • $\begingroup$ @Gabrielek I didn't claim the pattern was the worst possible, only that it is within a constant factor of the upper bound I proved. If you think you have a configuration that requires more steps, feel free to describe it! I don't yet know of any configurations that take more steps than the diagonal arrangement I described. $\endgroup$ Feb 17, 2022 at 2:00
  • $\begingroup$ Maybe I misunderstood your claim when I read it the first time. You are taking the whole square almost half filled under one of the two diagonals, am I right? In this case I agree with your answer and I apologize for my comment $\endgroup$
    – Gabrielek
    Feb 17, 2022 at 10:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .