Maths Olympiad Prep

Library / CMO /13 of 22

CMO, 2023

Algebra Difficulty 6.6 National Olympiad Prove it Canada

Problem:
Let f(x)f(x) be a non-constant polynomial with integer coefficients such that f(1)≠1f(1) \neq 1. For a positive integer nn, define divs⁡(n)\operatorname{divs}(n) to be the set of positive divisors of nn.
A positive integer mm is ff-cool if there exists a positive integer nn for which
f[divs⁡(m)]=divs⁡(n) f[\operatorname{divs}(m)]=\operatorname{divs}(n)
Prove that for any such ff, there are finitely many ff-cool integers.
(The notation f[S]f[S] for some set SS denotes the set {f(s):s∈S}\{f(s): s \in S\}.)

Solution

Solution:
Assume for the sake of contradiction that there are infinitely many ff-cool integers.
If f(x)f(x) has a negative leading coefficient, then a sufficiently large ff-cool integer mm will have f(m)<0f(m)<0. But this implies mm is not ff-cool, contradiction.
Thus f(x)f(x) has a positive leading coefficient, so we can pick an NN such that for all m>Nm>N,
f(m)>max⁡(f(1),f(2),…,f(m−1)) f(m)>\max (f(1), f(2), \ldots, f(m-1))
This means f(m)f(m) is the largest value in f[divs⁡(m)]f[\operatorname{divs}(m)], so if mm is ff-cool with f[divs⁡(m)]=divs⁡(n)f[\operatorname{divs}(m)]=\operatorname{divs}(n), then we must have n=f(m)n=f(m), since nn is the largest value in divs⁡(n)\operatorname{divs}(n). In other words,
f[divs⁡(m)]=divs⁡(f(m)) f[\operatorname{divs}(m)]=\operatorname{divs}(f(m))
for all ff-cool m>Nm>N.
For each of those mm's, 1∈divs⁡(f(m))1 \in \operatorname{divs}(f(m)), so there must be a k∈divs⁡(m)k \in \operatorname{divs}(m) such that f(k)=1f(k)=1. Let k1,k2,…,knk_{1}, k_{2}, \ldots, k_{n} be the solutions to f(x)=1f(x)=1. Thus every ff-cool m>Nm>N is divisible by some k∈{k1,k2,…,kn}k \in\left\{k_{1}, k_{2}, \ldots, k_{n}\right\}. Since there are infinitely many such mm's and finitely many kk's, by the Pigeonhole Principle there is some kk which divides infinitely many ff-cool integers mm. (Note that k≠1k \neq 1 since f(1)≠1f(1) \neq 1.)
For all ff-cool m>Nm>N divisible by kk, we have
f(mk)∈f[divs⁡(m)]=divs⁡(f(m))⟹f(mk)∣ f(m). \left.f\left(\frac{m}{k}\right) \in f[\operatorname{divs}(m)]=\operatorname{divs}(f(m)) \Longrightarrow f\left(\frac{m}{k}\right) \right\rvert\, f(m) .
Thus, f(x)∣f(kx)f(x) \mid f(k x) has infinitely many positive integer solutions. Let d=deg⁡(f)d=\operatorname{deg}(f), and write
f(kx)f(x)=kd+g(x)f(x) \frac{f(k x)}{f(x)}=k^{d}+\frac{g(x)}{f(x)}
for some g(x)∈Z[x]g(x) \in \mathbb{Z}[x] with deg⁡(g)<d\operatorname{deg}(g)<d. If g(x)≠0g(x) \neq 0, then for sufficiently large xx we have 0<∣g(x)∣<f(x)0<|g(x)|<f(x), since deg⁡(f)>deg⁡(g)\operatorname{deg}(f)>\operatorname{deg}(g). But then f(kx)f(x)−kd=g(x)f(x)\frac{f(k x)}{f(x)}-k^{d}=\frac{g(x)}{f(x)} cannot be an integer, which gives us the desired contradiction.
Therefore g(x)=0g(x)=0, so f(kx)=kdf(x)f(k x)=k^{d} f(x), i.e. f(x)=axdf(x)=a x^{d} for some positive integer aa. If a=1a=1 then f(1)=1f(1)=1, a contradiction. But if a>1a>1, then f(x)=1f(x)=1 has no integer solutions, another contradiction.

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.