Maths Olympiad Prep

Library / /386 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it

3.66 n(>3)n(>3) is an integer, a0,a1,,ana_{0}, a_{1}, \cdots, a_{n} are integers satisfying 1a0<a1<<1 \leqslant a_{0}<a_{1}<\cdots< an2k3a_{n} \leqslant 2 \mathcal{k}-3, prove that there exist different integers i,j,k,l,mi, j, k, l, m, such that
ai+aj=ak+al=ama_{i}+a_{j}=a_{k}+a_{l}=a_{m}

Solution

[Proof] We prove a stronger conclusion: among integers satisfying 1a0<a1<<an2n1 \leqslant a_{0}<a_{1}<\cdots<a_{n} \leqslant 2 n -3, there must exist i,j,k,li, j, k, l, all not equal to nn, such that
ai+aj=ak+al=an.a_{i}+a_{j}=a_{k}+a_{l}=a_{n}.

We use proof by contradiction. Assume that there do not exist i,j,k,li, j, k, l satisfying the above equation, and let
A={a0,a1,,an1}.A=\left\{a_{0}, a_{1}, \cdots, a_{n-1}\right\}.

When an=2p+1a_{n}=2 p+1 (an odd number), consider pp pairs of numbers (1+i,2pi),i=0,1,2,,p1(1+i, 2 p-i), i=0,1, 2, \cdots, p-1. Since the sum of each pair is 2p+1=an2 p+1=a_{n}, the number of pairs where both numbers belong to AA is at most one. Since these pp pairs of 2p2 p numbers include all integers from 1 to 2p2 p, the elements of set AA must all appear in these pp pairs. Therefore, the number of elements in set AA is
np+1,n \leqslant p+1,
2n2p+2=an+1(2n3)+1,2 n \leqslant 2 p+2=a_{n}+1 \leqslant(2 n-3)+1, which is a contradiction.
When an=2pa_{n}=2 p (an even number), consider p1p-1 pairs of numbers (1+i,2p1i)(1+i, 2 p-1-i), i=0,1,,p2i=0,1, \cdots, p-2. Since the sum of each pair is 2p=an2 p=a_{n}, the number of pairs where both numbers belong to AA is at most one. Since these p1p-1 pairs of 2p22 p-2 numbers include all integers from 1 to 2p12 p-1 except pp, all elements of set AA except possibly pp must appear in these p1p-1 pairs. Therefore, the number of elements in set AA is
np+1,2n2p+2=an+2(2n3)+2, which is a contradiction. \begin{array}{l} n \leqslant p+1, \\ 2 n \leqslant 2 p+2=a_{n}+2 \leqslant(2 n-3)+2, \text { which is a contradiction. } \end{array}

Thus, the original proposition is proved.

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.