Let $ a > b > 1$ be relatively prime positive integers. Define the weight of an integer $ c$, denoted by $ w(c)$ to be the minimal possible value of $ |x| + |y|$ taken over all pairs of integers $ x$ and $ y$ such that \[ax + by = c.\] An integer $ c$ is called a local champion if $ w(c) \geq w(c \pm a)$ and $ w(c) \geq w(c \pm b)$. Find all local champions and determine their number. Proposed by Zoran Sunic, USA
Problem
Source: IMO Shortlist 2006, Number Theory 6, AIMO 2007, TST 1, P3
Tags: number theory, relatively prime, greatest common divisor, IMO Shortlist
shunka
22.09.2007 01:54
in the original version, this problem did not ask for all local champions. there were two questions (a) show that there are only finitely many local champions (b) show that there exists at least one local champion both questions allow for many different (and even elegant) solutions. in my opinion, the beauty of the problem was completely distroyed by asking for all local champions, since many of the interesting ideas and approaches that work for (a) and (b) do not work anymore and one is left with a somewhat tedious work od grinding out all solutions.
Hamper.r
05.11.2019 00:02
Not hard but long
These are just the steps and...
Lemma1: XY<0
First we notice that if C=ax+by then C=a(x-bk)+b(y+ak) for arbitrary k.
Then just consider a local champion C and W(c+a).
So then wlog c=ax-by which x,y have same sign(wlog positive).
Now two of local champion properties are obvious.
The other ones show that k>0 and |x|<b and |y|<a then if for a local champion c, we consider the minimum k which weight of a(x+1-bk)-b(y-ak) is smaller than |x|+|y| , writing all the 9 cases of y<ak , ... Shows that the minimum k should be 1.
And then it's easy to see that the only local champions are the ones which x+y = $\lfloor \frac {a+b}{2} \rfloor$ and they all work.
I'm sorry that I skipped the details, I try to post the complete solution later.