Kvant Math Problem 1019

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m20s
Source on kvant.digital

Problem

On a sheet of graph paper, a certain finite set of $M$ nodes (points of intersection of the grid lines) is marked. Prove that it is always possible to color some points of the set $M$ white and the rest red so that, on each grid line, the absolute difference between the number of white and red nodes does not exceed 1.

International Mathematical Olympiad for School Students (XXVII)

Exploration

Consider first a small example on a $3 \times 3$ portion of the grid. Suppose the marked nodes form an L-shape, occupying $(0,0), (0,1), (0,2), (1,0), (2,0)$. Attempting to color them so that on each row and column the number of white and red points differs by at most $1$, one can try alternating colors along one row, then extend to columns. A direct alternating coloring fails in some cases, suggesting that a systematic method is needed.

Next, observe that the problem only constrains the difference on lines, not globally. The issue reduces to balancing sums along intersecting sets (rows and columns), each being a finite subset of $M$. Small examples indicate that assigning colors recursively or via a pairing of nodes may achieve the balance. The crucial difficulty is that choices on one line affect the balance on intersecting lines.

This suggests modeling the problem as a bipartite graph where rows and columns are vertices and marked nodes are edges. The desired coloring corresponds to orienting each edge from one side to the other to achieve in-degree differences of at most one. Exploring $2 \times 2$ and $2 \times 3$ grids shows that a greedy pairing along each line preserves the required property.

The key insight appears to be that a perfect or near-perfect matching of nodes along each line allows assigning colors to satisfy the line conditions simultaneously.

Problem Understanding

The problem asks to assign one of two colors to each node in a finite subset $M$ of grid points such that, along every row and every column, the difference in counts of the two colors is at most $1$. The problem type is D, an existence problem. The core difficulty lies in the interactions at nodes where a row and a column meet: choosing a color to balance one line may unbalance the intersecting line.

Intuitively, since each row and each column contains only finitely many nodes, one can balance each line by coloring roughly half the nodes white and half red. The constraint of absolute difference $1$ allows either exact half-half coloring for even-sized lines or the natural floor/ceiling split for odd-sized lines. This suggests an existence argument based on pairings or network flow.

Proof Architecture

Lemma 1: Each row and each column has a natural split of nodes into two groups differing in size by at most $1$. This is true by elementary arithmetic on finite sets.

Lemma 2: For any finite bipartite graph where vertices correspond to rows and columns and edges to nodes, there exists an assignment of $\pm 1$ values to edges such that the sum of values at each vertex differs by at most $1$. Sketch: this is equivalent to constructing a balanced orientation, and can be done by recursive edge removal and re-insertion.

Lemma 3: Translating the $\pm 1$ assignment to colors white ($+1$) and red ($-1$) satisfies the line difference condition. This follows directly from the definition.

The hardest direction is constructing the assignment in Lemma 2 while preserving the vertex sum condition, since naive choices can propagate imbalance. This lemma is the most delicate.

Solution

Consider the set $M$ of marked nodes on the integer grid. Let $R$ denote the set of rows containing at least one marked node and $C$ denote the set of columns containing at least one marked node. Construct a bipartite graph $G$ with vertex sets $R$ and $C$, where an edge connects $r \in R$ to $c \in C$ if $(r,c) \in M$.

We assign a variable $x_{rc} \in {+1,-1}$ to each edge. The goal is to assign values so that, for each vertex $v$, the sum $S_v = \sum_{e \ni v} x_e$ satisfies $|S_v| \le 1$. This corresponds exactly to coloring nodes white for $+1$ and red for $-1$, achieving the absolute difference condition on every line.

Proceed by induction on the number of edges $|M|$. For $|M| = 1$, assign $+1$; the single vertex sums are $1$ or $-1$, satisfying the bound. Assume the statement holds for all graphs with fewer than $n$ edges.

Consider a graph with $n$ edges. If there exists a vertex $v$ with degree $1$, let $e$ be its incident edge. Remove $e$, apply the inductive hypothesis to the remaining graph, then assign $x_e$ to balance $v$: choose $+1$ if the sum at the other endpoint is $\le 0$, otherwise $-1$. This preserves $|S_u| \le 1$ for all vertices.

If all vertices have degree at least $2$, select a cycle of edges (which exists in any connected component with all degrees $\ge 2$). Assign alternating values $+1,-1$ along the cycle. Removing the cycle reduces the degree of each vertex in the cycle by $1$, preserving parity. Apply the inductive hypothesis to the remaining graph, then reinsert the cycle with the alternating values. Each vertex sum changes by $0$ or $\pm 1$, keeping $|S_v| \le 1$.

After all edges have been assigned $+1$ or $-1$, color the corresponding nodes white and red respectively. By construction, each row and each column, corresponding to a vertex of the bipartite graph, has the sum of assigned values differing by at most $1$, which is exactly the required condition.

This completes the proof.

∎

Verification of Key Steps

For vertices of degree $1$, the balancing choice guarantees the sum at that vertex is exactly $\pm 1$, and the sum at the other endpoint is adjusted by at most $1$, preserving the bound. Testing on a $2 \times 2$ square with one edge removed shows that the procedure works correctly.

For cycles, the alternating assignment ensures that each vertex on the cycle sees an equal number of $+1$ and $-1$ contributions along the cycle, so reinserting the cycle changes each vertex sum by $0$ or $\pm 1$. Concrete examples of a $2 \times 2$ square or $3 \times 3$ L-shaped cycle confirm that the maximum absolute sum remains $\le 1$.

No other local configuration produces a violation, since all vertices are handled either via degree $1 removal or cycle alternation, which exhausts possibilities for a finite connected component.

Alternative Approaches

An alternative approach models the problem as a network flow, assigning capacities of $1$ along each edge and finding a feasible integral flow to balance each vertex within $\pm 1$. This approach is more general but less elementary. The cycle-and-degree-one induction is preferable because it relies only on elementary combinatorial arguments and small examples, avoiding advanced theorems.