Kvant Math Problem 950

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m39s
Source on kvant.digital

Problem

Twenty-five dwarfs are dividing garden plots in Flower City. Each plot is a square of $1\times1$, and all the plots together form a square of $5\times5$. Each dwarf is in a quarrel with no more than three other dwarfs. Prove that it is possible to allocate the plots so that no two dwarfs who are quarrelling have neighboring plots. (Plots are considered neighbors if they share a common side.)

S. V. Konyagin

All-Russian School Mathematics Olympiad (XI)

Exploration

The $25$ plots form the $5\times5$ grid graph. Two plots are adjacent when they share a side. We must assign one dwarf to each plot so that every pair of quarrelling dwarfs occupies nonadjacent plots.

The quarrel relation defines a graph $G$ on $25$ vertices. Every vertex has degree at most $3$.

The grid graph $H$ of the $5\times5$ board is bipartite. Coloring the board like a chessboard gives color classes of sizes $13$ and $12$. Every plot is adjacent only to plots of the opposite color. Hence any two plots of the same color are automatically nonadjacent.

If we could place one independent set of dwarfs on the $13$ squares of one color and all remaining dwarfs on the $12$ squares of the other color, then no quarrelling pair inside either color class would be adjacent. The only possible adjacent pairs would lie across the two color classes. Thus we need a partition of the dwarfs into sets of sizes $13$ and $12$ such that neither set contains a quarrelling pair.

This becomes a graph-theoretic question. Since the maximum degree of $G$ is at most $3$, perhaps $G$ is $2$-colorable with color classes differing in size by at most $1$. That is false in general because $G$ may contain odd cycles.

A natural theorem is Brooks' theorem: graphs of maximum degree $3$ are $4$-colorable unless they are $K_4$. Since $K_4$ is also $4$-colorable, every such graph is $4$-colorable. If the dwarfs are split into four independent color classes, then perhaps two classes can be merged to obtain $13$ vertices and the other two classes $12$ vertices.

Let the color classes have sizes $a,b,c,d$, with $a+b+c+d=25$. Every subset sum of these sizes corresponds to the size of a union of color classes. We need a subset sum equal to $12$ or $13$.

Is that always possible? Since every class is independent, obtaining such a subset sum would solve the problem.

Suppose no subset sum equals $12$ or $13$. Since the total is $25$, absence of $12$ is equivalent to absence of $13$. Order the sizes as $a\le b\le c\le d$.

Because $a+b+c+d=25$, we have $a\le6$. Consider subset sums generated greedily. If each size were at most one more than the sum of previous sizes, all integers up to $25$ would occur. Therefore some size must exceed one plus the sum of smaller ones. With total $25$, this severely restricts possibilities. Let us classify.

Set $s=a+b+c$. If $d\le s+1$, every integer from $0$ to $25$ is representable, hence $12$ appears. Therefore $d>s+1$, so $25=s+d>2s+1$, giving $s\le11$. Then $d\ge14$.

Now $a+b+c=s\le11$. If $c\le a+b+1$, then every integer from $0$ to $s$ is representable. Since $s\le11$, absence of $12$ causes no issue, but then $d\ge14$. We need to see whether such quadruples can exist. Let us continue. If also $b\le a+1$, then every integer from $0$ to $s$ is representable. Since $s=25-d\ge0$.

A more direct route: since $d\ge14$, the other three classes sum to at most $11$. By the same representability argument, all sums from $0$ to $11$ are obtainable from $a,b,c$. Then $12$ would fail only if $12-d<0$, which it is. We need a cleaner argument.

Try proving: for any four positive integers summing to $25$, some subset sums to $12$ or $13$. Let $d$ be largest.

If $d=13$, done. If $d\ge14$, then $a+b+c\le11$, and the complementary subset has sum at most $11$, so no subset containing $d$ can sum to $12$ or $13$. We need a subset of $a,b,c$. But their total is at most $11$, impossible. Hence such quadruples would be counterexamples. Example $(1,1,1,22)$ gives no subset sum $12$ or $13$.

So the subset-sum statement is false.

Need a different idea.

Maybe use equitable coloring. The Hajnal-Szemerédi theorem says every graph with maximum degree $3$ has an equitable $4$-coloring, meaning the four color classes differ in size by at most $1$. For $25$ vertices, the class sizes are $7,6,6,6$. Then taking two classes gives sizes $12$ or $13$. That is exactly what is needed.

This seems to be the intended route, but Hajnal-Szemerédi is far too advanced for a school olympiad. There must be an elementary argument for $\Delta\le3$.

Perhaps every graph with maximum degree $3$ admits a proper $4$-coloring with class sizes $7,6,6,6$. Let us derive it. Take a proper $4$-coloring minimizing the size of the largest class. Then class sizes differ by at most $1$. Indeed, if one class exceeds another by at least $2$, one can move a vertex through a Kempe-chain type argument because each vertex sees at most three colors among neighbors. There is a standard easy proof of equitable coloring for $\Delta=3$.

Let color classes be $C_1,C_2,C_3,C_4$. Choose a proper $4$-coloring with lexicographically minimal class sizes. Suppose $|C_1|-|C_4|\ge2$. Every vertex of $C_1$ must have neighbors in each of the other three colors, otherwise it could be recolored into a smaller class. Hence every vertex of $C_1$ has degree $3$.

Consider the directed graph on colors where $i\to j$ if some vertex of color $i$ lacks a neighbor of color $j$. Then recoloring chains produce a contradiction. This is the standard proof of equitable coloring for $\Delta<4$.

Need a cleaner olympiad proof. Let largest class $A$, smallest class $D$, with difference at least $2$. Define reachability by recoloring. Let $S$ be colors reachable from $D$. For a reachable color class, every vertex must have a neighbor in every reachable class, otherwise recoloring along a chain would move one vertex into $D$ and reduce imbalance. Counting edges between reachable classes yields contradiction because degree at most $3$ and there are at most four colors. Let's formulate.

Known proof of equitable coloring theorem for $\Delta=r-1$: every graph with max degree $r-1$ has equitable $r$-coloring. Here $r=4$. Use minimal coloring. Reachable set size $k$. Each vertex in reachable classes has at least $k-1$ neighbors within reachable classes. Vertices in largest reachable class have at least $k$ neighbors, impossible when $k=4$ and degree $\le3$. Then derive contradiction.

Let's write concise version. Once equitable 4-coloring obtained, sizes are $7,6,6,6$. Union of two color classes gives exactly $12$ or $13$. Place one union on black squares (13) and complement on white squares (12). Since each union is independent? Wait union of two color classes is not independent. Need partition into two independent sets. Mistake.

Need rethink. If color classes are four independent sets, union of two need not be independent. We need each side of board color class to contain no quarrelling pair, so each side must be independent in quarrel graph. Thus we need a 2-coloring of dwarfs graph, not 4-coloring.

Alternative: Board bipartition suggests partition dwarfs into two independent sets sizes 13 and12. That requires quarrel graph bipartite. Not given.

Different approach: Assign four color classes of dwarfs to four residue classes of board? The grid graph itself is 4-colorable by coordinates mod 2. Indeed color classes sizes are 9,6,6,4 on 5x5. Adjacent squares have different colors. If dwarfs graph is 4-colorable with class sizes fitting into these capacities, then map each dwarf color to one board color. Need capacities at least class sizes. Equitable coloring gives classes sizes at most 7, so they fit into 9,6,6,4? Largest class 7 doesn't fit into 6 or4. Need choose board 4-coloring sizes 9,6,6,4. Need graph coloring class sizes bounded by those capacities.

Need find intended graph homomorphism. Quarrel graph max degree 3 => 4-colorable. Board graph 5x5 also 4-colorable with color class sizes 9,6,6,4. If we can 4-color dwarfs so class sizes do not exceed corresponding capacities after ordering. Need show color classes sizes can be made at most 9,6,6,4. Equitable 4-coloring gives sizes 7,6,6,6. Sorted: 7,6,6,6. Capacities sorted: 9,6,6,4. Not fitting due one class 6 >4. But we can merge? Need assign.

Need instead color board with 4 colors sizes 7,6,6,6 maybe. Check 5x5 grid 4-coloring by parity gives 9,6,6,4. Another 4-coloring may have balanced classes. Need check. We need four independent sets of board graph capacities 7,6,6,6. Can 5x5 grid be partitioned into 4 independent sets of those sizes? Likely yes. Let's construct via 4-coloring then move some vertices. Need easier.

Maybe use equitable coloring on both graphs. Since max degree of board graph is 4 though. Need assign color classes.

Wait simpler: Use Hajnal-Szemerédi on board graph? Overkill.

Need map quarrel graph into board graph complement adjacency? Let's do graph coloring both with 4 colors size pattern 7,6,6,6. Then place dwarfs color i onto squares color i. Since adjacent board squares have different colors, dwarfs of same color never occupy adjacent squares. Quarrelling dwarfs have different colors, but could occupy adjacent squares. Mapping arbitrary within color classes doesn't prevent that. Need homomorphism from quarrel graph to board coloring? Let's think.

If dwarfs graph properly 4-colored and board graph properly 4-colored with same colors, then a quarrel edge joins different dwarf colors. Adjacent plots also join different board colors. That doesn't stop a quarrel edge from landing on adjacent plots.

Need reinterpret. We need inject vertices of quarrel graph into grid squares so every quarrel edge maps to nonadjacent squares. Equivalent embedding into complement of grid graph. Maybe use coloring of complement.

Observe board 4-coloring classes are independent in grid; thus any two squares of same color are nonadjacent. If all dwarfs of a given quarrel-color are placed on same board color class, then quarrelling dwarfs, having different quarrel-colors, may still be adjacent. Not enough.

Need another idea: Use graph coloring of quarrel graph with 4 colors and place each color class into one board color class of a proper 4-coloring of grid complement? Running low.

Maybe use theorem: max degree 3 graph is subgraph of 5x5 rook? Let's find simpler. Need construct placement on grid where no adjacent squares contain quarrelling dwarfs. Grid graph max degree 4. We need color squares with 4 colors so that each color class size at least? Actually if quarrel graph 4-colorable, place same color dwarfs on squares of same color. Since neighboring squares have different colors, same-color dwarfs are nonadjacent. But quarrel edges are between different colors, so still issue.

Wait if board coloring is such that squares of different colors are never adjacent? Impossible.

Need model differently. We need assign dwarfs to squares. Let conflict graph G. Let H be grid adjacency graph. Need bijection so edges of G map to nonedges of H. Equivalently embed G into complement of H. Complement of 5x5 grid has minimum degree 20. Maybe use graph embedding theorem: any 25-vertex graph with max degree 3 embeds into graph with minimum degree 20 via Sauer-Spencer since 2Δ(G)Δ(H)<n? Here complement degree min20. There is a simple greedy embedding: complement has min degree 20 > 25-1-3=21? Check.

Need olympiad likely uses Hall. Let's derive. We need place vertices one by one because each dwarf conflicts with ≤3 others. Number squares adjacent to already placed conflict-neighbors ≤4 each. Maybe greedy.

Order dwarfs arbitrarily. When placing a dwarf, avoid neighbors of plots occupied by quarrelling dwarfs. Each dwarf has at most 3 quarrelling predecessors, excluding at most 12 squares. If k-th step, remaining squares count maybe less than 13 near end. Greedy fails.

Use embedding theorem via Hall: Complement graph C of grid. Need show any graph G with Δ≤3 is subgraph of C. C has n=25, minimum degree 20. There is a theorem of Dirac: any graph with max degree ≤3 embeds into graph with min degree ≥21? Greedy works because 20 not enough.

Need find elegant: Use equitable 5-coloring? Maybe grid can be partitioned into 5 independent rows/columns.

Let's do embedding via Hall. Consider assigning dwarfs to squares. By theorem of Hajnal-Szemerédi? No.

Need finish. Maybe use known result: If Δ(G)+Δ(H)<n then G embeds into complement of H. Here Δ(G)=3, Δ(H)=4, n=25, sum=7<25. Sauer-Spencer theorem. There is an elementary greedy proof for this strong inequality. Let's use. We need prove existence.

Construct embedding of G into complement of H. Let f be maximal partial embedding. If some dwarf unplaced, use switching argument. Might be long.

Given olympiad, likely intended theorem simpler: Since 3+4<25. I'll craft proof of Sauer-Spencer special case. Need fit sections.

Let G=quarrel graph, H=grid graph. Suppose no embedding. Take maximal injective map f preserving edges of G into nonedges of H. One vertex u unembedded. For every free square x, some neighbor v of u already mapped to a square adjacent to x in H, else place u at x. Since deg(u)≤3 and each f(v) has ≤4 adjacent squares, at most 12 free squares blocked. But if unembedded count >12 we'd place. In maximal stage only few free squares. Hard.

Need concise. Maybe use standard theorem: Δ(G)Δ(H)< n/2 => pack. Here 12<12.5. Use Sauer-Spencer. I'll provide proof sketch? Need rigorous enough.

Given constraints, I'll do proof using Sauer-Spencer packing theorem specialized. Might be acceptable. Need prove theorem briefly. Hmm.

Exploration

Let $G$ be the graph whose vertices are the dwarfs, two vertices being joined when the corresponding dwarfs are quarrelling. Then $|V(G)|=25$ and $\Delta(G)\le 3$.

Let $H$ be the $5\times5$ grid graph. Its vertices are the plots, and two vertices are adjacent when the corresponding plots share a side. The maximum degree of $H$ is $4$.

The required allocation is exactly an injective map from the vertices of $G$ to the vertices of $H$ such that every edge of $G$ is mapped to a nonedge of $H$. In graph-theoretic language, we must embed $G$ into the complement $\overline H$.

A standard packing criterion states that two graphs on the same number $n$ of vertices pack whenever

$$2\Delta(G)\Delta(H)<n.$$

Here

$$2\Delta(G)\Delta(H)\le 2\cdot3\cdot4=24<25=n.$$

Thus the criterion applies immediately.

The only point requiring real work is the packing theorem. For this problem we need only the special case above. The delicate step is the switching argument showing that a maximal partial embedding can always be improved when $2\Delta(G)\Delta(H)<n$.

Problem Understanding

We have $25$ dwarfs and $25$ unit plots forming a $5\times5$ square. Each dwarf quarrels with at most three others. We must assign one dwarf to each plot so that no pair of quarrelling dwarfs occupies neighboring plots.

This is a Type B problem. We must prove that such an allocation always exists.

The core difficulty is that the pattern of quarrels is arbitrary. The only information available is the bound $3$ on the number of quarrels of each dwarf. The natural formulation is in terms of graph embeddings.

Proof Architecture

Let $G$ be the quarrel graph and $H$ the $5\times5$ grid graph.

Lemma 1. The desired allocation exists if and only if $G$ can be embedded into $\overline H$; this is just a translation of the condition on neighboring plots.

Lemma 2. If graphs $A$ and $B$ have the same number $n$ of vertices and satisfy $2\Delta(A)\Delta(B)<n$, then $A$ and $B$ pack, meaning that after a relabeling of vertices they have no common edge. The proof uses a maximal labeling and a switching argument.

Lemma 3. For the grid graph $H$, $\Delta(H)=4$, while for the quarrel graph $G$, $\Delta(G)\le3$. Hence

$$2\Delta(G)\Delta(H)\le24<25.$$

The hardest step is Lemma 2. The switching count is the place where a careless argument can miss a forbidden configuration.

Solution

Let $G$ be the graph whose vertices are the $25$ dwarfs. Two vertices of $G$ are joined when the corresponding dwarfs are quarrelling. By hypothesis,

$$\Delta(G)\le3.$$

Let $H$ be the graph whose vertices are the $25$ plots of the $5\times5$ board. Two vertices of $H$ are joined when the corresponding plots share a side. Every plot has at most four neighboring plots, hence

$$\Delta(H)=4.$$

An allocation of dwarfs to plots is a bijection between $V(G)$ and $V(H)$. Such an allocation is acceptable precisely when every edge of $G$ is sent to a pair of nonadjacent plots. Equivalently, after identifying the vertices of $G$ with the vertices of $H$ via the allocation, no edge of $G$ is also an edge of $H$.

Thus we must show that $G$ and $H$ can be labeled on the same $25$-element vertex set so that they have no common edge. In graph-theoretic language, we must show that $G$ and $H$ pack.

We use the following packing theorem of Sauer and Spencer.

Packing theorem. If graphs $A$ and $B$ on the same set of $n$ vertices satisfy

$$2\Delta(A)\Delta(B)<n,$$

then $A$ and $B$ pack.

For completeness, we prove the theorem.

Assume that a labeling of the vertices has been chosen so that the number of common edges of $A$ and $B$ is minimal. Suppose a common edge still exists; call it $xy$.

Choose a vertex $z$. Interchange the labels of $x$ and $z$. Since the original labeling was minimal, this interchange cannot decrease the number of common edges.

The only common edges whose status may change are those incident with $x$ or $z$. Since $xy$ is a common edge, destroying it must be compensated by creating at least one new common edge. Consequently, for every choice of $z$, there exists a vertex $u$ such that either

$$xu\in E(A)\quad\text{and}\quad zu\in E(B),$$

or

$$xu\in E(B)\quad\text{and}\quad zu\in E(A).$$

For a fixed $z$, the number of possible vertices $u$ of the first type is at most

$$\Delta(A)\Delta(B),$$

because $u$ must lie simultaneously in a neighborhood of a neighbor of $x$ in one graph and in a neighborhood of $z$ in the other graph. The same bound holds for the second type. Hence each vertex $z$ belongs to a set of size at most

$$2\Delta(A)\Delta(B)$$

that can prevent the interchange from improving the labeling.

Since

$$2\Delta(A)\Delta(B)<n,$$

there exists a vertex $z$ outside all these forbidden possibilities. For this vertex, interchanging $x$ and $z$ destroys the common edge $xy$ and creates no new common edge, contradicting the minimality of the labeling.

The contradiction shows that the minimal number of common edges is $0$. Therefore $A$ and $B$ pack. The theorem is proved.

Applying the theorem to $A=G$ and $B=H$, we obtain

$$2\Delta(G)\Delta(H)\le2\cdot3\cdot4=24<25.$$

Hence $G$ and $H$ pack.

Therefore there exists a bijection between dwarfs and plots such that no edge of $G$ corresponds to an edge of $H$. In other words, no two quarrelling dwarfs occupy neighboring plots.

This completes the proof.

∎

Verification of Key Steps

The translation into graph language is exact. An edge of the quarrel graph represents a pair that must not be placed on neighboring plots. An edge of the grid graph represents a neighboring pair of plots. The allocation is valid precisely when no edge of the quarrel graph coincides with an edge of the grid graph after the vertices are identified.

The numerical condition required by the packing theorem is

$$2\Delta(G)\Delta(H)<25.$$

Substituting the degree bounds gives

$$2\cdot3\cdot4=24,$$

which is strictly less than $25$. Equality would not suffice for the theorem, so the strict inequality is essential.

In the switching argument, the crucial point is that every interchange affecting a common edge must create a compensating common edge, otherwise the number of common edges would decrease. The count of possible compensating edges is bounded by

$$2\Delta(A)\Delta(B),$$

which is exactly the quantity appearing in the theorem. Missing one of the two symmetric cases would invalidate the estimate.

Alternative Approaches

A different route is to work directly with the complement $\overline H$. The complement of the $5\times5$ grid graph has minimum degree $20$. One can prove, by a vertex-by-vertex embedding argument with exchanges, that every $25$-vertex graph of maximum degree $3$ embeds into any $25$-vertex graph whose minimum degree exceeds $25-1-2\cdot3$. Applied to $\overline H$, this yields the required embedding.

The packing approach is preferable because it isolates the problem into a single numerical inequality,

$$2\Delta(G)\Delta(H)<25,$$

after which the structure of the quarrel graph and the grid graph no longer needs to be analyzed separately.