Difference between revisions of "1983 IMO Problems/Problem 3"
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | ==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. | 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}} | {{IMO box|year=1983|num-b=2|num-a=4}} |
Latest revision as of 22:37, 29 January 2021
Problem
Let ,
and
be positive integers, no two of which have a common divisor greater than
. Show that
is the largest integer which cannot be expressed in the form
, where
,
and
are non-negative integers.
Solution 1
First off, I prove is un-achievable. Also, assume WLOG
.
Assume , then take the equation
to give us
. By CRT and
, we take this equation mod a and mod b to give us
, and
(and using all numbers are relatively prime pairwise). Substituting this back into the original equation gives us
, contradiction (this is where the
part comes in).
Now, let , and if a solution exists where
then we are done because we can add
to
always.
Consider the set , where
and
where
.
Therefore, we get . This is the same as
after doing some simplifying. By CRT, this must hold mod a and mod b and because
. Mod
gives us
, for which a value of
obviously exists mod
, which can be chosen from the set of values we have assigned for
. Similar method shows a value of
exists mod
from the set we have given to
.
Now, we already know that . Also, the LHS of the equation
is at least
, therefore
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 is unattainable, as such:
Suppose
. Then, taking this mod
, we have that
, so
, and
. Similarly,
, and
, so
,
, and
. Thus,
, so
, which is a contradiction.
Now we will prove all is attainable, as such: consider the integer
such that
and
. Rearranging the equation
yields
, so set
. We see that
, so
is a positive integer (obviously
. Now, note that since
, we have that
, so
. Thus,
so
, so by Chicken Mc-Nugget theorem, there exist
that satisfy the equation and are now done.
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 |