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
joybangla
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 :
From (ii) we have $\frac{2am-m^2+n^2}{2n}=\ell \in\mathbb{Z}\implies n(2\ell-n)=m(2a-m)\ldots(*)$. Thus $m\equiv n\pmod 2$.
Now \begin{align*} \ell & =\frac{(2am-2mn)+(n^2-m^2+2mn)}{2n}\\ &\le \frac{(2am-2mn)+2a(n-m)}{2n}\quad(\text{Using (iii) })\\ &=a-m \end{align*}
Now from this we have :
\[ 2\ell -n<2\ell \le 2a-2m <2a-m \] using this and $(*)$ we conclude $n>m$. Also we have from (iii) that :
\[ 2mn\le 2a(n-m)-(n^2-m^2)\implies (n-m)(2a-n-m) \]
Thus we have $2a-n-m>0$. From this we $f(m,n)=\frac{m(2a-m-n)}{n} >0$
Anyways thus we have than $f(m,n)=2\ell-(m+n)\equiv 0\pmod 2$ and $f(m,n)>0$. Thus we conclude $f(m,n)\ge 2$ and the equality indeed holds as mentioned in the beginning.
Now consider
\begin{align*} f(n-2,n)&=\frac{2a(n-2)-(n-2)^2-n(n-2)}{n}\\ &=2a+6-2\left(n+\frac{4004}{n}\right) \end{align*}
Now obviously to maximise this we need to minimise $n+\frac{4004}{n}$. For this we need to choose $n\mid 4004$ such that $n$ and $\frac{4004}{n}$ are as close as possible. See two possible candidates are $n=52,77$. But see $(50,52)\in A$ but $(75,77)\not\in A$. So we have $f(50,52)=3750$. Now since we know $n>m$ and $m\equiv n \pmod 2$ it suffices to prove that for $n\ge m+4$, we have $f(m,n)<3750$.
Now we proceed with that.
\begin{align*} f(m,n)&=\frac{(2a-m)m}{n}-m\\ &\le \frac{(2a-m)m}{m+4}-m\\ &=3998-\left(2(m+4)+\frac{16024}{m+4}\right)\\ &\le 3998-\left2\sqrt{32048}\\ &<3998-2(179)\\ &<3640 \end{align*}
If my arithmetic is right then we are done. $\blacksquare$
First assume $A$ contains positive as well as negative integers. We show $\min f=-\infty$. Consider a sequence of positive integers $\{a_n\}_{n=0}^{\infty}$ such that $\lim_{n\to \infty}a_n=+\infty$. Now take $(m_k,n_k)=(-2a_k,2)$. We show that $(m_k,n_k)\in A\;\forall k$.
For part (i) - $m<0<2a$
For part (ii) -
\begin{align*} &2n\mid (2am-m^2+n^2)\\ & \iff 4\mid (4a-4a_k^2+4)\end{align*} which is obviously true.
For part (iii) -
\begin{align*} & (n^2-m^2+2mn)\le 2a(n-m)\\ &\iff (4-4a_k^2-4a_k)\le 2a(2+2a_k)\\ &\iff a_k^2+a_k(a+1)+(a+1)\ge 0 \end{align*} which is obviously true.
Thus $(m_k,n_k)\in A$. Now consider
\begin{align*}f(m_k,n_k) &=\frac{-4aa_k-4a_k^2+4a_k}{4}\\ &=-(a_k^2+(a-1)a_k) \end{align*}
Which obviously goes to negative infinity since $a_k$ goes to infinity. So $f$ has no minimum. So the problem becomes trivialized vastly even for one part if we consider integers in $A$. So positive integers is what it should be. Hope my justification is correct. But I do not have any example for $\max f =+\infty$. And sorry for making this huge.
alexiaslexia
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$
While it may seem that there's a lot to cover here, there really isn't so much "hidden stuff" which is invisible in the solution. The conditions itself are one of the most contrived and artificial I've seen (recently) --- and how to handle them is (hopefully) is already presented clearly.
Playing the devil's advocate for a bit here, considering $n-m$ to be divisible by $2$, and bounding $n-m$ itself to be greater than zero might not be an obvious thing in the first read, but stay with me here. Naturally, (at first glance) the maximum should occur when the denominator is $n = 1$ (bonus: $2 \cdot 1$ should be divisible by $\textit{almost every number}$, right?) and the minimum should occur when the denominator is as large as possible --- or when that's a bit obscure, when $m$ is as small as possible (i.e. $m = 1$ or $2$.)
$\rule{25cm}{1.5pt}$
[True start of motivation] However, getting the minimum to be $2$ should trigger some red flags, because this does imply that $f(m,n)$ in the problem statement is strong, but is easily defeated by some "even" property. Following up from this, there's an uncanny coincidence in the $2$ which is present in the $LHS$ of the divisibility --- and modifying it for a bit (adding $n(n-m)$ to force $mn$ to appear) should yield the first and (a part) of the third chunk.
A problem also appears when one tries to consider $n = 2$, because the inequality in (ii) will force $4002(n-m)$ to be a large negative, except when $m$ is also small. For me, this almost pushed me to directly consider factoring out this pesky hindrance. Another way to motivate this is by wondering "our work would be so easy if $4002-m-n$ can be negative" (which unfortunately cannot be); and after finally transiting $n^2-m^2$ to the right-side, we finally get our dream term $4002-m-n$ in the $RHS$.
The rest is easy enough, as if the RHS is negative, it would force $n-m$ to be negative as well. Directly using $m < 4002$ on the $RHS$ to tinker with the numerator and also the strange $2mn$ on the left side yields the result. (Heh, as it turns out, this isn't so short after all. Maybe that's why I rate this as a 20M problem?)
$\rule{25cm}{1.5pt}$
The final hard obstacle is, of course, the maxima of $f(m,n)$. My argument for taking the leap of faith here is the prevalence of $n-m$ in the $\color{green} \textbf{\text{Intro}}$, and that we can represent $f(m,n)$ as
\[ f(m,n) = (4002-m-n) \cdot \dfrac{m}{n} \]which should, for $n$ small, make the fraction $\dfrac{m}{n}$ to be as low as $\dfrac{3}{5}$. The existence of such fractions would diminish $f(m,n)$ to $\dfrac{3}{5}\cdot 4000 \sim 2400$, which was unthinkable.
After doing the $\lambda(x-a)^3$ problem, I was tempted to consider a standard inequality like $AM-GM$ here. However, the existence of an equality case specifically when $n-m = 2$ and $m = 50$ wrecks the hope, because there's no way $\dfrac{4002-m-n}{n} = 75$ and $m = 50$ could be considered equal in any sense. Again, putting a bit of time to blindly set $n-m = k$ saves the day, when the equality case itself isn't something as "regular" as the inequality next door.
$\color{green} \rule{25cm}{1pt}$
Final Comments: The artificial conditions do not make this a "bad problem", and this is still good for practice and teaching. In my opinion, this problem is closer to a "culprit search" rather than a "series of discoveries" --- where you have to discern what the conditions mean (they don't mean anything on their own, but the problem condition and problem statement are basically twins of each other.) I would rate this 2.5 points for the first chunk, 10 points for the second and third chunks combined, 0 points for the first part (since this is only a reiteration of the third chunk) and a final 5+ for the brute force (which is only a test of faith), which results in a 20 point/20M total.