Maths Olympiad Prep

Library / /39 of 97

Number theory Difficulty 7.8 National olympiad, round 2 Find the answer

For a given integer n2n\ge 2, let a0,a1,,ana_0,a_1,\ldots ,a_n be integers satisfying 0=a0<a1<<an=2n10=a_0<a_1<\ldots <a_n=2n-1. Find the smallest possible number of elements in the set {ai+aj0ijn}\{ a_i+a_j \mid 0\le i \le j \le n \}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

For a given integer n2 n \ge 2 , let a0,a1,,an a_0, a_1, \ldots, a_n be integers satisfying 0=a0<a1<<an=2n1 0 = a_0 < a_1 < \ldots < a_n = 2n-1 . We aim to find the smallest possible number of elements in the set {ai+aj0ijn} \{ a_i + a_j \mid 0 \le i \le j \le n \} .

First, we prove that the set {ai+aj1ijn1} \{ a_i + a_j \mid 1 \le i \le j \le n-1 \} takes all residues modulo 2n1 2n-1 . Consider the 2n 2n numbers:
a0<a1<<an1<an a_0 < a_1 < \cdots < a_{n-1} < a_n
and
ra0>ra1>>ran1>ran r - a_0 > r - a_1 > \cdots > r - a_{n-1} > r - a_n
for any integer 0r2n2 0 \le r \le 2n-2 . By the Pigeonhole Principle, there must be two numbers that are congruent modulo 2n1 2n-1 . Since ai≢aj(mod2n1) a_i \not\equiv a_j \pmod{2n-1} for 1i<jn1 1 \le i < j \le n-1 , there exist 1i,jn1 1 \le i, j \le n-1 such that airaj(mod2n1) a_i \equiv r - a_j \pmod{2n-1} , meaning ai+ajr(mod2n1) a_i + a_j \equiv r \pmod{2n-1} .

Thus, the set {ai+aj1ijn1} \{ a_i + a_j \mid 1 \le i \le j \le n-1 \} takes all residues modulo 2n1 2n-1 .

Returning to the original problem, we note that there are 2n+1 2n+1 distinct numbers:
a0+a0<a0+a1<<a0+an1<an+a0<an+a1<<an+an, a_0 + a_0 < a_0 + a_1 < \cdots < a_0 + a_{n-1} < a_n + a_0 < a_n + a_1 < \cdots < a_n + a_n,
which, modulo 2n1 2n-1 , take only n n different residues. Combining this with the fact that {ai+aj1ijn1} \{ a_i + a_j \mid 1 \le i \le j \le n-1 \} takes all residues modulo 2n1 2n-1 , there are at least n1 n-1 additional distinct numbers.

Therefore, the number of elements in the set {ai+aj0ijn} \{ a_i + a_j \mid 0 \le i \le j \le n \} is at least 2n+1+n1=3n 2n + 1 + n - 1 = 3n .

By setting ai=n1 a_i = n-1 for 1in1 1 \le i \le n-1 , we achieve {ai+aj0ijn}=3n \left| \{ a_i + a_j \mid 0 \le i \le j \le n \} \right| = 3n . Hence, the smallest possible number of elements in the set is 3n \boxed{3n} .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.