Maths Olympiad Prep

Track / Stage 6 / 159 of 400 #1159 of 1964

Problem 1159

National olympiad, first round
Combinatorics Difficulty 6.2 Prove it

. Consider 2007 real numbers x1,,x2007x_{1}, \ldots, x_{2007} such that for any I{1,2,,2007}I \subset\{1,2, \ldots, 2007\} of cardinality 7, there exists J{1,2,,2007}J \subset\{1,2, \ldots, 2007\} of cardinality 11 satisfying

17iIxi=111jJxj \frac{1}{7} \sum_{i \in I} x_{i}=\frac{1}{11} \sum_{j \in J} x_{j}

Show that all the xix_{i} are equal.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

First, note that up to a translation, we can assume that x1=0x_{1}=0.

Suppose first that the xix_{i} are integers. In this case, if II is a subset of {1,,2007}\{1, \ldots, 2007\} of cardinality 7, then 11iIxi0(mod7)11 \sum_{i \in I} x_{i} \equiv 0(\bmod 7) and thus, since 7 and 11 are coprime, iIxi0(mod7)\sum_{i \in I} x_{i} \equiv 0(\bmod 7). We deduce that for all i,xix0=0i, x_{i} \equiv x_{0}=0 (mod7)(\bmod 7), that is, all the xix_{i} are multiples of 7. Of course, the family of xi7\frac{x_{i}}{7} is still a solution to the problem. By infinite descent, we finally show that all the xix_{i} are zero, which is what we wanted.

Now let's handle the general case. We proceed by approximation. Take a family (xi)\left(x_{i}\right) of reals. Let NN be a strictly positive integer and greater than all the inverses of the xi\left|x_{i}\right| for xix_{i} non-zero. By applying the pigeonhole principle, we obtain a strictly positive integer DD and integers pip_{i} such that Dxipi1155N\left|D x_{i}-p_{i}\right| \leqslant \frac{1}{155 N} for all ii. Let's show that the family of the pip_{i} still satisfies the conditions of the statement. Take II a subset of {1,,2007}\{1, \ldots, 2007\} of cardinality 7. Then we can find a subset JJ of {1,,2007}\{1, \ldots, 2007\} of cardinality 11 such that:

11iIDxi=7jJDxj 11 \sum_{i \in I} D x_{i}=7 \sum_{j \in J} D x_{j}

Evaluate:

11iIpi7jJpj=11iI(piDxi)7jJ(pjDxj)11iIpiDxi+7jJpjDxj154155N<1 \begin{aligned} \left|11 \sum_{i \in I} p_{i}-7 \sum_{j \in J} p_{j}\right| & =\left|11 \sum_{i \in I}\left(p_{i}-D x_{i}\right)-7 \sum_{j \in J}\left(p_{j}-D x_{j}\right)\right| \\ & \leqslant 11 \sum_{i \in I}\left|p_{i}-D x_{i}\right|+7 \sum_{j \in J}\left|p_{j}-D x_{j}\right| \leqslant \frac{154}{155 N}<1 \end{aligned}

We deduce the expected equality, given that the number on the left-hand side is an integer. By the previous case, all the pip_{i} are zero and thus xiDxi1155N\left|x_{i}\right| \leqslant\left|D x_{i}\right| \leqslant \frac{1}{155 N}, which is impossible if xi0x_{i} \neq 0 by the definition of NN.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.