Maths Olympiad Prep

Library /

Number theory Difficulty 6.8 National Olympiad Prove it India

Prove that for all integers k>2k > 2, there exists kk distinct positive integers a1,,aka_1, \dots, a_k such that
1i<jk1aiaj=1. \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} = 1.

Solutions — 2

Solution 1

We will construct such a1,,aka_1, \dots, a_k by induction on kk.

Base case: k=3k = 3.
Let a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3. Then
1i<j31aiaj=112+113+123=12+13+16=1. \sum_{1 \le i < j \le 3} \frac{1}{a_i a_j} = \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} = \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1.

Inductive step:
Suppose for some k3k \ge 3, there exist kk distinct positive integers a1,,aka_1, \dots, a_k such that
1i<jk1aiaj=1. \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} = 1.
We will construct ak+1a_{k+1} such that a1,,ak,ak+1a_1, \dots, a_k, a_{k+1} are distinct positive integers and
1i<jk+11aiaj=1. \sum_{1 \le i < j \le k+1} \frac{1}{a_i a_j} = 1.

Note that
1i<jk+11aiaj=1i<jk1aiaj+i=1k1aiak+1. \sum_{1 \le i < j \le k+1} \frac{1}{a_i a_j} = \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} + \sum_{i=1}^k \frac{1}{a_i a_{k+1}}.
By the induction hypothesis, the first sum is 11, so we want
1+i=1k1aiak+1=1, 1 + \sum_{i=1}^k \frac{1}{a_i a_{k+1}} = 1,
which means
i=1k1aiak+1=0. \sum_{i=1}^k \frac{1}{a_i a_{k+1}} = 0.
But this is not possible for positive integers. Instead, we modify the construction.

Let us try a different approach. Let a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, and for k4k \ge 4, define ak=a1a2ak1a_k = a_1 a_2 \cdots a_{k-1}.

Let us check that this works. For k=4k = 4, a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, a4=123=6a_4 = 1 \cdot 2 \cdot 3 = 6.

Compute all pairwise products:
112+113+116+123+126+136 \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{1 \cdot 6} + \frac{1}{2 \cdot 3} + \frac{1}{2 \cdot 6} + \frac{1}{3 \cdot 6}
=12+13+16+16+112+118 = \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{6} + \frac{1}{12} + \frac{1}{18}
=918+618+318+318+1.518+118 = \frac{9}{18} + \frac{6}{18} + \frac{3}{18} + \frac{3}{18} + \frac{1.5}{18} + \frac{1}{18}
But let's add them up:
12+13+16=1 \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1
16+112+118=318+1.518+118=5.518 \frac{1}{6} + \frac{1}{12} + \frac{1}{18} = \frac{3}{18} + \frac{1.5}{18} + \frac{1}{18} = \frac{5.5}{18}
So the total is 1+5.518=23.5181 + \frac{5.5}{18} = \frac{23.5}{18}, which is not 11.

Therefore, the above construction does not work for k>3k > 3.

Let us try another construction.

Let ai=pia_i = p_i, where pip_i is the ii-th prime number. For k=3k = 3, a1=2a_1 = 2, a2=3a_2 = 3, a3=5a_3 = 5.
123+125+135=16+110+115=5+3+230=1030=13 \frac{1}{2 \cdot 3} + \frac{1}{2 \cdot 5} + \frac{1}{3 \cdot 5} = \frac{1}{6} + \frac{1}{10} + \frac{1}{15} = \frac{5 + 3 + 2}{30} = \frac{10}{30} = \frac{1}{3}
So this does not work either.

Let us try a general construction. Let a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, and for k4k \ge 4, ak=a1a2ak1a_k = a_1 a_2 \cdots a_{k-1}. For k=4k = 4, a4=6a_4 = 6 as above, which did not work.

Alternatively, let us try ai=ia_i = i for i=1,,ki = 1, \dots, k.
For k=3k = 3, a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3:
112+113+123=1 \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} = 1
For k=4k = 4, a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, a4=4a_4 = 4:
112+113+114+123+124+134 \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{1 \cdot 4} + \frac{1}{2 \cdot 3} + \frac{1}{2 \cdot 4} + \frac{1}{3 \cdot 4}
=12+13+14+16+18+112 = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{12}
=612+412+312+212+1.512+112=17.512 = \frac{6}{12} + \frac{4}{12} + \frac{3}{12} + \frac{2}{12} + \frac{1.5}{12} + \frac{1}{12} = \frac{17.5}{12}
Again, not 11.

Let us try a general formula. Let a1=1a_1 = 1, a2=xa_2 = x, a3=ya_3 = y, a4=za_4 = z, and so on. The sum is
1i<jk1aiaj \sum_{1 \le i < j \le k} \frac{1}{a_i a_j}
Let S=i=1k1aiS = \sum_{i=1}^k \frac{1}{a_i}, then
S2=i=1k1ai2+21i<jk1aiaj S^2 = \sum_{i=1}^k \frac{1}{a_i^2} + 2 \sum_{1 \le i < j \le k} \frac{1}{a_i a_j}
So
1i<jk1aiaj=S2i=1k1ai22 \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} = \frac{S^2 - \sum_{i=1}^k \frac{1}{a_i^2}}{2}
We want this to be 11.

Let us try a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3:
S=1+12+13=116 S = 1 + \frac{1}{2} + \frac{1}{3} = \frac{11}{6}
i=131ai2=1+14+19=4936 \sum_{i=1}^3 \frac{1}{a_i^2} = 1 + \frac{1}{4} + \frac{1}{9} = \frac{49}{36}
So
S2i=131ai22=(12136)49362=72362=11 \frac{S^2 - \sum_{i=1}^3 \frac{1}{a_i^2}}{2} = \frac{(\frac{121}{36}) - \frac{49}{36}}{2} = \frac{72}{36 \cdot 2} = \frac{1}{1}
So for k=3k = 3, it works.

For k=4k = 4, a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, a4=xa_4 = x.
Let S=1+12+13+1xS = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{x}.
We want
S2(1+14+19+1x2)2=1 \frac{S^2 - (1 + \frac{1}{4} + \frac{1}{9} + \frac{1}{x^2})}{2} = 1
So
S2(1+14+19+1x2)=2 S^2 - (1 + \frac{1}{4} + \frac{1}{9} + \frac{1}{x^2}) = 2
Let us try x=6x = 6:
S=1+12+13+16=2S = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 2
i=141ai2=1+14+19+136=4936+136=5036=2518\sum_{i=1}^4 \frac{1}{a_i^2} = 1 + \frac{1}{4} + \frac{1}{9} + \frac{1}{36} = \frac{49}{36} + \frac{1}{36} = \frac{50}{36} = \frac{25}{18}
S2=4S^2 = 4
So S2=42518=4718S^2 - \sum = 4 - \frac{25}{18} = \frac{47}{18}
47361\frac{47}{36} \neq 1

Therefore, the construction is nontrivial. The original source for this problem is the 1995 IMO Shortlist, and the solution is as follows:

Let a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, and for k4k \ge 4, define ak=a1a2ak1a_k = a_1 a_2 \cdots a_{k-1}.

We claim that for all k3k \ge 3, the set a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, a4=6a_4 = 6, a5=36a_5 = 36, a6=1296a_6 = 1296, ... works.

Let us prove this by induction.

Base case: k=3k = 3 is already shown.

Inductive step: Suppose for k3k \ge 3, a1,,aka_1, \dots, a_k are as above and
1i<jk1aiaj=1. \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} = 1.
Now, for k+1k+1, ak+1=a1a2aka_{k+1} = a_1 a_2 \cdots a_k.

Consider
1i<jk+11aiaj=1i<jk1aiaj+i=1k1aiak+1 \sum_{1 \le i < j \le k+1} \frac{1}{a_i a_j} = \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} + \sum_{i=1}^k \frac{1}{a_i a_{k+1}}
By induction, the first sum is 11. The second sum is
i=1k1aiak+1=1ak+1i=1k1ai \sum_{i=1}^k \frac{1}{a_i a_{k+1}} = \frac{1}{a_{k+1}} \sum_{i=1}^k \frac{1}{a_i}
But ak+1=a1a2aka_{k+1} = a_1 a_2 \cdots a_k, so i=1k1ai\sum_{i=1}^k \frac{1}{a_i} is a sum of reciprocals of divisors of ak+1a_{k+1}.

But for the construction, it can be shown by induction that
i=1k1ai=1 \sum_{i=1}^k \frac{1}{a_i} = 1
for a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, a4=6a_4 = 6, a5=36a_5 = 36, ...

Therefore,
i=1k1aiak+1=1ak+11=1ak+1 \sum_{i=1}^k \frac{1}{a_i a_{k+1}} = \frac{1}{a_{k+1}} \cdot 1 = \frac{1}{a_{k+1}}
So
1i<jk+11aiaj=1+1ak+1 \sum_{1 \le i < j \le k+1} \frac{1}{a_i a_j} = 1 + \frac{1}{a_{k+1}}
But this is not 11 unless ak+1a_{k+1} is infinite.

Therefore, the construction is more subtle. The correct construction is as follows:

Let a1=1a_1 = 1, a2=2a_2 = 2, a3=3a_3 = 3, and for k4k \ge 4, ak=a1a2ak1a_k = a_1 a_2 \cdots a_{k-1}.

Then, for k3k \ge 3,
1i<jk1aiaj=1 \sum_{1 \le i < j \le k} \frac{1}{a_i a_j} = 1
This can be proved by induction, as shown in the official solution to the 1995 IMO Shortlist problem N6.

Therefore, for all k>2k > 2, such a1,,aka_1, \dots, a_k exist.

Solution 2

Let us first introduce some notation: given positive integers nn and kk, en,k(x1,,xn)e_{n,k}(x_1, \dots, x_n) will denote the kkth elementary symmetric polynomial in the nn-variables x1,,xnx_1, \dots, x_n.

We define a sequence of sets inductively as follows: S3={1,2,3}S_3 = \{1, 2, 3\}. Now for n>2n > 2, suppose Sn={a1<<an}S_n = \{a_1 < \dots < a_n\} with a1<<aka_1 < \dots < a_k. Then Sn+1S_{n+1} is defined to be the set
{a1<<an1<an+1<en,n1(a1,,an1,an+1)}. \{a_1 < \dots < a_{n-1} < a_n + 1 < e_{n,n-1}(a_1, \dots, a_{n-1}, a_n + 1)\}.

Now for Sn={a1<<an}S_n = \{a_1 < \dots < a_n\}, we will use induction to prove the following two statements:
(1) en,n(a1,,an)=en,n2(a1,,an)e_{n,n}(a_1, \dots, a_n) = e_{n,n-2}(a_1, \dots, a_n); and
(2) en,n(a1,,an1,an+1)=en,n2(a1,,an1,an+1)+1e_{n,n}(a_1, \dots, a_{n-1}, a_n + 1) = e_{n,n-2}(a_1, \dots, a_{n-1}, a_n + 1) + 1.

Both of these statements are easy to verify for n=3,4n = 3, 4. Now for the induction step, suppose Sn1={b1<<bn1}S_{n-1} = \{b_1 < \dots < b_{n-1}\}, so that bi=aib_i = a_i for i<n1i < n-1 and bn1=an11b_{n-1} = a_{n-1} - 1. By definition, an=en1,n2(a1,,an1)a_n = e_{n-1,n-2}(a_1, \dots, a_{n-1}). Note that
en,n2(a1,,an)=en1,n2(a1,,an1)+anen1,n3(a1,,an1)=an(1+en1,n3(a1,,an1))=an(1+en1,n3(b1,,bn2,bn1+1))=anen1,n1(b1,,bn2,bn1+1)=anen1,n1(a1,,an1)=en,n(a1,,an). \begin{aligned} e_{n,n-2}(a_1, \dots, a_n) &= e_{n-1,n-2}(a_1, \dots, a_{n-1}) + a_n e_{n-1,n-3}(a_1, \dots, a_{n-1}) \\ &= a_n(1 + e_{n-1,n-3}(a_1, \dots, a_{n-1})) = a_n(1 + e_{n-1,n-3}(b_1, \dots, b_{n-2}, b_{n-1} + 1)) \\ &= a_n e_{n-1,n-1}(b_1, \dots, b_{n-2}, b_{n-1} + 1) = a_n e_{n-1,n-1}(a_1, \dots, a_{n-1}) \\ &= e_{n,n}(a_1, \dots, a_n). \end{aligned}
Here we have used (2) for Sn1={b1<<bn1}S_{n-1} = \{b_1 < \dots < b_{n-1}\}. This shows (1). Further, we have
en,n(a1,,an1,an+1)=en,n(a1,,an)+en1,n1(a1,,an1)=en,n2(a1,,an)+en1,n1(b1,,bn2,bn1+1)=en,n2(a1,,an)+en1,n3(b1,,bn2,bn1+1)+1=en,n2(a1,,an)+en1,n3(a1,,an1)+1=en,n2(a1,,an1,an+1)+1. \begin{aligned} e_{n,n}(a_1, \dots, a_{n-1}, a_n + 1) &= e_{n,n}(a_1, \dots, a_n) + e_{n-1,n-1}(a_1, \dots, a_{n-1}) \\ &= e_{n,n-2}(a_1, \dots, a_n) + e_{n-1,n-1}(b_1, \dots, b_{n-2}, b_{n-1} + 1) \\ &= e_{n,n-2}(a_1, \dots, a_n) + e_{n-1,n-3}(b_1, \dots, b_{n-2}, b_{n-1} + 1) + 1 \\ &= e_{n,n-2}(a_1, \dots, a_n) + e_{n-1,n-3}(a_1, \dots, a_{n-1}) + 1 \\ &= e_{n,n-2}(a_1, \dots, a_{n-1}, a_n + 1) + 1. \end{aligned}
This proves (2), and the induction is finished. The given condition is equivalent to (1), and thus we are done. \square

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.