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

Page

Toolbox

Search

1983 IMO Problems/Problem 3

Problem

Solution 1

Solution 2