3
$\begingroup$

You can try this with pencil and paper, or make it a physical puzzle you can try out with your kids if you have one of those large 3x6 egg cartons laying around.

Imagine you have 3 rows of 6 spots. Fill the first row with 6 red colored eggs, the second with 6 green colored eggs, and the last with 6 blue colored eggs.

You are allowed to make as many moves as you like by following these steps:

  1. Choose two rows and two columns.
  2. At the intersection is four eggs: swap the top two eggs with the bottom two eggs.

First part of the puzzle:
Starting from this state

[RRRRRR]  
[GGGGGG]  
[BBBBBB]

can you reach this diagonally striped state?

[RGBRGB]  
[GBRGBR]  
[BRGBRG]

If not, prove why.

Second part:
Can you reach this state?

[RRRRRB]  
[GGGGGG]  
[BBBBBR]

If not, prove why.

I was able to solve the first part, and am stuck on the second part.
I assume it is some kind of parity argument, like most of these types of puzzles, but I cannot figure out how to demonstrate it.

I've filled a few sheets of paper doodling move sequences, and haven't spotted the "invariant" or pattern yet.
Help?

$\endgroup$

1 Answer 1

3
$\begingroup$

Basically, at every moment, each column corresponds to a permutation in $S_3$, the symmetric group of three elements.

The elements of $S_3$ are divided into two classes: the even permutations and the odd permutations. Any swap of two elements changes the parity.

Now simply consider the number of even permutations in all six columns. Each operation changes the parity of two columns, hence the parity of the number of even permutations never changes.

Originally there are $6$ even permutations (all being identity) and the goal has $5$ even permutations. Hence it's impossible.

$\endgroup$
1
  • $\begingroup$ ha, the parity of the parity!! No wonder I kept seeing "something", but couldn't tie it together. $\endgroup$ Mar 8, 2021 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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