5
$\begingroup$

Suppose there are $M$ different colors of ball and you have $N$ of each kind. You arrange all of the balls in an arbitrary linear order. Is it always possible to find a permutation of order 2 such that no ball shares a color with its neighbor?

(Note: a permutation of order 2 is a permutation which is its own inverse.)

If you only have one color $(M=1)$, then excluding the trivial one-ball case, it's impossible. If you have two colors $(M=2)$, it's always possible: supposing the colors are black and white, just swap every black ball in an odd-numbered position with a white ball in an even-numbered position.

The case for $M>2$ colors seems tricky to me, because the available moves (permutation) and success condition (no same-color neighbors) seem incomparable. I have tried extending the above $M=2$ strategy to greater numbers of colors without much success (e.g. considering index mod $M$, or trying to interleave pairs of colors.) I have also tried to represent the list of colored balls as integers mod $M$, or even the differences between neighboring balls as integers mod $M$; then, swaps affect the difference list in a particular way.

I have tried representing the list of balls as a matrix $A$, where $A_{i,j}$ is the number of balls of color $i$ in a position that is equal to $j\pmod{M}$; then, the sums of the rows and columns are all $N$, and one special way of achieving the desired condition is if the colors are all interleaved so that the matrix becomes a multiple of the identity matrix.

$\endgroup$
  • $\begingroup$ Is it always possible to find a permutation of order 2 such that no ball shares a color with its neighbor? in the last part you listed a matrix of all solutions, you want all permutations or just a valid one ? $\endgroup$ – Abr001am Mar 19 '18 at 0:27
  • $\begingroup$ @Abra001 Oops my example was incorrect; deleted. I would like to know if for every $M>2$ and $N$ and arrangement of balls, it is possible to find a permutation of order 2 such that no ball shares a color with its neighbor. $\endgroup$ – user326210 Mar 19 '18 at 3:51
  • 1
    $\begingroup$ Intuitively, it must be possible because $M \gt 2$ "has got to be" easier than $M=2$. For even $M$ it is easy-just make every odd color black, every even color white and apply your proof for $M=2$ $\endgroup$ – Ross Millikan Mar 19 '18 at 4:04
  • $\begingroup$ There is something here i couldn't wrap up, you said "is it possible to find a permutation of order 2", from here you see that every permutation can be constructed from two deterministic ones of order-2 , or i may be missing something ? $\endgroup$ – Abr001am Mar 19 '18 at 18:52
  • $\begingroup$ @Abra001. You want exactly one list permutation of order 2 that exchanges everything. For example, if you have ABCD, you can use a single order 2 permutation to make it BADC, but you can't use a single order 2 permutation to make BDAC. That BDAC permutation isn't order 2 because applying it twice produces DCBA, not the original list. $\endgroup$ – user326210 Mar 19 '18 at 18:58

Your Answer

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

Browse other questions tagged or ask your own question.