Let $G$ be an $n \times n$ grid and color each cell. Suppose that no row contains two cells of the same color. Show that the cells can be permuted within each row such that no column contains two cells of the same color. (Formally: show that there exist $n$ permutations $p_1, p_2, \cdots, p_n$ such that $p_i$ is a permutation of row $i$, and the composition $p = p_1 \circ p_2 \circ \cdots \circ p_n$, when applied to $G$, yields a new grid in which no column contains two cells of the same color.)

  • $\begingroup$ This means each row contains exactly one cell of each color. This means you can rearange them in any order you want. Just imagine a legal configuration, and by my previous sentence you can get there. $\endgroup$ – Espace' etale May 5 '20 at 11:18
  • $\begingroup$ how do you know the legal configuration exists, though? ex. n=3 and our grid is filled with colors [[123][124][125]] (left-to-right, top-to-bottom). A greedy algorithm would put 3,4,5 in the first column and then be stuck with the remaining 1s and 2s in the other two columns $\endgroup$ – atenao May 5 '20 at 12:50

Update: As pointed out in the comments, this doesn't work. In fact any strategy of reassigning colors will fail for some grids.

We use the notation $[n]$ for $\{1, 2, \ldots, n\}$. We will denote the colors in the grid as $1, 2, \ldots, m$ where $m\geq n$. If $m=n$, it is easy to construct such a rearrangement: Rearrange the cells of the $i$th row to $(i, i+1, \ldots, n, 1, 2, \ldots, i-1)$.

We will construct a function $f:[m]\rightarrow [n]$ such that $f$ is surjective on each row (i.e., according to the remapped color scheme, the cells in each row will have colors $[n]$). Let the colors in the first row be denoted by $1, 2, \ldots, n$ and set $f(i) = i$ for $i \in [n]$. We will extend the domain of $f$ to all of $[m]$ by working row by row. Suppose we have extended $f$ to the colors appearing in the first $i$ rows. For each color $c_1, \ldots, c_k$ in the $i+1$st row not appearing in the first $i$ rows, arbitrarily assign $f(c_j)$ to one of $[n]$ such that each cell receives a different color. That this can be done follows because each color in the $i+1$st row is distinct.

Applying $f$, we now have a grid with $n$ colors, so we can solve the problem. It is clear that the same permutations will work for the original grid.

  • $\begingroup$ if n=5 and we encounter the color 6 in some row, we try to reassign it to 4 or something. but we still need to check that 6 and 4 never appear together in subsequent rows $\endgroup$ – atenao May 6 '20 at 7:36
  • $\begingroup$ You are right - I've updated the post to indicate that this doesn't work $\endgroup$ – Anand May 6 '20 at 14:43

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.