Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /39 of 270

Iranian Mathematical Olympiad

Algebra Difficulty 5.8 AIME, harder Prove it Iran

Let n∈Nn \in \mathbb{N} be a positive integer. We call a function f(x,y)f(x, y) a friend of nn if for at least one percent of positive integers kk such that 0≤k≤n0 \le k \le n the equation f(x,y)=kf(x, y) = k has a solution (x0,y0)(x_0, y_0) in positive integers such that y0x0∈[1100,100]\frac{y_0}{x_0} \in [\frac{1}{100}, 100]. Let g(x,y)g(x, y) be a polynomial with non-negative real coefficients of total degree greater than 22 such that g(x,y)≤f(x,y)g(x, y) \le f(x, y), for all positive real numbers x,yx, y satisfying yx∈[1100,100]\frac{y}{x} \in [\frac{1}{100}, 100]. Prove that f(x,y)f(x, y) would not be a friend of nn for all sufficiently large nn.

Solution

First, note that given the positive coefficients, if axmyna x^m y^n is the highest degree term appearing in gg, we have axnym≤g(x,y)a x^n y^m \le g(x, y). Therefore, if f(p,q)=k<nf(p, q) = k < n and (p,q)(p, q) are in the specified region, we have:
apn(p100)m≤apnqm≤n  ⟹  p≤100mnan+m a p^n \left(\frac{p}{100}\right)^m \le a p^n q^m \le n \implies p \le \sqrt[n+m]{\frac{100^m n}{a}}
Therefore, for some constant cc, we have p,q<cn1n+mp, q < c n^{\frac{1}{n+m}}, which implies that (p,q)(p, q) can have at most cn2n+mc n^{\frac{2}{n+m}} possibilities, which is a 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.