Maths Olympiad Prep

Library / /1 of 4

Number theory Difficulty 5.5 AIME, harder Prove it Romania

Let aa and bb be two distinct positive integers having the same parity.
Prove that a!+b!2a\frac{a!+b!}{2^a} is not an integer (note: n!=12nn! = 1 \cdot 2 \cdot \dots \cdot n, for any positive integer nn).

Solution

First, we prove that for any positive integer nn, 2n2^n is not a divisor of n!n!.
Assume the opposite; then, in the prime factorization of n!n! there should be at least nn factors equal to 22. The exponent of 22 in n!n! is equal to n2+n22++n2k\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{2^2} \rfloor + \dots + \lfloor \frac{n}{2^k} \rfloor, where kNk \in \mathbb{N}^*, k<nk < n, n2k0\lfloor \frac{n}{2^k} \rfloor \ne 0 and n2k+1=0\lfloor \frac{n}{2^{k+1}} \rfloor = 0. It follows that n2+n22++n2kn2+n22++n2kn\frac{n}{2} + \frac{n}{2^2} + \dots + \frac{n}{2^k} \ge \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{2^2} \rfloor + \dots + \lfloor \frac{n}{2^k} \rfloor \ge n.
Then n2+n22++n2kn\frac{n}{2} + \frac{n}{2^2} + \dots + \frac{n}{2^k} \ge n, so 112k11 - \frac{1}{2^k} \ge 1, which is false.

If ab+2a \ge b+2, then a!+b!=b!(1+(b+1)(b+2)a)=n2aa! + b! = b! \cdot (1 + (b+1) \cdot (b+2) \cdot \dots \cdot a) = n \cdot 2^a and, since 1+(b+1)(b+2)b1 + (b+1) \cdot (b+2) \cdot \dots \cdot b is odd, we get 2ab!2^a \mid b!. But b!a!b! \mid a!, so 2aa!2^a \mid a!, which is false.

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.