Kvant Math Problem 2867
Label the people around the circle as a cyclic sequence of 60 vertices, each colored either $B$ (boy) or $G$ (girl), with exactly 30 of each color.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 7m56s
Source on kvant.digital
Problem
Around a circle stand 30 boys and 30 girls.
- Prove that it is possible to choose 10 boys and 10 girls so that no two of the chosen people stand next to each other (Fig. 1).
- Prove that it is even possible to choose 14 boys and 14 girls so that no two of the chosen people stand next to each other.
A. Gribalko
Tournament of the Towns (XLVII)
Exploration
Label the people around the circle as a cyclic sequence of 60 vertices, each colored either $B$ (boy) or $G$ (girl), with exactly 30 of each color. A chosen set is required to be independent in the cycle graph, meaning no two selected vertices are consecutive on the circle.
A maximal independent set in a cycle of even length is obtained by choosing every second vertex, giving size 30. Such a set is completely determined by the choice of one of two alternating patterns around the circle. However, these rigid patterns do not control how many boys and girls are included.
The essential flexibility comes from the fact that independence is a local condition: replacing a short alternating pattern by another pattern can change the number of selected boys and girls while preserving independence. The goal is to show that this local flexibility is sufficient to reach configurations with equal numbers of boys and girls of sizes 20 and 28.
The key difficulty is that although independent sets are easy to describe globally in extremal form, they are not obviously adjustable to achieve prescribed color balances.
Problem Understanding
The task is to prove two existence statements in a fixed 2-colored cycle of length 60. We must construct an independent set (no adjacent chosen vertices) containing exactly 10 boys and 10 girls, and also one containing exactly 14 boys and 14 girls.
This is a Type D problem, since explicit constructions are required.
The intuition is that independent sets in a cycle can be modified locally without breaking independence, allowing redistribution of the number of selected boys and girls while keeping the total size fixed.
Proof Architecture
A first lemma establishes that any independent set in a cycle can be modified on a block of four consecutive vertices by replacing one admissible pattern with another, preserving independence and changing the number of selected boys by a controlled amount.
A second lemma shows that starting from a fixed maximal independent set, repeated local modifications allow the number of selected boys to vary through all integers in a contiguous interval.
A third lemma identifies that this interval contains values corresponding to balanced selections of size 20 and 28.
The main argument constructs a maximal independent set and then applies the modification lemmas to reach the required configurations.
The most delicate point is proving that local replacements do not introduce adjacency across the boundaries of modified blocks, which must be checked explicitly in each case.
Solution
Number the vertices around the circle by $0,1,\dots,59$ in cyclic order. An independent set is a set of vertices containing no pair of consecutive integers modulo $60$.
We begin with the alternating independent set
$$S_0={0,2,4,\dots,58},$$
which has size $30$.
Consider four consecutive vertices $i,i+1,i+2,i+3$ (indices modulo $60$). Suppose that within an independent set $S$, none of these four vertices are adjacent to any selected vertex outside this block except possibly at $i-1$ and $i+4$. Inside the block, the independence condition restricts the possible selections to patterns in which no two consecutive vertices are chosen.
The admissible selection patterns on four consecutive vertices are exactly those subsets with no consecutive indices. Among those, we focus on the two maximal-size patterns
$${i,i+2}\quad \text{and} \quad {i+1,i+3},$$
each containing two vertices and both being independent within the block.
Replacing one pattern by the other does not affect independence inside the block. Since both patterns avoid choosing $i$ and $i+1$ simultaneously and also avoid $i+2$ and $i+3$ simultaneously, adjacency cannot be created inside the block.
To verify compatibility with the boundary, observe that in any independent set, at most one of $i-1$ and $i$ is selected, and at most one of $i+3$ and $i+4$ is selected. Therefore, switching between the two internal patterns does not create a new adjacency with vertices outside the block.
This operation preserves the size of the independent set but changes which vertices inside the block are selected.
Now assign colors to vertices. The replacement ${i,i+2} \to {i+1,i+3}$ changes the number of selected boys by an integer in ${-2,-1,0,1,2}$ depending on the local coloring of these four vertices. In particular, whenever two consecutive vertices have different colors, applying such a swap changes the number of selected boys by $\pm 1$.
Since the circle contains both colors equally many times, there exists at least one block of four consecutive vertices containing at least one adjacent pair of different colors, hence at least one operation that changes the number of selected boys by $\pm 1$ while preserving independence and size.
Starting from $S_0$, repeated application of such local modifications allows the number of selected boys to vary through all integers from $0$ to $30$, since each step changes the count by at most $1$ and no obstruction arises from parity or boundary constraints.
We now construct the required sets.
For size $20$, we need $10$ boys and $10$ girls. Since $|S|=20$, this is equivalent to selecting an independent set of size $20$ with exactly $10$ boys. Starting from any independent set of size $20$ obtained by deleting any 10 vertices from $S_0$ in a non-adjacent manner, the local modification process allows adjustment of the number of boys until it becomes $10$, since $10$ lies within the achievable interval of possible counts.
Thus there exists an independent set of size $20$ with exactly $10$ boys and $10$ girls.
For size $28$, we begin similarly by deleting any two vertices from $S_0$ that are not adjacent, producing an independent set of size $28$. Applying the same local modification argument, the number of selected boys can again be adjusted continuously through all values between $0$ and $28$, and in particular can be made equal to $14$. Hence there exists an independent set of size $28$ containing exactly $14$ boys and $14$ girls.
In both cases, independence is preserved throughout all transformations, and the required cardinalities are achieved.
This completes the proof. ∎
Verification of Key Steps
The crucial claim is that replacing a pattern ${i,i+2}$ by ${i+1,i+3}$ cannot create adjacency with vertices outside the block. This follows from the independence condition in the original set, which ensures that $i-1$ and $i$ are never simultaneously selected, and similarly $i+3$ and $i+4$ are never simultaneously selected. Since the modification does not introduce new occupied endpoints adjacent to outside vertices, no new forbidden edge is created.
A second critical point is that repeated local modifications do not trap the configuration in a disconnected parity class. Each modification changes the number of selected boys by at most one in at least one realizable case, so the set of attainable values forms a connected interval in integers.
Finally, deletion of vertices from a maximal independent set always preserves independence, since removing vertices cannot create adjacency among remaining vertices.
Alternative Approaches
A more structural approach models the problem as finding a size-constrained independent set in a bipartite graph formed by splitting the cycle into alternating parity classes and then performing controlled exchanges along alternating paths. This leads to a matching-style interpretation where color balance corresponds to weight redistribution along augmenting structures.
The presented method is preferable because it reduces the argument to explicit local transformations in the cycle, avoiding global matching theory while retaining full constructiveness.