IMO 1986 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + PASS
Solve time: 8m02s

Problem

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$?

Exploration

A first attempt to force balance by treating each vertical or horizontal line independently fails because every point influences two constraints simultaneously, one vertical and one horizontal. Any method that assigns colors line by line immediately breaks compatibility when a point belongs to two different lines whose decisions disagree.

Testing small configurations confirms the obstruction is not local. A single point or two points are trivial. A $2\times 2$ full grid admits many valid colorings, for instance alternating colors. A $2\times 3$ rectangle also admits a solution, but attempting to enforce balance column by column while fixing rows shows that local adjustments propagate. This indicates that any correct argument must control all lines at once through a global structure rather than sequential balancing.

Reformulating the problem as a signed incidence system shows that each point behaves like an edge between its $x$-coordinate and $y$-coordinate. This converts the problem into assigning signs to edges of a bipartite multigraph so that every vertex sees total incident sum in ${-1,0,1}$. This reformulation avoids the earlier failed pairing idea because it keeps track of how every point contributes simultaneously to exactly two constraints.

The main structural question becomes whether every finite bipartite graph admits such a bounded imbalance edge signing. Small graphs confirm plausibility: paths and cycles admit alternating sign patterns with perfect cancellation at internal vertices. The difficulty lies only in ensuring a global decomposition into such structures.

Problem Understanding

Each point $(x,y)$ corresponds to an edge between a vertex $x$ on the left side and a vertex $y$ on the right side of a bipartite graph. Coloring a point red or white is equivalent to assigning a value $-1$ or $+1$ to that edge.

For a fixed $x$-coordinate, the vertical line condition requires that the sum of assigned values on edges incident to the vertex $x$ lies in ${-1,0,1}$. The same condition holds for each $y$-vertex.

The task is therefore to assign signs to edges so that every vertex in the bipartite graph has incident sum of absolute value at most $1$.

Key Observations

A cycle in a graph admits an alternating $+1,-1$ assignment that produces zero net contribution at every vertex in the cycle. A path admits an alternating assignment that produces cancellation at all internal vertices, leaving only the endpoints contributing $\pm 1$.

If the entire edge set can be decomposed into paths and cycles, then cycles contribute nothing to vertex sums, while paths contribute only at endpoints. The remaining problem becomes controlling how often a vertex appears as an endpoint in this decomposition.

A standard graph-theoretic reduction shows that endpoint imbalance can be controlled by first pairing vertices of odd degree inside each connected component, artificially making all degrees even, and then using an Euler circuit to induce a structured traversal of all edges.

Solution

Each point $(x,y)$ is identified with an edge joining the vertex $x$ on the left part of a bipartite graph to the vertex $y$ on the right part. Let each edge receive a value $+1$ or $-1$, corresponding to the two colors.

For a vertex $v$, define its imbalance as the sum of values on edges incident to $v$. The requirement is that every vertex has imbalance in ${-1,0,1}$.

The construction is carried out separately on each connected component of the bipartite graph.

In a fixed connected component, consider the set of vertices of odd degree. These vertices are even in number because the sum of all degrees in a graph is even. Pair the odd-degree vertices arbitrarily within the component and, for each pair, add a temporary edge joining them. After this modification, every vertex in the resulting multigraph has even degree.

An Euler circuit exists in every connected graph in which all vertex degrees are even. Take an Euler circuit in the modified multigraph. Traverse this circuit and orient every edge in the direction of travel along the circuit. Assign value $+1$ to edges traversed in the forward direction of the circuit and $-1$ to edges traversed in the reverse direction of a fixed traversal orientation, equivalently interpret consecutive edges along the circuit as alternating $+1,-1,+1,-1$.

This produces a signing in which, at every vertex of the modified graph, the contributions of incident edges cancel in pairs because each entry into the vertex is matched with an exit along the Euler circuit. Therefore every vertex has imbalance $0$ in the modified graph.

Now remove the temporary edges. Removing an edge changes the imbalance of its two endpoints by at most $1$ in absolute value, since that edge contributed either $+1$ or $-1$ to each endpoint before deletion. Each vertex was incident to at most one temporary edge because the temporary edges form a matching on the odd-degree vertices. Therefore each vertex loses at most one contribution in magnitude.

Consequently, in the original graph, every vertex has imbalance in ${-1,0,1}$.

Translating back to the plane, the sum on each vertical line and each horizontal line equals the imbalance of the corresponding vertex, so every such line has difference between white and red points at most $1$.

This completes the construction.

Verification of Key Steps

The reformulation into a bipartite graph is exact because each point contributes to exactly one vertical and one horizontal line, hence corresponds to exactly one edge incident to exactly two vertices.

The pairing of odd-degree vertices is always possible because every finite graph has an even number of odd-degree vertices in each connected component, a consequence of the handshake lemma applied componentwise.

The existence of an Euler circuit after adding a perfect matching on odd-degree vertices follows from the characterization of Eulerian graphs as connected graphs with all vertices of even degree.

Along an Euler circuit, every time a vertex is entered, it is also exited, so incident edges can be paired consecutively along the traversal, ensuring that their signed contributions cancel at that vertex.

Each vertex is incident to at most one added temporary edge because those edges form a matching, so deletion alters the imbalance at each vertex by at most one unit. This guarantees the final bound of absolute value at most $1$.

Alternative Approaches

One alternative formulation uses linear algebra over the incidence matrix of the bipartite graph, viewing the problem as constructing a ${-1,1}$ vector whose image under the vertex-edge incidence map lies in the cube ${-1,0,1}^{V}$. This can be solved by decomposing the matrix into circulations corresponding to cycles and paths.

Another approach constructs a flow on a directed version of the incidence graph and uses integrality of flows to guarantee a solution with bounded vertex excess, again yielding the same $\pm 1$ assignment after interpreting flow directions as colors.