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$
  • $\begingroup$ Can I use $mn$ pieces, and $x=0$ moves? :-) $\endgroup$ – Jaap Scherphuis Sep 27 '19 at 12:10
  • $\begingroup$ @JaapScherphuis sure, that a trivial solution, but I'm more interested in general solutions. $\endgroup$ – Steven Sep 27 '19 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$ – Jaap Scherphuis Sep 27 '19 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$ – antkam Sep 27 '19 at 13:17
  • $\begingroup$ Is symmetry along a diagonal for square boards allowed? $\endgroup$ – Connor Harris Sep 27 '19 at 13:53
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$
  • $\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$ – Steven Sep 30 '19 at 12:56
  • $\begingroup$ @StevenFontaine: Thanks for letting me know. I updated my answer. $\endgroup$ – Jaap Scherphuis Sep 30 '19 at 13:21

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.