IMO 2006 Shortlisted Problems

Call the pair of integers $(x,y)$ a representation of $c$ if $ax+by=c$ and $|x|+|y|$ has the smallest possible value, i.e. $|x|+|y|=w(c)$. We characterise the local champions by the following three observations.

Lemma 1. If $(x,y)$ a representation of a local champion $c$ then $xy<0$.

Proof. Suppose indirectly that $x\ge 0$ and $y\ge 0$ and consider the values $w(c)$ and $w(c+a)$. All representations of the numbers $c$ and $c+a$ in the form $au+bv$ can be written as $$c=a(x-kb)+b(y+ka),c+a=a(x+1-kb)+b(y+ka)$$ where $k$ is an arbitrary integer. Since $|x|+|y|$ is minimal, we have $$x+y=|x|+|y|\le |x-kb|+|y+ka|$$ for all $k$. On the other hand, $w(c+a)\le w(c)$, so there exists a $k$ for which $$|x+1-kb|+|y+ka|\le |x|+|y|=x+y.$$ Then $$(x+1-kb)+(y+ka)\le |x+1-kb|+|y+ka|\le x+y\le |x-kb|+|y+ka|.$$ Comparing the first and the third expressions, we find $k(a-b)+1\le 0$ implying $k<0$. Comparing the second and fourth expressions, we get $|x+1-kb|\le |x-kb|$, therefore $kb>x$; this is a contradiction. If $x,y\le 0$ then we can switch to $-c,-x$ and $-y$. $\square$

From this point, write $c=ax-by$ instead of $c=ax+by$ and consider only those cases where $x$ and $y$ are nonzero and have the same sign. By Lemma 1, there is no loss of generality in doing so.

Lemma 2. Let $c=ax-by$ where $|x|+|y|$ is minimal and $x,y$ have the same sign. The number $c$ is a local champion if and only if $|x|<b$ and $|x|+|y|=\lfloor \frac{a+b}{2}\rfloor$.

Proof. Without loss of generality we may assume $x,y>0$. The numbers $c-a$ and $c+b$ can be written as $$c-a=a(x-1)-by\text{ and }c+b=ax-b(y-1)$$ and trivially $w(c-a)\le (x-1)+y<w(c)$ and $w(c+b)\le x+(y-1)<w(c)$ in all cases. Now assume that $c$ is a local champion and consider $w(c+a)$. Since $w(c+a)\le w(c)$, there exists an integer $k$ such that $$c+a=a(x+1-kb)-b(y-ka)\text{ and }|x+1-kb|+|y-ka|\le x+y.$$ This inequality cannot hold if $k\le 0$, therefore $k>0$. We prove that we can choose $k=1$. Consider the function $f(t)=|x+1-bt|+|y-at|-(x+y)$. This is a convex function and we have $f(0)=1$ and $f(k)\le 0$. By Jensen's inequality, $f(1)\le \left(1-\frac{1}{k}\right)f(0)+\frac{1}{k}f(k)<1$. But $f(1)$ is an integer. Therefore $f(1)\le 0$ and $$|x+1-b|+|y-a|\le x+y.$$ Knowing $c=a(x-b)-b(y-a)$, we also have $$x+y\le |x-b|+|y-a|.$$ Combining the two inequalities yields $|x+1-b|\le |x-b|$ which is equivalent to $x<b$. Considering $w(c-b)$, we obtain similarly that $y<a$. Now $|x-b|=b-x,|x+1-b|=b-x-1$ and $|y-a|=a-y$, therefore we have $$\begin{array}{rl}(b-x-1)+(a-y)& \le x+y\le (b-x)+(a-y),\\ \frac{a+b-1}{2}& \le x+y\le \frac{a+b}{2}.\end{array}$$ Hence $x+y=\lfloor \frac{a+b}{2}\rfloor$. To prove the opposite direction, assume $0<x<b$ and $x+y=\lfloor \frac{a+b}{2}\rfloor$. Since $a>b$, we also have $0<y<a$. Then $$w(c+a)\le |x+1-b|+|y-a|=a+b-1-(x+y)\le x+y=w(c)$$ and $$w(c-b)\le |x-b|+|y+1-a|=a+b-1-(x+y)\le x+y=w(c)$$ therefore $c$ is a local champion indeed. $\square$

Lemma 3. Let $c=ax-by$ and assume that $x$ and $y$ have the same sign, $|x|<b,|y|<a$ and $|x|+|y|=\lfloor \frac{a+b}{2}\rfloor$. Then $w(c)=x+y$.

Proof. By definition $w(c)=\min \{|x-kb|+|y-ka|:k\in \mathbb{Z}\}$. If $k\le 0$ then obviously $|x-kb|+|y-ka|\ge x+y$. If $k\ge 1$ then $$|x-kb|+|y-ka|=(kb-x)+(ka-y)=k(a+b)-(x+y)\ge (2k-1)(x+y)\ge x+y.$$ Therefore $w(c)=x+y$ indeed. $\square$

Lemmas 1, 2 and 3 together yield that the set of local champions is $$C=\left\{\pm (ax-by):0<x<b,x+y=\lfloor \frac{a+b}{2}\rfloor \right\}.$$ Denote by $C^{+}$ and $C^{-}$ the two sets generated by the expressions $+(ax-by)$ and $-(ax-by)$, respectively. It is easy to see that both sets are arithmetic progressions of length $b-1$, with difference $a+b$. If $a$ and $b$ are odd, then $C^{+}=C^{-}$, because $a(-x)-b(-y)=a(b-x)-b(a-y)$ and $x+y=\frac{a+b}{2}$ is equivalent to $(b-x)+(a-y)=\frac{a+b}{2}$. In this case there exist $b-1$ local champions. If $a$ and $b$ have opposite parities then the answer is different. For any $c_1\in C^{+}$ and $c_2\in C^{-}$, $$2c_1\equiv -2c_2\equiv 2\left(a\frac{a+b-1}{2}-b\cdot 0\right)\equiv -a(\mathrm{mod}a+b)$$ and $$2c_1-2c_2\equiv -2a(\mathrm{mod}a+b)$$ The number $a+b$ is odd and relatively prime to $a$, therefore the elements of $C^{+}$ and $C^{-}$ belong to two different residue classes modulo $a+b$. Hence, the set $C$ is the union of two disjoint arithmetic progressions and the number of all local champions is $2(b-1)$. So the number of local champions is $b-1$ if both $a$ and $b$ are odd and $2(b-1)$ otherwise.