1983 IMO Problems/Problem 3

Problem

Let $a$, $b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc - ab - bc- ca$ is the largest integer which cannot be expressed in the form $xbc + yca + zab$, where $x$, $y$ and $z$ are non-negative integers.

Solution 1

First off, I prove $2abc-ab-bc-ca$ is un-achievable. Also, assume WLOG $a\ge b\ge c$.

Assume $2abc-bc-ca=xbc+yca+zab$, then take the equation $\pmod{ab}$ to give us $(x+1)bc+(y+1)ac\equiv 0\pmod{ab}$. By CRT and $\gcd(a,b)=1$, we take this equation mod a and mod b to give us $y+1\equiv 0\pmod{b}$, and $x+1\equiv 0\pmod{a}$ (and using all numbers are relatively prime pairwise). Substituting this back into the original equation gives us $z\le -1$, contradiction (this is where the $2abc$ part comes in).

Now, let $2abc-bc-ca-ab+k=xbc+yca+zab$, and if a solution exists where $bc-1\ge k\ge 1$ then we are done because we can add $1$ to $x$ always.

Consider the set $x=a-m$, where $m\in \{1,2,\cdots, a-1, a\}$ and $y=b-n$ where $n\in \{1,2,\cdots, b-1, b\}$.

Therefore, we get $2abc-bc-ca-ab+k=(a-m)bc+(b-n)ca+zab$. This is the same as $bc(m-1)+ca(n-1)+k=(z+1)ab$ after doing some simplifying. By CRT, this must hold mod a and mod b and because $\gcd(a,b)=1$. Mod $a$ gives us $bc(m-1)+k\equiv 0\pmod{a}$, for which a value of $m-1$ obviously exists mod $a$, which can be chosen from the set of values we have assigned for $m$. Similar method shows a value of $n-1$ exists mod $b$ from the set we have given to $n$.

Now, we already know that $x,y\ge 0$. Also, the LHS of the equation $bc(m-1)+ca(n-1)+k$ is at least $1$, therefore $z\ge 0$ and we are done.

This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [1]

Solution 2

First we will prove $2abc-ab-bc-ca$ is unattainable, as such: Suppose $xbc+yca+zab=2abc-ab-bc-ca$. Then, taking this mod $a$, we have that $xbc\equiv 0\pmod{a}$, so $x\equiv 0\pmod{a}$, and $a|x$. Similarly, $b|y$, and $c|z$, so $x\ge a$, $y\ge b$, and $z\ge c$. Thus, $xbc+yca+zac\ge 3abc$, so $2abc\ge 3abc$, which is a contradiction.

Now we will prove all $n>2abc-ab-bc-ca$ is attainable, as such: consider the integer $r$ such that $r\equiv \frac{n}{bc} \pmod{a}$ and $0\le r\le a-1$. Rearranging the equation $xbc+yca+zab=n$ yields $\frac{n-xbc}{a}=yc+zb$, so set $x=r$. We see that $xbc-n=rbc-n\equiv 0 \pmod{a}$, so $\frac{n-xbc}{a}$ is a positive integer (obviously $n-xbc>0)$. Now, note that since $x\le a-1$, we have that $2abc-ab-ac-bc=(a-1)bc+abc-ab-ac\ge xbc+abc-ab-ac$, so $n>xbc+abc-ab-ac$. Thus, $n-xbc>abc-ab-ac$ so $\frac{n-xbc}{a}>bc-b-c$, so by Chicken Mc-Nugget theorem, there exist $b, c$ that satisfy the equation and are now done. $\blacksquare$

This solution was posted and copyrighted by Stormersyle. The original thread for this problem can be found here: [2]



1983 IMO (Problems) • Resources
Preceded by
Problem 2
1 2 3 4 5 6 Followed by
Problem 4
All IMO Problems and Solutions