Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1983 IMO Problems/Problem 3"
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
Let <math>a</math>, <math>b</math> and <math>c</math> be positive integers, no two of which have a common divisor greater than <math>1</math>. Show that <math>2abc - ab - bc- ca</math> is the largest integer which cannot be expressed in the form <math>xbc + yca + zab</math>, where <math>x</math>, <math>y</math> and <math>z</math> are non-negative integers
+
==Problem==
 +
Let <math>a</math>, <math>b</math> and <math>c</math> be positive integers, no two of which have a common divisor greater than <math>1</math>. Show that <math>2abc - ab - bc- ca</math> is the largest integer which cannot be expressed in the form <math>xbc + yca + zab</math>, where <math>x</math>, <math>y</math> and <math>z</math> are non-negative integers.
 +
 
 +
==Solution 1==
 +
First off, I prove <math>2abc-ab-bc-ca</math> is un-achievable. Also, assume WLOG <math>a\ge b\ge c</math>.
 +
 
 +
Assume <math>2abc-bc-ca=xbc+yca+zab</math>, then take the equation <math>\pmod{ab}</math> to give us <math>(x+1)bc+(y+1)ac\equiv 0\pmod{ab}</math>. By CRT and <math>\gcd(a,b)=1</math>, we take this equation mod a and mod b to give us <math>y+1\equiv 0\pmod{b}</math>, and <math>x+1\equiv 0\pmod{a}</math> (and using all numbers are relatively prime pairwise). Substituting this back into the original equation gives us <math>z\le -1</math>, contradiction (this is where the <math>2abc</math> part comes in).
 +
 
 +
Now, let <math>2abc-bc-ca-ab+k=xbc+yca+zab</math>, and if a solution exists where <math>bc-1\ge k\ge 1</math> then we are done because we can add <math>1</math> to <math>x</math> always.
 +
 
 +
Consider the set <math>x=a-m</math>, where <math>m\in \{1,2,\cdots, a-1, a\}</math> and <math>y=b-n</math> where <math>n\in \{1,2,\cdots, b-1, b\}</math>.
 +
 
 +
Therefore, we get <math>2abc-bc-ca-ab+k=(a-m)bc+(b-n)ca+zab</math>. This is the same as <math>bc(m-1)+ca(n-1)+k=(z+1)ab</math> after doing some simplifying. By CRT, this must hold mod a and mod b and because <math>\gcd(a,b)=1</math>. Mod <math>a</math> gives us <math>bc(m-1)+k\equiv 0\pmod{a}</math>, for which a value of <math>m-1</math> obviously exists mod <math>a</math>, which can be chosen from the set of values we have assigned for <math>m</math>. Similar method shows a value of <math>n-1</math> exists mod <math>b</math> from the set we have given to <math>n</math>.
 +
 
 +
Now, we already know that <math>x,y\ge 0</math>. Also, the LHS of the equation <math>bc(m-1)+ca(n-1)+k</math> is at least <math>1</math>, therefore <math>z\ge 0</math> and we are done.
 +
 
 +
This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [https://aops.com/community/p2930827]
 +
 
 +
==Solution 2==
 +
First we will prove <math>2abc-ab-bc-ca</math> is unattainable, as such:
 +
Suppose <math>xbc+yca+zab=2abc-ab-bc-ca</math>. Then, taking this mod <math>a</math>, we have that <math>xbc\equiv 0\pmod{a}</math>, so <math>x\equiv 0\pmod{a}</math>, and <math>a|x</math>. Similarly, <math>b|y</math>, and <math>c|z</math>, so <math>x\ge a</math>, <math>y\ge b</math>, and <math>z\ge c</math>. Thus, <math>xbc+yca+zac\ge 3abc</math>, so <math>2abc\ge 3abc</math>, which is a contradiction.
 +
 
 +
Now we will prove all <math>n>2abc-ab-bc-ca</math> is attainable, as such: consider the integer <math>r</math> such that <math>r\equiv \frac{n}{bc} \pmod{a}</math> and <math>0\le r\le a-1</math>. Rearranging the equation <math>xbc+yca+zab=n</math> yields <math>\frac{n-xbc}{a}=yc+zb</math>, so set <math>x=r</math>. We see that <math>xbc-n=rbc-n\equiv 0 \pmod{a}</math>, so <math>\frac{n-xbc}{a}</math> is a positive integer (obviously <math>n-xbc>0)</math>. Now, note that since <math>x\le a-1</math>, we have that <math>2abc-ab-ac-bc=(a-1)bc+abc-ab-ac\ge xbc+abc-ab-ac</math>, so <math>n>xbc+abc-ab-ac</math>. Thus, <math>n-xbc>abc-ab-ac</math> so <math>\frac{n-xbc}{a}>bc-b-c</math>, so by Chicken Mc-Nugget theorem, there exist <math>b, c</math> that satisfy the equation and are now done. <math>\blacksquare</math>
 +
 
 +
This solution was posted and copyrighted by Stormersyle. The original thread for this problem can be found here: [https://aops.com/community/p12471179]
 +
 
 +
 
 +
 
 +
 
 +
{{IMO box|year=1983|num-b=2|num-a=4}}

Latest revision as of 22:37, 29 January 2021

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1983_IMO_Problems/Problem_3&oldid=144008"