Maths Olympiad Prep

Library / /48 of 56

Number theory Difficulty 6.3 National Olympiad Prove it Singapore

Find the smallest positive integer nn, or show no such nn exists, such that one can find infinitely many distinct nn-tuplets of positive rationals (a1,a2,,an)(a_1, a_2, \dots, a_n) satisfying:
i=1naiZ,i=1n1aiZ. \sum_{i=1}^{n} a_i \in \mathbb{Z}, \quad \sum_{i=1}^{n} \frac{1}{a_i} \in \mathbb{Z}.

Solution

The smallest such nn is n=3n=3. For n=2n=2, let a1=aba_1 = \frac{a}{b}, a2=cda_2 = \frac{c}{d} where gcd(a,b)=gcd(c,d)=1\gcd(a,b) = \gcd(c,d) = 1. Then we must have bdad+bcbd \mid ad+bc, acad+bcac \mid ad+bc. Taking mod dd in the first condition, we get that dbcd \mid bc but since c,dc,d are coprime we have that dbd|b. Taking mod bb, we get badb \mid ad and since a,ba,b are coprime we get bdb \mid d which tells us that b=db=d. Similarly we get a=ca=c and hence we have a1=a2a_1=a_2. Clearly only a1=a2=1a_1=a_2=1 or 12\frac{1}{2} works and we only have finitely many such duplets.

Now for n=3n=3, we will look for triplets of the form (aa+b+c,ba+b+c,ca+b+c)(\frac{a}{a+b+c}, \frac{b}{a+b+c}, \frac{c}{a+b+c}) where a,b,ca,b,c are positive integers. Fixing a=1a=1, it suffices to find infinitely many pairs of (b,c)(b,c) such that 1b+1c+bc+cb\frac{1}{b}+\frac{1}{c}+\frac{b}{c}+\frac{c}{b} is an integer. We shall show that there are infinitely many solutions to 1b+1c+bc+cb=3\frac{1}{b}+\frac{1}{c}+\frac{b}{c}+\frac{c}{b}=3 by Vieta Jumping. If we let cbc \ge b, the equation rearranges into b2b(3c1)+c2+c=0b^2-b(3c-1)+c^2+c=0. Viewing it as a quadratic in bb, we get that there exists another bb' satisfying 1b+1c+bc+cb=3\frac{1}{b'}+\frac{1}{c}+\frac{b'}{c}+\frac{c}{b'}=3 and that this bb' satisfies b+b=3c1b'+b' = 3c-1, bb=c2+cbb' = c^2+c. Since bb is a positive integer, we get that b=3c1bb' = 3c-1-b is also a positive integer. Furthermore, b=c2+cbc2+cc>cb' = \frac{c^2+c}{b} \ge \frac{c^2+c}{c} > c. Hence our triplet (1,b,c)(1,b,c) will transform into another triplet (1,c,b)(1,c,b') where b>cb' > c and we can then jump again but this time with cc as the subject of the quadratic. Starting with b=3,c=6b=3, c=6, this algorithm will generate infinitely many distinct triplets of desired positive integers (a,b,c)(a,b,c) which will then give us infinitely many distinct triplets of rationals satisfying the problem conditions.

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.