# $n \times n$ grid, each row contains n distinct colors. Permute the cells within each row such that columns contain n distinct colors

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.)

• 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. – Espace' etale May 5 '20 at 11:18
• 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 – atenao May 5 '20 at 12:50

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.