Maths Olympiad Prep

Library / /2 of 16

Combinatorics Difficulty 8.0 National olympiad, round 2 Prove it IMO

A positive integer NN is called balanced, if N=1N=1 or if NN can be written as a product of an even number of not necessarily distinct primes. Given positive integers aa and bb, consider the polynomial PP defined by P(x)=(x+a)(x+b)P(x)=(x+a)(x+b).

a. Prove that there exist distinct positive integers aa and bb such that all the numbers P(1),P(2),,P(50)P(1), P(2), \ldots, P(50) are balanced.

b. Prove that if P(n)P(n) is balanced for all positive integers nn, then a=ba=b.

Solution

Define a function ff on the set of positive integers by f(n)=0f(n)=0 if nn is balanced and f(n)=1f(n)=1 otherwise. Clearly, f(nm)f(n)+f(m)mod2f(n m) \equiv f(n)+f(m) \bmod 2 for all positive integers n,mn, m.

a. Now for each positive integer nn consider the binary sequence (f(n+1),f(n+2),,f(n+50))(f(n+1), f(n+2), \ldots, f(n+50)). As there are only 2502^{50} different such sequences there are two different positive integers aa and bb such that
(f(a+1),f(a+2),,f(a+50))=(f(b+1),f(b+2),,f(b+50)). (f(a+1), f(a+2), \ldots, f(a+50))=(f(b+1), f(b+2), \ldots, f(b+50)).
But this implies that for the polynomial P(x)=(x+a)(x+b)P(x)=(x+a)(x+b) all the numbers P(1),P(2),,P(50)P(1), P(2), \ldots, P(50) are balanced, since for all 1k501 \leq k \leq 50 we have f(P(k))f(a+k)+f(b+k)2f(a+k)0mod2f(P(k)) \equiv f(a+k)+f(b+k) \equiv 2 f(a+k) \equiv 0 \bmod 2.

b. Now suppose P(n)P(n) is balanced for all positive integers nn and a<ba<b. Set n=k(ba)an=k(b-a)-a for sufficiently large kk, such that nn is positive. Then P(n)=k(k+1)(ba)2P(n)=k(k+1)(b-a)^2, and this number can only be balanced, if f(k)=f(k+1)f(k)=f(k+1) holds. Thus, the sequence f(k)f(k) must become constant for sufficiently large kk. But this is not possible, as for every prime pp we have f(p)=1f(p)=1 and for every square t2t^2 we have f(t2)=0f\left(t^2\right)=0.
Hence a=ba=b.

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.