Difference between revisions of "1970 Canadian MO Problems/Problem 7"
Line 29: | Line 29: | ||
Therefore, one can chose 2 integers with the same modularity with each other and another integer with a different modularity but the same modularity with each other. | Therefore, one can chose 2 integers with the same modularity with each other and another integer with a different modularity but the same modularity with each other. | ||
− | So, from integers <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> | + | So, from integers <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math>, the only combinations of the modularities that we can have with 4 numbers such that no three of those numbers get a sum that divisible by three are: |
− | + | Combination 1: <math>0 0 1 1</math>, Combination 2: <math>0 0 -1 -1</math>, or Combination 3: <math>-1 -1 1 1</math> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
The fifth number <math>e</math> will be of modularity <math>-1, 0,</math> or <math>1</math>. | The fifth number <math>e</math> will be of modularity <math>-1, 0,</math> or <math>1</math>. | ||
Line 52: | Line 40: | ||
From Combination 2, we have <math>0 0 -1 -1 -1</math> from which we can chose <math>-1 -1 -1</math> which is divisible by three | From Combination 2, we have <math>0 0 -1 -1 -1</math> from which we can chose <math>-1 -1 -1</math> which is divisible by three | ||
+ | |||
+ | From Combination 3, we have <math>-1 -1 1 1 -1</math> from which we can chose <math>-1 -1 -1</math> which is divisible by three | ||
'''Case 2:''' <math>e\equiv 0\;(mod\;3)</math> | '''Case 2:''' <math>e\equiv 0\;(mod\;3)</math> | ||
Line 58: | Line 48: | ||
From Combination 2, we have <math>0 0 -1 -1 0</math> from which we can chose <math>0 0 0</math> which is divisible by three | From Combination 2, we have <math>0 0 -1 -1 0</math> from which we can chose <math>0 0 0</math> which is divisible by three | ||
+ | |||
+ | From Combination 3, we have <math>-1 -1 1 1 0</math> from which we can chose <math>-1 0 1</math> which is divisible by three | ||
'''Case 3:''' <math>e\equiv 1\;(mod\;3)</math> | '''Case 3:''' <math>e\equiv 1\;(mod\;3)</math> | ||
Line 64: | Line 56: | ||
From Combination 2, we have <math>0 0 -1 -1 1</math> from which we can chose <math>0 -1 1</math> which is divisible by three | From Combination 2, we have <math>0 0 -1 -1 1</math> from which we can chose <math>0 -1 1</math> which is divisible by three | ||
+ | |||
+ | From Combination 3, we have <math>-1 -1 1 1 1</math> from which we can chose <math>1 1 1</math> which is divisible by three | ||
And this proves that from any five integers, not necessarily distinct, one can always choose three of these integers whose sum is divisible by <math>3</math> | And this proves that from any five integers, not necessarily distinct, one can always choose three of these integers whose sum is divisible by <math>3</math> |
Revision as of 21:41, 27 November 2023
Problem
Show that from any five integers, not necessarily distinct, one can always choose three of these integers whose sum is divisible by .
Solution
Claim 1: if ,
, and
have equal modularity, then
is divisible by
Proof of Claim 1: Let ,
, and
be three integers with equal modularity.
That is, , where
or
.
Then
Thus, if ,
, and
have equal modularity, then
is divisible by
Claim 2: if ,
, and
have different modularity from each other, then
is divisible by
Proof of Claim 2: Let ,
, and
be three integers where one of them is is divisible by 3, the other one has a reminder of 1 when divided by 3 and the other one a reminder of 2, (or -1) for simplicity.
Then
Thus, if ,
, and
have different modularity from each other, then
is divisible by
In order for the sum of three integers to be divisible by three these three integers should have either all with the same modularity to each other, or they must have distinct modularity.
To have 4 integers that their sum is not divisible by three, then we can't have any combinations of 3 out of 4 where each of those are either the same modularity or different modularity with each other.
Therefore, one can chose 2 integers with the same modularity with each other and another integer with a different modularity but the same modularity with each other.
So, from integers ,
,
, and
, the only combinations of the modularities that we can have with 4 numbers such that no three of those numbers get a sum that divisible by three are:
Combination 1: , Combination 2:
, or Combination 3:
The fifth number will be of modularity
or
.
Case 1:
From Combination 1, we have from which we can chose
which is divisible by three
From Combination 2, we have from which we can chose
which is divisible by three
From Combination 3, we have from which we can chose
which is divisible by three
Case 2:
From Combination 1, we have from which we can chose
which is divisible by three
From Combination 2, we have from which we can chose
which is divisible by three
From Combination 3, we have from which we can chose
which is divisible by three
Case 3:
From Combination 1, we have from which we can chose
which is divisible by three
From Combination 2, we have from which we can chose
which is divisible by three
From Combination 3, we have from which we can chose
which is divisible by three
And this proves that from any five integers, not necessarily distinct, one can always choose three of these integers whose sum is divisible by
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.