Maths Olympiad Prep

Library / /293 of 299

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Iran

We say a set {a1,,an}\{a_1, \dots, a_n\} of real numbers is interesting if for all 1<i<n1 < i < n we have 0<ai+1ai<aiai10 < a_{i+1} - a_i < a_i - a_{i-1}. For each positive integer mm find the smallest positive integer kk such that there is an interesting set AA with kk elements such that 11 can be written in at least mm different ways as the difference of two elements of AA.

Solution

First Solution. Defining bi=ai+1aib_i = a_{i+1} - a_i, i=1,,n1i = 1, \dots, n-1. Thus, (bi)(b_i) is a decreasing sequence of positive real numbers. Then, the difference of any two elements of AA can be written as the sum of some of the bib_i's. Assume
bi1+bi2++bij=bi2++bij==bim++bin=1 b_{i_1} + b_{i_2} + \dots + b_{i_j} = b_{i_2} + \dots + b_{i_j} = \dots = b_{i_m} + \dots + b_{i_n} = 1
Such that i1<i2<<imi_1 < i_2 < \cdots < i_m. If t>kt > k then jtit>jkikj_t - i_t > j_k - i_k. Since these numbers are positive, we find that i1,,imi_1, \dots, i_m are distinct. Therefore,
jm=jmim+imm1+m j_m = j_m - i_m + i_m \geq m - 1 + m
Yielding, n2mn \ge 2m. Now, we construct two different examples;

1st Example. Let bm=2m1m(3m1)b_m = \frac{2m-1}{m(3m-1)}, bm+1=2m2m(3m+1)b_{m+1} = \frac{2m-2}{m(3m+1)}, \dots, b2m1=2m(3m1)b_{2m-1} = \frac{2}{m(3m-1)}. Then, we go inductively through i=m1i = m-1 and construct b1,,bm1b_1, \dots, b_{m-1} as bi=b2i+b2i+1b_i = b_{2i}+b_{2i+1}, notice that since for all i<n1i < n-1 the inequalities bi>bi+1b_i > b_{i+1} and b2i+b2i+1>b2i+2+b2i+3b_{2i} + b_{2i+1} > b_{2i+2} + b_{2i+3} are equivalent, we find that b1,b_1, \dots form a decreasing sequence. On the other hand,
bi++b2i1=bi+1++b2(i+1)1 b_i + \cdots + b_{2i-1} = b_{i+1} + \cdots + b_{2(i+1)-1}
It is easy to verify that such an example works.

Second Solution We can prove something more general; for every positive integer mm there is a nice set AA of size 2m2m and a nonzero real number dd that can be written as a difference of two elements of AA in at least mm different ways. Let Sd={(a,b)A×A;ab=d}S_d = \{(a,b) \in A \times A; a-b=d\}, we prove that Sdm|S_d| \ge m. Indeed, Let A={a1<<a2m}A = \{a_1 < \cdots < a_{2m}\}, which is made of two halves. The set AA begins with 00, and then has gaps 1+(i1)δ1+ (i-1)\delta, for some very small δ>0\delta > 0 which will be specified later. The first half of AA is filled like this. That is, for 1km+11 \le k \le m+1, we define ak=(k1)+δ(k2)(k1)2a_k = (k-1)+\delta \frac{(k-2)(k-1)}{2}, and so the first m+1m+1 elements of AA are elements of the set A1={0,1,2+δ,3+3δ,,m+δm(m1)2}A_1 = \{0,1,2+\delta,3+3\delta,\cdots,m+\delta \frac{m(m-1)}{2}\}. Fix d=m+δm(m1)2=am+1d = m + \delta \frac{m(m-1)}{2} = a_{m+1}. The rest of AA is defined iteratively. For 1im11 \le i \le m-1, we get am+1+i=a1+2i+da_{m+1+i} = a_{1+2i}+d. This immediately gives rise to the system of equations d=am+1a1=am+2a3==a2ma2m1d = a_{m+1} - a_1 = a_{m+2} - a_3 = \cdots = a_{2m} - a_{2m-1}. We therefore Sd(A)m|S_d(A)| \ge m. It remains to check that this set is nice. Note that A1={a1,,am+1}A_1 = \{a_1, \cdots, a_{m+1}\} is nice, since the consecutive difference increase by δ\delta at each step.
We will prove by induction on ii that the set {a1,,am+2+i}\{a_1, \cdots, a_{m+2+i}\} is nice for 0im20 \le i \le m-2. We first check the base for i=0i=0. We need to verify that the difference am+2am+1a_{m+2}-a_{m+1} is sufficiently large, which will give a condition on δ\delta. We must have am+2am+1>am+1ama_{m+2}-a_{m+1}>a_{m+1}-a_m. We need to have δ<1m2\delta < \frac{1}{m-2}. Now, let 1im21 \le i \le m-2. We must verify that {a1,,am+2+i}\{a_1, \cdots, a_{m+2+i}\} is nice, given the induction hypothesis that {a1,a2,,am+1+i}\{a_1, a_2, \cdots, a_{m+1+i}\} is nice. All that remains to check that am+2+iam+1+i>am+1+iam+ia_{m+2+i}-a_{m+1+i} > a_{m+1+i}-a_{m+i}. Note That am+2+iam+1+i=a1+2(i+1)a1+2ia_{m+2+i}-a_{m+1+i} = a_{1+2(i+1)} - a_{1+2i} and am+1+iam+i=a1+2ia1+2(i1)a_{m+1+i} - a_{m+i} = a_{1+2i} - a_{1+2(i-1)}. Note that, since the difference on the right hand side above are then consecutive differences of length two within a nice set, we have
am+2+iam+1+i=a1+2(i+1)a1+2i>a1+2ia1+2(i1)=am+1+iam+i a_{m+2+i} - a_{m+1+i} = a_{1+2(i+1)} - a_{1+2i} > a_{1+2i} - a_{1+2(i-1)} = a_{m+1+i} - a_{m+i}
as needed. Here we have used the inductive hypothesis that {a1,,am+1+i}\{a_1, \cdots, a_{m+1+i}\} is nice as well as the fact that 1+2(i+1)m+1+i1+2(i+1) \le m+1+i. The latter inequality follows from the condition im2i \le m-2.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.