Maths Olympiad Prep

Library / /6 of 24

, 2015

Number theory Difficulty 6.0 AIME, harder Prove it Argentina

Find all nNn \in \mathbb{N} that can be represented in the form n=[a,b]+[b,c]+[c,a]n = [a,b] + [b,c] + [c,a] with a,b,cNa, b, c \in \mathbb{N}. Here denotes the least common multiple of uu and vv.

Solution

All nNn \in \mathbb{N} are representable except the powers of 22. Set f(a,b,c)=[a,b]+[b,c]+[c,a]f(a,b,c) = [a,b] + [b,c] + [c,a]. Take an arbitrary kNk \in \mathbb{N} and let a=ka = k, b=c=1b = c = 1 to obtain f(k,1,1)=2k+1f(k,1,1) = 2k + 1. Hence all odd nn, n3n \ge 3, are representable. If nn is representable then so is 2n2n

because [2u,2v]=2[2u, 2v] = 2 implies f(2a,2b,2c)=2f(a,b,c)f(2a, 2b, 2c) = 2f(a, b, c). So each n3n \ge 3 is representable if it has an odd divisor greater than 11.
There remain the powers 2k2^k of 22, with k0k \ge 0. We show that they are not representable. This is true for k=0,1k = 0, 1 since clearly f(a,b,c)3f(a,b,c) \ge 3 for all a,b,cNa, b, c \in \mathbb{N}. Suppose that f(a,b,c)=2kf(a,b,c) = 2^k with k2k \ge 2. Consider the least kk with this property. Observe that at least two numbers among a,b,ca, b, c are even. Otherwise f(a,b,c)f(a,b,c) is odd while 2k2^k is even. If a,b,ca, b, c are all even, they can be divided by 22 to yield f(a2,b2,c2)=2k1f\left(\frac{a}{2}, \frac{b}{2}, \frac{c}{2}\right) = 2^{k-1}, which contradicts the minimality of kk. Hence one may assume that a,ba, b are even and cc is odd. Here [a,b]=2[a2,b2][a,b] = 2\left[\frac{a}{2}, \frac{b}{2}\right]. Note also that
[a,c]=2[a2,c] holds because a is even and c is odd. [a,c] = 2\left[\frac{a}{2}, c\right] \text{ holds because } a \text{ is even and } c \text{ is odd.}
Analogously [b,c]=2[b2,c][b,c] = 2\left[\frac{b}{2}, c\right]. It follows that
f(a2,b2,c)=12f(a,b,c)=2k1, contradicting the minimality of k again. f\left(\frac{a}{2}, \frac{b}{2}, c\right) = \frac{1}{2} f(a, b, c) = 2^{k-1}, \text{ contradicting the minimality of } k \text{ again.}

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 and solution reproduced as published; topic and difficulty added by this site.