5
$\begingroup$

You are given a $3\times n$ checkerboard, covered with $n$ red, $n$ white, and $n$ blue checkers. Call a board patriotic if every column has a red, white and blue checker. You want to make the given board patriotic. To do this, you are allowed to do a series of moves, where a move consists of changing the places of two checkers which are in the same row. Can you succeed?

In the case that you can, you should demonstrate why, and in the case you can't, you should give an example of a starting board which can't achieve patriotism.

enter image description here

Here are some examples when $n=7$. On the left is a starting position which is very unpatriotic: none of the columns feature all three colors. It can, however, be rearranged to the patriotic board on the right.

$\endgroup$
1
$\begingroup$

It's always possible, using a reasonably simple approach:

Choose a colour (say white), and switch counters so that each column has exactly one of that colour present. Now choose a second colour (say blue), and again switch counters so that each column only has one of that colour present, but without disturbing the first-chosen colour counters. This is always possible because in a column where there are two blue counters, you can choose which of them to switch to a column with no blue counter so that you do not disturb the white counter in that column. Having done that, your grid is fully patriotic - the final space in each column is filled with the third colour automatically.

I note that, conveniently, this puzzle is patriotic for many nations. Yay Iceland!

$\endgroup$
  • $\begingroup$ I'm not convinced that, as you place the blue counters, you never run out of room. In fact, suppose, when $n=3$, we start with whites on the diagonal, in positions (1,1), (2,2) and (3,3). We then place our first two blues in positions (1,2) and (2,1). Now the last blue can't be placed unless an earlier blue is moved. So, you need to specify, as you place the blues, how to choose their locations to avoid running out of space, or how to shift around blues when this happens. $\endgroup$ – Mike Earnest Apr 22 '15 at 22:21
  • $\begingroup$ For each column with two blues in it, you switch one of them into a column with no blues in it. You choose which one (if necessary) to avoid touching the white in that target column. I'm not sure where "placing" counters comes in - I was only concerned with switching them on a board where all the counters have already been (randomly) placed. $\endgroup$ – Joffan Apr 22 '15 at 22:33
  • $\begingroup$ I see now! Elegant! Vive la France! $\endgroup$ – Mike Earnest Apr 22 '15 at 22:45
  • $\begingroup$ You'd need to add a minor gimmick to extend to four colours, and a pigeonhole-based variation on that gimmick should allow extension to any number. $\endgroup$ – Joffan Apr 22 '15 at 22:52
6
$\begingroup$

Yes, it can always done for any $n$. Moreover, this also holds when the number of row and colors $3$ is replaced by any number $r$.

Proof:

It suffices to show that one can pick one checker out of each row so that their colors are distinct. Then, one can swap those checkers into the first column and recurse on the subproblem of the remaining columns with $n-1$. We need to a find a one-to-one matching between rows and colors so that each row contains at least one checker of that color. Apply Hall's Marriage Theorem. In any $k$ rows, there $kn$ checkers and so at least $k$ colors of checkers appear (since there's $n$ per color). So, the theorem's conditions are satisfied and a matching exists.

$\endgroup$
  • $\begingroup$ This is a very cool generalization! In a way it's killing a cockroach with a cannonball, and the original problem can be done without this theorem $\endgroup$ – Mike Earnest Apr 21 '15 at 22:52

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.