Maths Olympiad Prep

Library / /380 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Let 3a1,a2,,a20023 a_{1}, a_{2}, \cdots, a_{2002} be non-negative integers, satisfying
ai+ajai+jai+aj+1,1i,j2002,i+j2002.a_{i}+a_{j} \leqslant a_{i+j} \leqslant a_{i}+a_{j}+1,1 \leqslant i, j \leqslant 2002, i+j \leqslant 2002 .

Prove: There exists a real number x,an=[nx],n=1,2,,2002x, a_{n}=[n x], n=1,2, \cdots, 2002.

Solution

Let In=(ann,an+1n),n=1,2,,2002I_{n}=\left(\frac{a_{n}}{n}, \frac{a_{n}+1}{n}\right), n=1,2, \cdots, 2002. If there exists a real number xn=12002Inx \in \bigcap_{n=1}^{2002} I_{n}, then the proposition is proved.

For this, let L=max1n2002ann,U=min1n2002an+1nL=\max _{1 \leqslant n \leqslant 2002} \frac{a_{n}}{n}, U=\min _{1 \leqslant n \leqslant 2002} \frac{a_{n}+1}{n}. We want to prove L<UL < U. To do this, we need to show that for any n,m{1,2,,2002}n, m \in \{1, 2, \cdots, 2002\}, the following inequality holds:
man<n(am+1).(1) m a_{n} < n (a_{m} + 1). \tag{1}

We will prove this by induction on mm.

Base Case: For m=1m = 1, the inequality becomes an<n(a1+1)a_{n} < n (a_{1} + 1). Since a10a_{1} \geq 0, this is clearly true.

Inductive Step: Assume that for some m1m \geq 1, the inequality holds for all n{1,2,,2002}n \in \{1, 2, \cdots, 2002\}. We need to show that the inequality holds for m+1m+1.

- If m>nm > n, then by the induction hypothesis, we have (mn)an<n(amn+1)(m-n) a_{n} < n (a_{m-n} + 1). By the given condition, n(amn+an)namn (a_{m-n} + a_{n}) \leq n a_{m}. Therefore, man<n(am+1)m a_{n} < n (a_{m} + 1), and inequality (1) holds.
- If m<nm < n, by the induction hypothesis, we have manm<(nm)(am+1)m a_{n-m} < (n - m) (a_{m} + 1). By the given condition, manm(am+anm+1)m a_{n} \leq m (a_{m} + a_{n-m} + 1). Adding these two inequalities, we get man<n(am+1)m a_{n} < n (a_{m} + 1), and inequality (1) also holds.

In conclusion, for n,m{1,2,,2002}n, m \in \{1, 2, \cdots, 2002\}, inequality (1) always holds.

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.