Prove that for all integers k>2, there exists k distinct positive integers a1,…,ak such that ∑1≤i<j≤k1aiaj=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, en,k(x1,⋯,xn) will denote the kth elementary symmetric polynomial in the n-variables x1,⋯,xn.
We define a sequence of sets inductively as follows: S3={1,2,3}. Now for n>2, suppose Sn={a1<⋯<an} with a1<⋯<ak. Then Sn+1 is defined to be the set {a1<⋯<an−1<an+1<en,n−1(a1,…,an−1,an+1)}.
Now for Sn={a1<⋯<an}, we will use induction to prove the following two statements:
(1) en,n(a1,…,an)=en,n−2(a1,…,an); and
(2) en,n(a1,…,an−1,an+1)=en,n−2(a1,…,an−1,an+1)+1.
Both of these statements are easy to verify for n=3,4. Now for the induction step, suppose Sn−1={b1<⋯<bn−1}, so that bi=ai for i<n−1 and bn−1=an−1−1. By definition, an=en−1,n−2(a1,…,an−1) Note that
en,n−2(a1,…,an)=en−1,n−2(a1,…,an−1)+anen−1,n−3(a1,…,an−1)=an(1+en−1,n−3(a1,…,an−1))=an(1+en−1,n−3(b1,…,bn−2,bn−1+1))=anen−1,n−1(b1,…,bn−2,bn−1+1)=anen−1,n−1(a1,…,an−1)=en,n(a1,…,an).Here we have used (2) for Sn−1={b1<⋯<bn−1}. This shows (1). Further, we have
en,n(a1,…,an−1,an+1)=en,n(a1,…,an)+en−1,n−1(a1,…,an−1)=en,n−2(a1,…,an)+en−1,n−1(b1,…,bn−2,bn−1+1)=en,n−2(a1,…,an)+en−1,n−3(b1,…,bn−2,bn−1+1)+1=en,n−2(a1,…,an)+en−1,n−3(a1,…,an−1)+1=en,n−2(a1,…,an−1,an+1)+1.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.