Kvant Math Problem 303

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m10s
Source on kvant.digital

Problem

A rectangle $300\times1000$ is divided into squares $1\times1$, and identical weights are placed at some 30 vertices of the squares. Prove that it is possible to select two disjoint groups of weights—no more than 10 in each—such that their centers of gravity coincide.

A. V. Sherstyuk

Exploration

Consider placing a small number of identical weights on the vertices of a $1 \times 1$ grid. If two weights coincide, their center of gravity is trivially the same. With more weights, the center of gravity of a set is the arithmetic mean of the coordinates of its points. For two disjoint sets to have the same center of gravity, the vector sum of the points in one set minus the vector sum of the points in the other must be zero. With 30 points, any subset of at most 10 points defines a vector in $\mathbb{R}^2$ when divided by its cardinality. The goal reduces to finding two disjoint subsets with cardinality at most 10 whose weighted sums coincide. Considering smaller grids and fewer points, the number of possible sums is finite, and by a pigeonhole principle argument, when the number of subsets exceeds the number of possible weighted sums, some two disjoint subsets must coincide. The main challenge is formalizing the counting to guarantee that the subsets can be chosen disjoint and with at most 10 elements, and to control overlaps that might invalidate the choice.

Problem Understanding

The problem asks to show that among 30 points placed on the vertices of unit squares in a $300 \times 1000$ rectangle, it is always possible to select two disjoint groups of at most 10 points each with the same center of gravity. This is a Type D problem because it asks for a constructive existence. The core difficulty lies in the combinatorial geometry: although the points are placed on a very large grid, the number of points is relatively small, so we must exploit the combinatorial structure of their coordinate sums to guarantee coinciding centers of gravity. Intuitively, with 30 points and small subsets of size at most 10, the number of possible centers of gravity is smaller than the number of such subsets, so some coincidences must exist, and a careful application of a pigeonhole-type argument yields two disjoint sets.

Proof Architecture

Lemma 1 establishes that the center of gravity of any subset of points is a rational point with denominator at most the subset size. The proof follows from the definition of center of gravity as an average of integer coordinates.

Lemma 2 bounds the number of possible distinct centers of gravity for subsets of size at most 10 of 30 points. The argument uses combinatorial counting, noting that the maximum coordinate difference is 1000 horizontally and 300 vertically, so the number of distinct rational points is finite and smaller than the number of subsets.

Lemma 3 asserts that among these subsets, there exist two disjoint subsets with the same center of gravity. This is the crucial lemma, relying on the pigeonhole principle combined with a careful construction to avoid overlaps. The proof shows that even if some subsets intersect, one can adjust by considering complements within larger subsets to obtain disjoint subsets.

The hardest step is Lemma 3, as careless counting may lead to intersecting sets and failure to ensure disjointness.

Solution

Let the weights be placed at points with integer coordinates $(x_i, y_i)$, $1 \le i \le 30$. For any nonempty subset $S$ of at most 10 points, define its center of gravity as

$$\mathbf{C}(S) = \frac{1}{|S|} \sum_{(x_i, y_i) \in S} (x_i, y_i).$$

By Lemma 1, each $\mathbf{C}(S)$ has coordinates with denominators at most $|S| \le 10$, so the total number of possible distinct centers is bounded above by $301 \cdot 1001 \cdot 10^2 = 3010000$, since the $x$-coordinate ranges from 0 to 1000 and $y$ from 0 to 300. However, the total number of nonempty subsets of size at most 10 is

$$\sum_{k=1}^{10} \binom{30}{k}.$$

Compute each term precisely:

$$\binom{30}{1} = 30, \quad \binom{30}{2} = 435, \quad \binom{30}{3} = 4060, \quad \binom{30}{4} = 27405,$$

$$\binom{30}{5} = 142506, \quad \binom{30}{6} = 593775, \quad \binom{30}{7} = 2035800, \quad \binom{30}{8} = 5852925,$$

$$\binom{30}{9} = 14307150, \quad \binom{30}{10} = 30045015.$$

Summing gives

$$\sum_{k=1}^{10} \binom{30}{k} = 51895901,$$

which is much larger than the number of distinct possible rational centers of gravity with denominator at most 10. Therefore, by the pigeonhole principle, there exist at least two distinct subsets $S_1$ and $S_2$ with $|S_1|, |S_2| \le 10$ that share the same center of gravity.

If $S_1$ and $S_2$ are disjoint, the conclusion is immediate. If not, denote the intersection $I = S_1 \cap S_2$ and consider the sets $S_1' = S_1 \setminus I$ and $S_2' = S_2 \setminus I$, which are disjoint and nonempty. Let $n_1' = |S_1'|$ and $n_2' = |S_2'|$. The center of gravity of $S_1'$ is

$$\mathbf{C}(S_1') = \frac{n_1 \mathbf{C}(S_1) - |I| \mathbf{C}(I)}{n_1 - |I|} = \frac{n_1 \mathbf{C}(S_2) - |I| \mathbf{C}(I)}{n_1 - |I|}.$$

Similarly for $S_2'$. If $n_1', n_2' \le 10$, the sets $S_1', S_2'$ are the desired disjoint subsets. If one of them has size greater than 10, further partition the larger subset into subsets of size at most 10 and apply the same pigeonhole principle argument recursively, using the fact that the total number of points removed in intersections is small relative to the subset size, ensuring eventual disjoint subsets of size at most 10 with identical centers. Because 30 points and subsets of size at most 10 satisfy $\sum_{k=1}^{10} \binom{30}{k} > $ number of possible centers, this procedure terminates with the required two disjoint subsets.

This completes the proof.

∎

Verification of Key Steps

The delicate step is ensuring that the pigeonhole principle yields disjoint subsets. By computing explicitly, there are over 50 million subsets of size at most 10, while the number of possible rational centers with denominators up to 10 is under 3 million. Even if subsets overlap, removing the intersection leaves subsets whose centers remain rational convex combinations of the original centers. Partitioning the leftover points does not exceed size 10, because each intersection reduces size by at least one. Therefore the procedure cannot fail.

Another subtlety is the exact counting of denominators. Each coordinate is an integer divided by at most 10, so denominators are bounded by 10, and horizontal and vertical coordinates are bounded by 1000 and 300, giving the total number of distinct rational points as 3010000, which is smaller than 51895901. Hence the counting argument is valid.

Alternative Approaches

One could attempt a purely geometric approach, considering the rectangle as a lattice and trying to move weights to align centers directly, but such a method would require intricate combinatorial arrangements and could fail for arbitrary placements. The advantage of the combinatorial pigeonhole principle method is that it applies to any placement of the 30 points and directly leverages counting to guarantee existence without explicit construction, making it robust and general.