Let $a=2001$. Consider the set $A$ of all pairs of integers $(m,n)$ with $n\neq0$ such that (i) $m<2a$; (ii) $2n|(2am-m^2+n^2)$; (iii) $n^2-m^2+2mn\leq2a(n-m)$. For $(m, n)\in A$, let \[f(m,n)=\frac{2am-m^2-mn}{n}.\] Determine the maximum and minimum values of $f$.
Problem
Source: 2001 China National Olmpiad
Tags: modular arithmetic, limit, number theory proposed, number theory
01.06.2014 11:37
Sorry for this huge revival. I think I have a solution. Firstly I think the problem is stated wrongly. We consider positive integers. We show that $\min f(m,n)=2,\max f(m,n)= 3750$ which is attained for $f(2,2000)=2,f(50,52)=3750$. It remains to be seen they satisfy the hypothesis. Now the proof :
13.12.2020 14:35
Yes, the $m$ and $n$ should only consist of positive integers. This problem forces you to look closely through the strange divisibility condition, the absurdly placed $2$ on the left side, and the inequality in relation to $f(m,n)$. Before even tackling the values of $f$, we establish some pre-existing characteristics of $m$ and $n$ that will help us finalize our result. $\color{green} \rule{25cm}{3pt}$ $\color{green} \textbf{\text{Intro.}}$ Given $m$ and $n$ that satisfies everything in the problem condition, this should happen: $n-m$ is divisible by $2$, $n>m$, and $f(m,n)$ is a positive even integer. Chunk 1. If $n$ is odd and $m$ is even, the $RHS$ (i.e. $4002m-m^2+n^2$) is odd. Likewise if $n$ is even and $m$ is odd. Chunk 2. If $m \geq n$, we will derive a contradiction from the inequality in (ii). Moving $n^2-m^2$ to the right side and factoring $(n-m)$ out, we get \[ 2m \leq (n-m) \cdot \dfrac{4002-m-n}{n} \]If $m+n \leq 4002$, then the $RHS$ is nonpositive, contradicting the inequality since the $LHS$ is positive. However, (finally) since $m < 4002$, the value of $\dfrac{4002-m-n}{n}$ must be greater than $-1$, since the absolute value of the numerator (something positive $-n$) is less than the absolute value of the denominator. However, when we manipulate the equation to be in the form \[ \dfrac{2m}{n-m} \geq \dfrac{4002-m-n}{n} \]this immediately yields a contradiction, since the absolute value of the denominator in the $LHS$ is less than $m$, half of its numerator (implying that the fraction's value is less than $-2$.) Chunk 3. First, we know that $2n \mid 4002m-m^2+n^2 + (-mn-n^2)$ because $2 \mid m-n-2m$; from this we can be sure that $2n \mid 4002m-m^2-mn$, implying that $f(m,n)$ is even. Now consider the only thing which can alter the sign of $f(m,n)$, namely $4002-m-n$. If this quantity is negative, then $m+n>4002$. Reverting back to the inequality in Chunk 2, this forces $m > n$, a contradiction. $\blacksquare$ $\color{red}\rule{25cm}{1pt}$ $\color{red} \textbf{\text{Finishing, Part 1.}}$ Consider $f(2,2000)$. We can easily see that this value is equal to $2$, and we have established that $f(m,n) \geq 2$. Then we are done. $\blacksquare$ $\color{magenta}\rule{25cm}{1pt}$ $\color{magenta} \textbf{\text{Finishing, Brute Force Part.}}$ You really do have to know what you're doing before computing the maximum (which we have covered in the green chunks.) Consider the values of $f(n-2,n)$, a computation yields the value to be \[ f(n-2,n) = 4008 - 2n - \dfrac{8008}{n} \]to minimize this value, $n$ must be as close as possible to the "equality case" of $n = \sqrt{4004}$. We can quickly check that $n = 52$ is the best candidate for this, yielding $f(50,52) = 3750$. And, leap of faith! For all $n - m \geq 4$, we can show that the value of $f(m,n)$ (regardless of it satisfying the second condition or not, and whether $n$ is actually an integer!) to be less than $3750$. A slightly contrived computation of setting $m = n-k$ yields \[ f(m,n) = 4002+3k - \dfrac{(4002+k)k}{n} - 2n \]which attains its minimum at $4002+3k - 2 \cdot \sqrt{(8004+2k)k}$. Wishing to show that this value is less than $3750$ for $k \geq 4$, the appropriate manipulation yields the final inequality \[ k^2-30504k+63504 < 0 \]which is true for $k \in [4,30000]$. Since $m+n < 4002$ by the inequality in Chunk 2, $n-m$ is obviously less than $30000$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$