Prove that for all integers $k>2$, there exists $k$ distinct positive integers $a_1, \dots, a_k$ such that $$\sum_{1 \le i<j \le k} \frac{1}{a_ia_j} =1.$$ Proposed by Anant Mudgal
Problem
Source: India TST 2023 Practice Test 1 P3
Tags: algebra
Ankoganit
11.07.2023 10:51
Extremely cursed problem. Here's what I came up with — if someone knows a better construction, please post it and restore my faith in symmetric polynomials.
We'll replace $k$ with $n$ so that I don't have to fix my original write-up. Let us first introduce some notation: given positive integers $n$ and $k$, $e_{n,k}(x_1,\cdots, x_n)$ will denote the $k$th elementary symmetric polynomial in the $n$-variables $x_1,\cdots, x_n$.
We define a sequence of sets inductively as follows: $S_3=\{1,2,3\}$. Now for $n>2$, suppose $S_n=\{a_1<\cdots< a_n\}$ with $a_1<\cdots<a_k$. Then $S_{n+1}$ is defined to be the set $$\{a_1<\cdots<a_{n-1}<a_n+1<e_{n,n-1}(a_1,\ldots, a_{n-1},a_{n}+1)\}.$$
Now for $S_n=\{a_1<\cdots< a_n\}$, we will use induction to prove the following two statements:
(1) $e_{n,n}(a_1,\ldots, a_n)=e_{n,n-2}(a_1,\ldots, a_n)$; and
(2) $e_{n,n}(a_1,\ldots, a_{n-1},a_n+1)=e_{n,n-2}(a_1,\ldots, a_{n-1},a_n+1)+1$.
Both of these statements are easy to verify for $n=3,4$. Now for the induction step, suppose $S_{n-1}=\{b_1<\cdots<b_{n-1}\}$, so that $b_i=a_i$ for $i<n-1$ and $b_{n-1}=a_{n-1}-1$. By definition, $a_n=e_{n-1,n-2}(a_1,\ldots, a_{n-1})$ Note that
\begin{align*}
e_{n,n-2}(a_1,\ldots, a_n)&=e_{n-1,n-2}(a_1,\ldots, a_{n-1})+a_ne_{n-1,n-3}(a_1,\ldots,a_{n-1})\\
&=a_n(1+e_{n-1,n-3}(a_1,\ldots, a_{n-1}))=a_n(1+e_{n-1,n-3}(b_1,\ldots, b_{n-2},b_{n-1}+1))\\
&=a_ne_{n-1,n-1}(b_1,\ldots, b_{n-2},b_{n-1}+1)=a_ne_{n-1,n-1}(a_1,\ldots,a_{n-1})\\
&=e_{n,n}(a_1,\ldots, a_n).
\end{align*}Here we have used $(2)$ for $S_{n-1}=\{b_1<\cdots<b_{n-1}\}$. This shows (1). Further, we have
\begin{align*}
e_{n,n}(a_1,\ldots, a_{n-1},a_{n}+1)&=e_{n,n}(a_1,\ldots, a_n)+e_{n-1,n-1}(a_1,\ldots, a_{n-1})\\
&=e_{n,n-2}(a_1,\ldots, a_n)+e_{n-1,n-1}(b_1,\ldots, b_{n-2},b_{n-1}+1)\\
&=e_{n,n-2}(a_1,\ldots, a_n)+e_{n-1,n-3}(b_1,\ldots, b_{n-2},b_{n-1}+1)+1\\
&=e_{n,n-2}(a_1,\ldots, a_n)+e_{n-1,n-3}(a_1,\ldots, a_{n-1})+1\\
&=e_{n,n-2}(a_1,\ldots, a_{n-1},a_n+1)+1.
\end{align*}This proves (2), and the induction is finished. The given condition is equivalent to (1), and thus we are done.
Safal
11.07.2023 11:32
@Ankoganit, Very Beautiful. @Aops, I want to know who proposed this, because I want to know how he/she came up with the motivation of making this problem.