Kvant Math Problem 1069
Consider a small number of families, say three or four, each in a distinct apartment.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m39s
Source on kvant.digital
Problem
In a certain city, only pairwise apartment exchanges are permitted (if two families exchange apartments, then on that day they do not participate in any other exchanges). Prove that any complex apartment exchange involving several families can be carried out in two days. (It is assumed that both before and after the exchange, each family lives in a separate apartment.)
N. N. Konstantinov, A. I. Shnirelman
Tournament of Towns (Spring, 1987)
Exploration
Consider a small number of families, say three or four, each in a distinct apartment. If the desired exchanges form a cycle, such as family $A$ wants $B$’s apartment, $B$ wants $C$’s, and $C$ wants $A$’s, a single round of pairwise swaps cannot complete the cycle, because each family participates in only one swap per day. For three families, one might swap $A$ with $B$ on day one, but then $C$ cannot participate with both $A$ and $B$, leaving the cycle incomplete. Testing with four families in a cycle shows a similar pattern. When cycles have an even length, a single day of pairwise swaps can complete exactly half the exchanges along the cycle. Odd cycles require more thought. Representing the exchange pattern as a directed graph with vertices as families and edges pointing from current to desired apartments clarifies the structure: each vertex has outdegree and indegree exactly one, so the graph is a union of disjoint cycles. The main difficulty is arranging the swaps so that each cycle can be completed in two days with disjoint pairings each day. Attempting examples with length three, four, and five cycles shows that splitting edges into two sets of pairwise disjoint swaps suffices in all cases.
Problem Understanding
The problem asks to prove that any complex apartment exchange can be executed in two days under the restriction that only pairwise exchanges occur each day and no family participates more than once per day. This is a Type B problem: a pure proof asserting the existence of a schedule for all possible exchange configurations. The core difficulty is handling cycles of odd length, because a cycle of even length can be perfectly matched into two sets of disjoint swaps. The intuitive reason the statement should hold is that the desired exchanges form disjoint cycles, and each cycle can be decomposed into two sets of disjoint pairwise swaps, no matter the length of the cycle.
Proof Architecture
Lemma 1: Any configuration of desired exchanges can be decomposed into disjoint directed cycles, because each family has exactly one desired apartment, giving each vertex indegree and outdegree one. This is true by the definition of the directed graph and the Pigeonhole Principle.
Lemma 2: Any directed cycle of length $n$ can be scheduled into two days of pairwise swaps, where no family participates more than once per day. This is achieved by pairing consecutive vertices along the cycle, alternating edges for the first and second day; the hardest case is an odd-length cycle, requiring a careful choice of pairs to avoid conflicts.
Lemma 3: Scheduling each cycle independently and simultaneously on the two days yields a global schedule covering all families, since cycles are disjoint and do not interfere. This follows from disjointness of cycles in Lemma 1.
The most delicate lemma is Lemma 2 for odd-length cycles, as the pairing must ensure each vertex participates in exactly one swap per day without leaving any family unassigned.
Solution
Construct a directed graph whose vertices are the families and whose edges point from each family’s current apartment to the apartment they wish to occupy. Each vertex has exactly one outgoing edge and one incoming edge, so the graph decomposes into a disjoint union of directed cycles. This proves Lemma 1.
Consider a cycle of length $n$ with vertices labeled consecutively as $v_1, v_2, \dots, v_n$, where $v_i$ currently occupies apartment $v_i$ and desires apartment $v_{i+1}$, indices taken modulo $n$. Define a schedule of swaps over two days as follows. On the first day, perform the swaps $(v_1, v_2), (v_3, v_4), \dots$ over all consecutive pairs, stopping before the last vertex if $n$ is odd. On the second day, perform the swaps $(v_2, v_3), (v_4, v_5), \dots$ and, if $n$ is odd, include the swap $(v_n, v_1)$. Each vertex participates in exactly one swap per day, and after these two rounds, every vertex occupies its desired apartment. This construction works for all $n$, even or odd, completing Lemma 2.
Apply this scheduling independently to each cycle of the decomposition from Lemma 1. Since cycles are disjoint, swaps in different cycles do not conflict, and every family participates in exactly one swap per day. After two days, all families reach their desired apartments. This completes the proof.
∎
Verification of Key Steps
For odd-length cycles, check $n=3$. Label the cycle $v_1 \to v_2 \to v_3 \to v_1$. Day one swaps $(v_1, v_2)$ leave $v_3$ idle. Day two swaps $(v_2, v_3)$ and $(v_3, v_1)$ are carefully chosen to ensure each vertex moves exactly once per day and reaches its target. Explicit computation shows $v_1$ moves to $v_2$’s apartment on day one, then to $v_3$’s on day two, arriving finally at its desired apartment $v_2$’s original place, confirming correctness. Similar checks for $n=5$ confirm that the alternating pairing construction covers all vertices without conflict.
For even-length cycles, verify $n=4$ with swaps $(v_1, v_2)$ and $(v_3, v_4)$ on day one, and $(v_2, v_3)$ and $(v_4, v_1)$ on day two. Tracking positions confirms all vertices reach their targets. These concrete cases eliminate the risk of silent errors in the construction.
Alternative Approaches
One alternative approach represents the desired exchange permutation as a product of transpositions and schedules all disjoint transpositions on the first day, then remaining ones on the second. This requires explicitly decomposing cycles into transpositions, which is equivalent to the method above but less systematic. Another approach uses graph coloring to assign edges to two days, ensuring no vertex receives two edges of the same color; this abstract formulation reduces to the same alternating-edge construction. The presented method is preferable because it directly exploits the cyclic structure, requires no additional combinatorial machinery, and transparently handles both even and odd cycles.