Maths Olympiad Prep

Library / Singapore Mathematical Olympiad (SMO) /44 of 52

Singapore Mathematical Olympiad (SMO)

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=1nai∈Z,∑i=1n1ai∈Z. \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 bd∣ad+bcbd \mid ad+bc, ac∣ad+bcac \mid ad+bc. Taking mod dd in the first condition, we get that d∣bcd \mid bc but since c,dc,d are coprime we have that d∣bd|b. Taking mod bb, we get b∣adb \mid ad and since a,ba,b are coprime we get b∣db \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 c≥bc \ge b, the equation rearranges into b2−b(3c−1)+c2+c=0b^2-b(3c-1)+c^2+c=0. Viewing it as a quadratic in bb, we get that there exists another b′b' satisfying 1b′+1c+b′c+cb′=3\frac{1}{b'}+\frac{1}{c}+\frac{b'}{c}+\frac{c}{b'}=3 and that this b′b' satisfies b′+b′=3c−1b'+b' = 3c-1, bb′=c2+cbb' = c^2+c. Since bb is a positive integer, we get that b′=3c−1−bb' = 3c-1-b is also a positive integer. Furthermore, b′=c2+cb≥c2+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.