Maths Olympiad Prep

Library / /300 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

Find the smallest positive integer nn, or show that no such nn exists, with the following property: there are infinitely many distinct nn-tuples of positive rational numbers (a1,a2,,an)\left(a_{1}, a_{2}, \ldots, a_{n}\right) such that both
a1+a2++an and 1a1+1a2++1an a_{1}+a_{2}+\cdots+a_{n} \quad \text { and } \quad \frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}
are integers. (Singapore) Answer: n=3n=3.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

For n=1,a1Z>0n=1, a_{1} \in \mathbb{Z}_{>0} and 1a1Z>0\frac{1}{a_{1}} \in \mathbb{Z}_{>0} if and only if a1=1a_{1}=1. Next we show that (i) There are finitely many (x,y)Q>02(x, y) \in \mathbb{Q}_{>0}^{2} satisfying x+yZx+y \in \mathbb{Z} and 1x+1yZ\frac{1}{x}+\frac{1}{y} \in \mathbb{Z}. Write x=abx=\frac{a}{b} and y=cdy=\frac{c}{d} with a,b,c,dZ>0a, b, c, d \in \mathbb{Z}_{>0} and gcd(a,b)=gcd(c,d)=1\operatorname{gcd}(a, b)=\operatorname{gcd}(c, d)=1. Then x+yZx+y \in \mathbb{Z} and 1x+1yZ\frac{1}{x}+\frac{1}{y} \in \mathbb{Z} is equivalent to the two divisibility conditions
bdad+bc(1) and acad+bc b d \mid a d+b c \quad(1) \quad \text { and } \quad a c \mid a d+b c
Condition (1) implies that dad+bcdbcdbd|a d+b c \Longleftrightarrow d| b c \Longleftrightarrow d \mid b since gcd(c,d)=1\operatorname{gcd}(c, d)=1. Still from (1) we get bad+bcbadbdb|a d+b c \Longleftrightarrow b| a d \Longleftrightarrow b \mid d since gcd(a,b)=1\operatorname{gcd}(a, b)=1. From bdb \mid d and dbd \mid b we have b=db=d. An analogous reasoning with condition (2) shows that a=ca=c. Hence x=ab=cd=yx=\frac{a}{b}=\frac{c}{d}=y, i.e., the problem amounts to finding all xQ>0x \in \mathbb{Q}_{>0} such that 2xZ>02 x \in \mathbb{Z}_{>0} and 2xZ>0\frac{2}{x} \in \mathbb{Z}_{>0}. Letting n=2xZ>0n=2 x \in \mathbb{Z}_{>0}, we have that 2xZ>04nZ>0n=1,2\frac{2}{x} \in \mathbb{Z}_{>0} \Longleftrightarrow \frac{4}{n} \in \mathbb{Z}_{>0} \Longleftrightarrow n=1,2 or 4, and there are finitely many solutions, namely (x,y)=(12,12),(1,1)(x, y)=\left(\frac{1}{2}, \frac{1}{2}\right),(1,1) or (2,2)(2,2). (ii) There are infinitely many triples (x,y,z)Q>02(x, y, z) \in \mathbb{Q}_{>0}^{2} such that x+y+zZx+y+z \in \mathbb{Z} and 1x+1y+1zZ\frac{1}{x}+\frac{1}{y}+\frac{1}{z} \in \mathbb{Z}. We will look for triples such that x+y+z=1x+y+z=1, so we may write them in the form
(x,y,z)=(aa+b+c,ba+b+c,ca+b+c) with a,b,cZ>0 (x, y, z)=\left(\frac{a}{a+b+c}, \frac{b}{a+b+c}, \frac{c}{a+b+c}\right) \quad \text { with } a, b, c \in \mathbb{Z}_{>0}
We want these to satisfy
1x+1y+1z=a+b+ca+a+b+cb+a+b+ccZb+ca+a+cb+a+bcZ \frac{1}{x}+\frac{1}{y}+\frac{1}{z}=\frac{a+b+c}{a}+\frac{a+b+c}{b}+\frac{a+b+c}{c} \in \mathbb{Z} \Longleftrightarrow \frac{b+c}{a}+\frac{a+c}{b}+\frac{a+b}{c} \in \mathbb{Z}
Fixing a=1a=1, it suffices to find infinitely many pairs (b,c)Z>02(b, c) \in \mathbb{Z}_{>0}^{2} such that
1b+1c+cb+bc=3b2+c23bc+b+c=0 \frac{1}{b}+\frac{1}{c}+\frac{c}{b}+\frac{b}{c}=3 \Longleftrightarrow b^{2}+c^{2}-3 b c+b+c=0
To show that equation (*) has infinitely many solutions, we use Vieta jumping (also known as root flipping): starting with b=2,c=3b=2, c=3, the following algorithm generates infinitely many solutions. Let cbc \geqslant b, and view (*) as a quadratic equation in bb for cc fixed:
b2(3c1)b+(c2+c)=0 b^{2}-(3 c-1) \cdot b+\left(c^{2}+c\right)=0
Then there exists another root b0Zb_{0} \in \mathbb{Z} of ( )\left.* *\right) which satisfies b+b0=3c1b+b_{0}=3 c-1 and bb0=c2+cb \cdot b_{0}=c^{2}+c. Since cbc \geqslant b by assumption,
b0=c2+cbc2+cc>c b_{0}=\frac{c^{2}+c}{b} \geqslant \frac{c^{2}+c}{c}>c
Hence from the solution (b,c)(b, c) we obtain another one (c,b0)\left(c, b_{0}\right) with b0>cb_{0}>c, and we can then "jump" again, this time with cc as the "variable" in the quadratic (*). This algorithm will generate an infinite sequence of distinct solutions, whose first terms are (2,3),(3,6),(6,14),(14,35),(35,90),(90,234),(234,611),(611,1598),(1598,4182),(2,3),(3,6),(6,14),(14,35),(35,90),(90,234),(234,611),(611,1598),(1598,4182), \ldots
Comment. Although not needed for solving this problem, we may also explicitly solve the recursion given by the Vieta jumping. Define the sequence (xn)\left(x_{n}\right) as follows:
x0=2,x1=3 and xn+2=3xn+1xn1 for n0 x_{0}=2, \quad x_{1}=3 \quad \text { and } \quad x_{n+2}=3 x_{n+1}-x_{n}-1 \text { for } n \geqslant 0
Then the triple
(x,y,z)=(11+xn+xn+1,xn1+xn+xn+1,xn+11+xn+xn+1) (x, y, z)=\left(\frac{1}{1+x_{n}+x_{n+1}}, \frac{x_{n}}{1+x_{n}+x_{n+1}}, \frac{x_{n+1}}{1+x_{n}+x_{n+1}}\right)
satisfies the problem conditions for all nNn \in \mathbb{N}. It is easy to show that xn=F2n+1+1x_{n}=F_{2 n+1}+1, where FnF_{n} denotes the nn-th term of the Fibonacci sequence ( F0=0,F1=1F_{0}=0, F_{1}=1, and Fn+2=Fn+1+FnF_{n+2}=F_{n+1}+F_{n} for n0n \geqslant 0 ).

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.