Maths Olympiad Prep

Library / /45 of 299

Algebra Difficulty 5.8 AIME, harder Prove it Iran

Let nNn \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 0kn0 \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 axnymg(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)mapnqmn    p100mnan+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,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.