Maths Olympiad Prep

Library / /214 of 520

Number theory Difficulty 6.3 National olympiad Prove it

Let aa and bb be positive integers such that a!b!a!b! is a multiple of a!+b!a!+b!. Prove that 3a2b+23a \geqslant 2b+2. (United Kingdom)

Solution

If a>ba>b, we immediately get 3a2b+23a \geqslant 2b+2. In the case a=ba=b, the required inequality is equivalent to a2a \geqslant 2, which can be checked easily since (a,b)=(1,1)(a, b)=(1,1) does not satisfy a!+b!a!b!a!+b! \mid a!b!. We now assume a>ba > b. We observe that c!Mc! \mid M since MM is a product of cc consecutive integers. Thus gcd(1+M,c!)=1\operatorname{gcd}(1+M, c!)=1, which implies
1+Ma!c!=(c+1)(c+2)a 1+M \left\lvert\, \frac{a!}{c!}=(c+1)(c+2) \cdots a\right.
If a2ca \leqslant 2c, then a!c!\frac{a!}{c!} is a product of acca-c \leqslant c integers not exceeding aa whereas MM is a product of cc integers exceeding aa. Therefore, 1+M>a!c!1+M>\frac{a!}{c!}, which is a contradiction.
It remains to exclude the case a=2c+1a=2c+1. Since a+1=2(c+1)a+1=2(c+1), we have c+1Mc+1 \mid M. Hence, we can deduce from (1) that 1+M(c+2)(c+3)a1+M \mid (c+2)(c+3) \cdots a. Now (c+2)(c+3)a(c+2)(c+3) \cdots a is a product of ac1=ca-c-1=c integers not exceeding aa; thus it is smaller than 1+M1+M. Again, we arrive at a contradiction.
Comment 1. One may derive a weaker version of (1) and finish the problem as follows. After assuming a2c+1a \leqslant 2c+1, we have a2c\left\lfloor\frac{a}{2}\right\rfloor \leqslant c, so a2!M\left.\left\lfloor\frac{a}{2}\right\rfloor!\right\rvert\, M. Therefore,
1+M(a2+1)(a2+2)a 1+M \left\lvert\,\left(\left\lfloor\frac{a}{2}\right\rfloor+1\right)\left(\left\lfloor\frac{a}{2}\right\rfloor+2\right) \cdots a\right.
Observe that (a2+1)(a2+2)a\left(\left\lfloor\frac{a}{2}\right\rfloor+1\right)\left(\left\lfloor\frac{a}{2}\right\rfloor+2\right) \cdots a is a product of a2\left\lceil\frac{a}{2}\right\rceil integers not exceeding aa. This leads to a contradiction when aa is even since a2=a2c\left\lceil\frac{a}{2}\right\rceil=\frac{a}{2} \leqslant c and MM is a product of cc integers exceeding aa.
When aa is odd, we can further deduce that 1+M(a+32)(a+52)a1+M \left\lvert\,\left(\frac{a+3}{2}\right)\left(\frac{a+5}{2}\right) \cdots a\right. since a2+1=a+12a+1\left.\left\lfloor\frac{a}{2}\right\rfloor+1=\frac{a+1}{2} \right\rvert\, a+1. Now (a+32)(a+52)a\left(\frac{a+3}{2}\right)\left(\frac{a+5}{2}\right) \cdots a is a product of a12c\frac{a-1}{2} \leqslant c numbers not exceeding aa, and we get a contradiction.

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.