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 "1970 Canadian MO Problems/Problem 7"
 
(5 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
  
−
'''Claim 1:'' 'if <math>a</math>, <math>b</math>, and <math>c</math> have equal modularity, then <math>(a+b+c)</math> is divisible by <math>3</math>
+
'''Claim 1:''' if <math>a</math>, <math>b</math>, and <math>c</math> have equal modularity, then <math>(a+b+c)</math> is divisible by <math>3</math>
  
 
Proof of Claim 1: Let <math>a</math>, <math>b</math>, and <math>c</math> be three integers with equal modularity.
 
Proof of Claim 1: Let <math>a</math>, <math>b</math>, and <math>c</math> be three integers with equal modularity.
Line 15: Line 15:
 
Thus, if <math>a</math>, <math>b</math>, and <math>c</math> have equal modularity, then <math>(a+b+c)</math> is divisible by <math>3</math>
 
Thus, if <math>a</math>, <math>b</math>, and <math>c</math> have equal modularity, then <math>(a+b+c)</math> is divisible by <math>3</math>
  
−
'''Claim 2:'' 'if <math>a</math>, <math>b</math>, and <math>c</math> have different modularity from each other, then <math>(a+b+c)</math> is divisible by <math>3</math>
+
'''Claim 2:''' if <math>a</math>, <math>b</math>, and <math>c</math> have different modularity from each other, then <math>(a+b+c)</math> is divisible by <math>3</math>
  
 
Proof of Claim 2: Let <math>a</math>, <math>b</math>, and <math>c</math> 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.
 
Proof of Claim 2: Let <math>a</math>, <math>b</math>, and <math>c</math> 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.
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:
  
−
Let  <math>a \equiv b\;(mod\;3)\equiv k\;(mod\;3)</math>, where <math>k=-1,0,</math> or <math>1</math>.
+
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>
  
−
and  <math>c \equiv d\;(mod\;3)\equiv q\;(mod\;3)</math>, where <math>q=-1,0,</math> or <math>1</math> and <math>q \ne k</math>
+
The fifth number <math>e</math> will be of modularity <math>-1, 0,</math> or <math>1</math>.
  
−
Then <math>(a+b+c)\equiv (2k+2q)\;(mod\;3)\equiv 0\;(mod\;3)</math>
+
'''Case 1:''' <math>e\equiv -1\;(mod\;3)</math>
  
−
Possible values of <math>k+q</math> are <math>(-1+0), (-1+1), (0-1), (0+1), (1-1), (1-0)</math>
+
From Combination 1, we have <math>0,\;0,\;1,\;1,\;-1</math> from which we can chose <math>0,\;1,\;-1</math> which is divisible by three
  
−
Notice that <math>(-1+1)\equiv 0\;(mod\;3)</math> and <math>(1-1)equiv 0\;(mod\;3)</math>, so we eliminate those from the possible values of <math>k+q</math> and we have: <math>(-1+0), (0-1), (0+1), (1-0)</math>
+
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
  
−
Therefore 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:
+
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
  
−
Combination 1: <math>0 0 1 1</math> or Combination 2: <math>0 0 -1 -1</math>
+
'''Case 2:''' <math>e\equiv 0\;(mod\;3)</math>
  
−
The fifth number <math>e</math> will be of modularity <math>-1, 0,</math> or <math>1</math>.
+
From Combination 1, we have <math>0,\;0,\;1,\;1,\;0</math> from which we can chose <math>0,\;0,\;0</math> which is divisible by three
  
−
'''Case 1:''' <math>e\equiv -1\;(mod\;3)</math>
+
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 1, 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,\;0</math> from which we can chose <math>-1,\;0,\;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
+
'''Case 3:''' <math>e\equiv 1\;(mod\;3)</math>
  
−
'''Case 2:''' <math>e\equiv 0\;(mod\;3)</math>
+
From Combination 1, 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 1, 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,\;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 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,\;1</math> from which we can chose <math>1,\;1,\;1</math> which is divisible by three
  
−
'''Case 3:''' <math>e\equiv 1\;(mod\;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>
 +
 
 +
~Tomas Diaz. orders@tomasdiaz.com
  
−
From Combination 1, we have <math>0 0 1 1 1</math> from which we can chose <math>1 1 1</math> which is divisible by three
+
==Solution 2==
  
−
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
+
Drawing a graph tree with nodes with all the modular possibilities and their paths chowing each path how it ends when a specific combination of three out of available numbers on that path, their summation is divisible by 3:
  
−
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>
+
[[File:1970_CMO_P7b.png|800px]]
  
 
~Tomas Diaz. orders@tomasdiaz.com
 
~Tomas Diaz. orders@tomasdiaz.com
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 22:38, 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 $3$.

Solution

Claim 1: if $a$, $b$, and $c$ have equal modularity, then $(a+b+c)$ is divisible by $3$

Proof of Claim 1: Let $a$, $b$, and $c$ be three integers with equal modularity.

That is, $a \equiv b\;(mod\;3)\equiv c\;(mod\;3)\equiv k\;(mod\;3)$, where $k=-1,0,$ or $1$.

Then $(a+b+c)\equiv 3k\;(mod\;3)\equiv 0\;(mod\;3)$

Thus, if $a$, $b$, and $c$ have equal modularity, then $(a+b+c)$ is divisible by $3$

Claim 2: if $a$, $b$, and $c$ have different modularity from each other, then $(a+b+c)$ is divisible by $3$

Proof of Claim 2: Let $a$, $b$, and $c$ 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 $(a+b+c)\equiv (-1+0+1)\;(mod\;3)\equiv 0\;(mod\;3)$

Thus, if $a$, $b$, and $c$ have different modularity from each other, then $(a+b+c)$ is divisible by $3$

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 $a$, $b$, $c$, and $d$, 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: $0,\;0,\;1,\;1$, Combination 2: $0,\;0,\;-1,\;-1$, or Combination 3: $-1,\;-1,\;1,\;1$

The fifth number $e$ will be of modularity $-1, 0,$ or $1$.

Case 1: $e\equiv -1\;(mod\;3)$

From Combination 1, we have $0,\;0,\;1,\;1,\;-1$ from which we can chose $0,\;1,\;-1$ which is divisible by three

From Combination 2, we have $0,\;0,\;-1,\;-1,\;-1$ from which we can chose $-1,\;-1,\;-1$ which is divisible by three

From Combination 3, we have $-1,\;-1,\;1,\;1,\;-1$ from which we can chose $-1,\;-1,\;-1$ which is divisible by three

Case 2: $e\equiv 0\;(mod\;3)$

From Combination 1, we have $0,\;0,\;1,\;1,\;0$ from which we can chose $0,\;0,\;0$ which is divisible by three

From Combination 2, we have $0,\;0,\;-1,\;-1,\;0$ from which we can chose $0,\;0,\;0$ which is divisible by three

From Combination 3, we have $-1,\;-1,\;1,\;1,\;0$ from which we can chose $-1,\;0,\;1$ which is divisible by three

Case 3: $e\equiv 1\;(mod\;3)$

From Combination 1, we have $0,\;0,\;1,\;1,\;1$ from which we can chose $1,\;1,\;1$ which is divisible by three

From Combination 2, we have $0,\;0,\;-1,\;-1,\;1$ from which we can chose $0,\;-1,\;1$ which is divisible by three

From Combination 3, we have $-1,\;-1,\;1,\;1,\;1$ from which we can chose $1,\;1,\;1$ 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 $3$

~Tomas Diaz. orders@tomasdiaz.com

Solution 2

Drawing a graph tree with nodes with all the modular possibilities and their paths chowing each path how it ends when a specific combination of three out of available numbers on that path, their summation is divisible by 3:

1970 CMO P7b.png

~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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1970_Canadian_MO_Problems/Problem_7&oldid=206193"