Maths Olympiad Prep

Library / China Mathematical Competition (Complementary Test) /12 of 17

China Mathematical Competition (Complementary Test)

Number theory Difficulty 6.5 National Olympiad Prove it China

Prove for any integer n≥4n \ge 4, there exists a polynomial of degree nn,
f(x)=xn+an−1xn−1+⋯+a1x+a0 f(x) = x^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0
with the following properties.
(1) a0,a1,…,an−1a_0, a_1, \dots, a_{n-1} are all positive integers;
(2) For any positive integer mm and arbitrary kk (k≥2k \ge 2) positive integers r1,r2,…,rkr_1, r_2, \dots, r_k that are different from each other, we have
f(m)≠f(r1)f(r2)⋯f(rk). f(m) \neq f(r_1)f(r_2)\cdots f(r_k).

Solution

Let
f(x)=(x+1)(x+2)⋯(x+n)+2.1◯ f(x) = (x+1)(x+2)\cdots(x+n)+2. \qquad \textcircled{1}
Obviously, f(x)f(x) is a monic polynomial of degree nn with positive integer coefficients. We are going to prove that f(x)f(x) has property (2).
For any integer tt, since n≥4n \ge 4, we know that there exists definitely a multiple of 4 in any nn consecutive numbers t+1,t+2,…,t+nt+1, t+2, \dots, t+n. Then from 1◯\textcircled{1}, we have f(t)≡2(mod4)f(t) \equiv 2 \pmod 4.
Then for any kk (k≥2k \ge 2) positive integers r1,r2,…,rkr_1, r_2, \dots, r_k, we have
f(r1)f(r2)⋯f(rk)≡2k≡0(mod4). f(r_1)f(r_2)\cdots f(r_k) \equiv 2^k \equiv 0 \pmod 4.
On the other hand, for any positive integer mm, we have
f(m)≡2(mod4)f(m) \equiv 2 \pmod{4}. Therefore,
f(m)≢f(r1)f(r2)⋯f(rk)(mod4), f(m) \not\equiv f(r_1)f(r_2)\cdots f(r_k) \pmod{4},
which implies that f(m)≠f(r1)f(r2)⋯f(rk)f(m) \neq f(r_1)f(r_2)\cdots f(r_k). We then find the required f(x)f(x) and complete the proof. □\square

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.