3
$\begingroup$

Given an $n\times m$ grid and $x$ elements on the grid, what's the maximum number of moves required to arrange the elements, for all possible starting permutations of the elements, into a symmetric pattern, given that the number of moves for each permutation is the minimum possible number of moves?

There's a fair bit to breakdown here, so let's work with an example. To explain what I mean by a "move", let's say the grid is an $m\times n$ chessboard, and the elements within that grid are queen chess pieces. However, these queens are superpowered. Instead of their normal limits in chess, these queen pieces can move to any other free space*, even if it requires passing through other queens.

As for symmetry, any form of rotational or axial symmetry is valid.

So, given our $n\times m$ chessboard and $x$ super queens placed on the chessboard, assuming each set of moves is the minimum possible number for the given arrangement of super queens, what is the maximum number of moves required to arrange any initial permutation of super queens into a pattern which is symmetrical?

*This is an important distinction. Typically, "super queens" are still limited to 8 directions of movement. However, I'm specifically asking about "queens" that can move to any free space on the board.

$\endgroup$
5
  • $\begingroup$ Can I use $mn$ pieces, and $x=0$ moves? :-) $\endgroup$ Commented Sep 27, 2019 at 12:10
  • $\begingroup$ @JaapScherphuis sure, that a trivial solution, but I'm more interested in general solutions. $\endgroup$ Commented Sep 27, 2019 at 12:23
  • 1
    $\begingroup$ Well, you asked for the largest number of pieces that works, and $mn$ is that largest number (as it works for any $x$). I think what you really intended to ask was the smallest number of pieces that didn't work, and a strategy for that number minus one. $\endgroup$ Commented Sep 27, 2019 at 12:55
  • $\begingroup$ haha @JaapScherphuis is right about your wording issue. :) It's more like the following, right? Let $k=$ no. of elements, then there is a number $x=f(k)$ s.t. for any initial arrangement of $k$ elements at most $x$ moves are needed to "symmetrize". clearly $f(0)=f(mn)=0$. then you might be asking, for a given $x$, what is max value of $k$ s.t. $\forall j \le k: f(j) \le x$. if $f()$ is unimodal then this would ask for the "rising" side of the "hill", whereas if $f()$ is multi-modal then this would ask for the "rising" side of the first "hill" that is taller than $x$. $\endgroup$ Commented Sep 27, 2019 at 13:17
  • $\begingroup$ Is symmetry along a diagonal for square boards allowed? $\endgroup$ Commented Sep 27, 2019 at 13:53

1 Answer 1

Reset to default
3
$\begingroup$

Here are some quick thoughts on the problem.

We are given an $n\times m$ board, and a number of pieces $x$.
It is fairly easy to see that we can move half the pieces to match the other half with respect to any 2-fold symmetry. If any pieces lie on the axis of reflection or rotation, that only makes it easier as we don't need to move as many pieces. This means that $M=\lceil\frac{x}{2}\rceil$ moves is always sufficient.

Are all those moves necessary? If all the pieces happened to lie in one quarter of a rectangular board (and not on any axis of symmetry), then no two pieces form a symmetric pair, and that number of moves is definitely necessary - for every unmoved piece, another has to be moved to make a symmetric pair.

So if $x \le \lfloor\frac{m}{2}\rfloor\lfloor \frac{n}{2}\rfloor$ and $m \neq n$, then $M$ moves are not just sufficient but also sometimes necessary to make them symmetric.

If $m=n$ then we also have diagonal symmetry. If the $x$ pieces happen to lie in the triangle forming one eighth of the board (between a diagonal and a midline of the square), then they cannot be made symmetric in fewer than $M$ moves. So if $m=n$ and $x \le \lfloor \frac{n}{2} \rfloor (\lfloor \frac{n}{2} \rfloor -1)/2$ then $M$ moves are sufficient and sometimes necessary to make them symmetric.

For larger $x$ things seem to become more complicated. However they are arranged, there will be some pieces that form symmetric pairs or which lie on an axis of symmetry. This means that fewer than $M$ moves are necessary, but it is hard to work out the details, especially as there are several symmetries to consider.

When the $x$ is very large, then it becomes easier again. A board with $mn-x$ pieces is equivalent to a board with $x$ pieces (by replacing pieces by empty cells and vice versa). It is the middle ground where it gets difficult.

$\endgroup$
2
  • $\begingroup$ I edited the question to better reflect what I'm tryin to ask, but that involved changing what $x$ refers to. It's up to you if you want to reword the answer to reflect that. $\endgroup$ Commented Sep 30, 2019 at 12:56
  • $\begingroup$ @StevenFontaine: Thanks for letting me know. I updated my answer. $\endgroup$ Commented Sep 30, 2019 at 13:21

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.