Maths Olympiad Prep

Library / /134 of 520

Number theory Difficulty 6.0 AIME, harder Prove it

20. (ROM 3) Let c1,,cnR(n2)c_{1}, \ldots, c_{n} \in \mathbb{R}(n \geq 2) such that 0i=1ncin0 \leq \sum_{i=1}^{n} c_{i} \leq n. Show that we can find integers k1,,knk_{1}, \ldots, k_{n} such that i=1nki=0\sum_{i=1}^{n} k_{i}=0 and
1nci+nkin for every i=1,,n 1-n \leq c_{i}+n k_{i} \leq n \quad \text { for every } i=1, \ldots, n

Solution

20. For every real xx we shall denote by x\lfloor x\rfloor and x\lceil x\rceil the greatest integer less than or equal to xx and the smallest integer greater than or equal to xx respectively. The condition ci+nki[1n,n]c_{i}+n k_{i} \in[1-n, n] is equivalent to kiIi=k_{i} \in I_{i}= [1cin1,1cin]\left[\frac{1-c_{i}}{n}-1,1-\frac{c_{i}}{n}\right]. For every cic_{i}, this interval contains two integers (not necessarily distinct), namely pi=1cin1qi=1cinp_{i}=\left\lceil\frac{1-c_{i}}{n}-1\right\rceil \leq q_{i}=\left\lfloor 1-\frac{c_{i}}{n}\right\rfloor. In order to show that there exist integers kiIik_{i} \in I_{i} with i=1nki=0\sum_{i=1}^{n} k_{i}=0, it is sufficient to show that i=1npi0i=1nqi\sum_{i=1}^{n} p_{i} \leq 0 \leq \sum_{i=1}^{n} q_{i}. Since picinp_{i}-\frac{c_{i}}{n} implies
i=1nqi>i=1ncin1 \sum_{i=1}^{n} q_{i}>-\sum_{i=1}^{n} \frac{c_{i}}{n} \geq-1
which leads to i=1nqi0\sum_{i=1}^{n} q_{i} \geq 0. The proof is complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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