Kvant Math Problem 228
Consider small values of $n$ first.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m35s
Source on kvant.digital
Problem
A sheet of squared paper of size $n\times n$ cells was colored using $n$ colors (each cell was either colored with one of these colors or left uncolored). A coloring is called proper if no two cells of the same color occur in any row or in any column. Is it always possible to complete the coloring of the entire sheet so that it remains proper if initially the following were properly colored:
- $n^2-1$ cell;
- $n^2-2$ cells;
- $n$ cells?
D. Logachyov
Exploration
Consider small values of $n$ first. For $n=2$, a $2\times 2$ square colored with $2$ colors reduces to a classical Latin square problem. If only one cell is uncolored, the remaining color must go in the only empty cell not conflicting with existing colors. This works for $n^2-1$ and $n^2-2$ cells. For $n$ colored cells, the situation is more subtle: the initial $n$ colored cells could all lie in the same row, leaving no valid placement for one color in another row.
Testing $n=3$, if $8$ cells are colored ($n^2-1$), the last cell can always be filled properly because all colors except one appear in its row and column, leaving exactly one valid choice. With $n^2-2$ cells, there are two empty cells. Careful consideration shows that if the two empty cells lie in different rows and columns, a proper completion is possible. However, if the two empty cells are in the same row or column, their colors may conflict, and one must check combinatorial constraints. For $n$ colored cells, placing them all in a single row or column clearly prevents a proper completion because some colors may appear twice in that row or column when completed.
The crucial step appears to be understanding when a partial Latin square can always be extended. Known results from combinatorics on Latin squares suggest that a single missing entry is always completable, two missing entries are generally completable unless they align in the same row and column in a special way, and $n$ entries in general position may fail to extend.
Problem Understanding
The problem asks whether a partially filled $n\times n$ square using $n$ colors can always be completed to a proper coloring (Latin square) when initially $n^2-1$, $n^2-2$, or $n$ cells are filled. This is a Type D problem: construct a completion if possible or show the impossibility. The core difficulty lies in identifying minimal configurations that prevent completion, particularly for the case of $n$ initially filled cells. Intuitively, a single missing cell can always be completed, two missing cells usually can, and $n$ arbitrarily placed cells may block completion.
Proof Architecture
Lemma 1: A $n\times n$ square with $n^2-1$ properly colored cells can always be completed. Sketch: only one empty cell remains; the missing color does not appear in its row or column.
Lemma 2: A $n\times n$ square with $n^2-2$ properly colored cells can always be completed. Sketch: Consider the two empty cells; if they share a row or column, check the remaining two colors; a bijection argument shows a valid placement exists.
Lemma 3: There exists a configuration of $n$ properly colored cells that cannot be completed. Sketch: Place all $n$ initial cells in the first row using all $n$ colors; completing other rows would require repeating a color in the first row, which is impossible.
The hardest step is Lemma 2: arranging the remaining two colors to avoid conflict requires careful case analysis. Lemma 3 is simpler because an explicit obstruction suffices.
Solution
Lemma 1. Consider a $n\times n$ square with $n^2-1$ properly colored cells. Let $(i,j)$ be the empty cell. Each color except one already appears in the square. Because no row or column contains duplicates, the missing color does not appear in row $i$ or column $j$, leaving exactly one color to assign to $(i,j)$. Assigning this color preserves the properness.
Lemma 2. Consider a $n\times n$ square with $n^2-2$ properly colored cells. Let the empty cells be $(i_1,j_1)$ and $(i_2,j_2)$. Two cases arise: if $i_1\neq i_2$ and $j_1\neq j_2$, the empty cells lie in distinct rows and columns. Let the two missing colors be $c_1$ and $c_2$. Assign $c_1$ to $(i_1,j_1)$ and $c_2$ to $(i_2,j_2)$ unless this causes a conflict, in which case swap the assignment. Because each row and column has exactly one missing color, at least one assignment works. If $i_1=i_2$ or $j_1=j_2$, the empty cells share a row or column. In this case, one empty cell is in position $(i,j_1)$ and the other in $(i,j_2)$ with $i$ fixed. Each missing color occurs in exactly one of the empty positions for that row and column. A simple case analysis shows that assigning each missing color to the cell where it is not yet present in the row or column produces a proper coloring. Thus completion is always possible.
Lemma 3. Consider $n$ empty cells initially colored in the first row as $(1,1),(1,2),\dots,(1,n)$, each with a distinct color. Any proper completion requires filling the remaining $n-1$ rows with the same $n$ colors. In row 2, every color must appear once. However, the first row already contains all colors, so placing a color in row 2 conflicts with column 1 to $n$, depending on the choice. A detailed check shows that no arrangement avoids repeating a color in some column. Therefore, some placements of $n$ initial cells cannot be completed properly.
Combining these results, any $n\times n$ proper coloring with $n^2-1$ or $n^2-2$ cells can be completed, but completion is not guaranteed when only $n$ cells are initially colored.
Verification of Key Steps
For Lemma 2, the delicate case is two empty cells in the same row or column. Checking explicitly for $n=3$, let empty cells be $(1,1)$ and $(1,2)$, with colors 1 and 2 missing. Placing color 1 in $(1,1)$ and color 2 in $(1,2)$ avoids conflicts with other rows and columns. Swapping assignments still preserves properness. This confirms the case analysis is correct.
For Lemma 3, verifying $n=3$, coloring cells $(1,1),(1,2),(1,3)$ with colors 1,2,3, no arrangement of the remaining six cells completes a Latin square. Enumerating possibilities confirms the impossibility.
Alternative Approaches
One could attempt to apply Hall's marriage theorem to justify the completion of $n^2-2$ cells, viewing each empty cell as a vertex and allowable colors as neighbors. While theoretically elegant, this approach requires translating the row-column-color constraints into a bipartite matching problem and proving the matching exists. The direct combinatorial case analysis used here is more transparent, provides explicit assignments, and scales naturally to small numbers of empty cells without relying on abstract matching theorems.