Mixing
Prove that given any ï¬Âve integers, there will be three for which the sum of the squares of those integers is divisible by 3.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Basically the question is asking us to prove that given any integers $$x_1,x_2,x_3,x_4,x_5$$ Prove that 3 of the integers from the set above, suppose $$x_a,x_b,x_c$$ satisfy this equation: $$x_a^2 + x_b^2 + x_c^2 = 3k$$ So I know I am suppose to use the pigeon hole principle to prove this. I know that if I have 5 pigeons and 2 holes then 1 hole will have 3 pigeons. But what I am confused about is how do you define the hole? Do I just say that the container has a property such that if 3 integers are in it then those 3 integers squared sum up to a multiple of 3?
discrete-mathematics
asked 31 mins ago
Geralt
242
add a comment |Â
up vote
1
down vote
favorite
Basically the question is asking us to prove that given any integers $$x_1,x_2,x_3,x_4,x_5$$ Prove that 3 of the integers from the set above, suppose $$x_a,x_b,x_c$$ satisfy this equation: $$x_a^2 + x_b^2 + x_c^2 = 3k$$ So I know I am suppose to use the pigeon hole principle to prove this. I know that if I have 5 pigeons and 2 holes then 1 hole will have 3 pigeons. But what I am confused about is how do you define the hole? Do I just say that the container has a property such that if 3 integers are in it then those 3 integers squared sum up to a multiple of 3?
discrete-mathematics
asked 31 mins ago
Geralt
242
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Basically the question is asking us to prove that given any integers $$x_1,x_2,x_3,x_4,x_5$$ Prove that 3 of the integers from the set above, suppose $$x_a,x_b,x_c$$ satisfy this equation: $$x_a^2 + x_b^2 + x_c^2 = 3k$$ So I know I am suppose to use the pigeon hole principle to prove this. I know that if I have 5 pigeons and 2 holes then 1 hole will have 3 pigeons. But what I am confused about is how do you define the hole? Do I just say that the container has a property such that if 3 integers are in it then those 3 integers squared sum up to a multiple of 3?
discrete-mathematics
asked 31 mins ago
Geralt
242
Basically the question is asking us to prove that given any integers $$x_1,x_2,x_3,x_4,x_5$$ Prove that 3 of the integers from the set above, suppose $$x_a,x_b,x_c$$ satisfy this equation: $$x_a^2 + x_b^2 + x_c^2 = 3k$$ So I know I am suppose to use the pigeon hole principle to prove this. I know that if I have 5 pigeons and 2 holes then 1 hole will have 3 pigeons. But what I am confused about is how do you define the hole? Do I just say that the container has a property such that if 3 integers are in it then those 3 integers squared sum up to a multiple of 3?
discrete-mathematics
discrete-mathematics
asked 31 mins ago
Geralt
242
asked 31 mins ago
Geralt
242
asked 31 mins ago
Geralt
242
asked 31 mins ago
Geralt
242
asked 31 mins ago
Geralt
242
242
add a comment |Â
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
5
down vote
Any square integer must be congruent to either 1 or 0 mod 3. So for each of the 5 squares, we put it into hole 0 if it is congruent to 0 and into hole 1 if it is congruent to 1. Then take three squares from the hole with at least 3 squares and add them together. You will get either: $0+0+0equiv 0$ or $1+1+1equiv0$ mod 3.
answered 24 mins ago
Ricky Tensor
2714
add a comment |Â
up vote
1
down vote
Let's look at any $3$ of them,say $a,b,c$ among $a,b,c,d,e$. You must have $2$ cases: $a^2 = 0, b^2=1, c^2=0$ or $a^2=0, b^2=1,c^2=1$ for the worst scenario. For the last $2$ numbers $d,e$, if at least one, say $d^2 = 0$, you're done. If not $d^2= e^2 = 1$, then $b^2+d^2+e^2 = 0$, all mod $3$. And you are done.
answered 22 mins ago
DeepSea
69.7k54386
add a comment |Â
up vote
0
down vote
The remainder of every integer in dividing by $3$ is either $0$,$1$,or $2$.
Thus the remainder of a square in dividing by $3$ is either $0$ or $1$.
Now we have $5$ perfect squares that means a set of $5$ remainders each of which is either a $0$ or a $1$.
The Pigeon hole principle says there are at least three of the same kind in the set of remainders.
Well, we either have $1+1+1$ or $0+0+0$ in our sum of the squares and in either case the sum is divisible by $3$
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
add a comment |Â
up vote
0
down vote
Basic pigeon hole. If all integers fall into either type $A$ or type $B$ and you have $n$ integers. Then at least $lceil frac n2 rceil$ will be of the same type.
I hope you can convince yourself of that on your own.
...
Let $x_i = 3*M_i + r_i$ where $r_i = 0, 1,$ or $-1$. All numbers will be one of these three options.
Then $x_i^2 = 9*M_i^2 + 6*M_i*r_i + r_i^2$. Let $V_i = 3*M_i^2 + 2*M_i*r_i$ so $x_i^2 = 3V_i + r_i^2$ where $r_i^2 = 0$ or $1$. All numbers will be one of these $2$ options.
Let all integers, $x_i$ where $r_i^2 = 0$ by of type $A$ and let all integers, $x_j$ where $r_j^2 =1$ by of type $B$.
So if you have $5$ integers and each is of type $A$ or type $B$ then by pigeon hole you must have at least $3$ of same type.
So suppose $x_a, x_b, x_c$ are three that are of one of these two types.
If the three are of the type where $A$ where $r_i^2 = 0$ then you will $x_a^2 + x_b^2 + x_c^2 = 3V_a + 0 + 3V_b + 0 + 3V_c + 0$. And that is divisible by $3$.
If the three are of the type $B$ where $r_i^2 = 1$ then you will have $x_a^2 + x_b^2 + x_c^2 = 3V_a + 1 + 3V_b+1 + 3V_c + 1 = 3V_a + 3V_b + 3V_c + 3$ which is divisible by $3$.
So you will always have at least three integers whose sums of squares is divisible by $3$.
answered 13 mins ago
fleablood
63.4k22679
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Any square integer must be congruent to either 1 or 0 mod 3. So for each of the 5 squares, we put it into hole 0 if it is congruent to 0 and into hole 1 if it is congruent to 1. Then take three squares from the hole with at least 3 squares and add them together. You will get either: $0+0+0equiv 0$ or $1+1+1equiv0$ mod 3.
answered 24 mins ago
Ricky Tensor
2714
add a comment |Â
up vote
5
down vote
Any square integer must be congruent to either 1 or 0 mod 3. So for each of the 5 squares, we put it into hole 0 if it is congruent to 0 and into hole 1 if it is congruent to 1. Then take three squares from the hole with at least 3 squares and add them together. You will get either: $0+0+0equiv 0$ or $1+1+1equiv0$ mod 3.
answered 24 mins ago
Ricky Tensor
2714
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Any square integer must be congruent to either 1 or 0 mod 3. So for each of the 5 squares, we put it into hole 0 if it is congruent to 0 and into hole 1 if it is congruent to 1. Then take three squares from the hole with at least 3 squares and add them together. You will get either: $0+0+0equiv 0$ or $1+1+1equiv0$ mod 3.
answered 24 mins ago
Ricky Tensor
2714
Any square integer must be congruent to either 1 or 0 mod 3. So for each of the 5 squares, we put it into hole 0 if it is congruent to 0 and into hole 1 if it is congruent to 1. Then take three squares from the hole with at least 3 squares and add them together. You will get either: $0+0+0equiv 0$ or $1+1+1equiv0$ mod 3.
answered 24 mins ago
Ricky Tensor
2714
answered 24 mins ago
Ricky Tensor
2714
answered 24 mins ago
Ricky Tensor
2714
answered 24 mins ago
Ricky Tensor
2714
2714
add a comment |Â
add a comment |Â
up vote
1
down vote
Let's look at any $3$ of them,say $a,b,c$ among $a,b,c,d,e$. You must have $2$ cases: $a^2 = 0, b^2=1, c^2=0$ or $a^2=0, b^2=1,c^2=1$ for the worst scenario. For the last $2$ numbers $d,e$, if at least one, say $d^2 = 0$, you're done. If not $d^2= e^2 = 1$, then $b^2+d^2+e^2 = 0$, all mod $3$. And you are done.
answered 22 mins ago
DeepSea
69.7k54386
add a comment |Â
up vote
1
down vote
Let's look at any $3$ of them,say $a,b,c$ among $a,b,c,d,e$. You must have $2$ cases: $a^2 = 0, b^2=1, c^2=0$ or $a^2=0, b^2=1,c^2=1$ for the worst scenario. For the last $2$ numbers $d,e$, if at least one, say $d^2 = 0$, you're done. If not $d^2= e^2 = 1$, then $b^2+d^2+e^2 = 0$, all mod $3$. And you are done.
answered 22 mins ago
DeepSea
69.7k54386
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let's look at any $3$ of them,say $a,b,c$ among $a,b,c,d,e$. You must have $2$ cases: $a^2 = 0, b^2=1, c^2=0$ or $a^2=0, b^2=1,c^2=1$ for the worst scenario. For the last $2$ numbers $d,e$, if at least one, say $d^2 = 0$, you're done. If not $d^2= e^2 = 1$, then $b^2+d^2+e^2 = 0$, all mod $3$. And you are done.
answered 22 mins ago
DeepSea
69.7k54386
Let's look at any $3$ of them,say $a,b,c$ among $a,b,c,d,e$. You must have $2$ cases: $a^2 = 0, b^2=1, c^2=0$ or $a^2=0, b^2=1,c^2=1$ for the worst scenario. For the last $2$ numbers $d,e$, if at least one, say $d^2 = 0$, you're done. If not $d^2= e^2 = 1$, then $b^2+d^2+e^2 = 0$, all mod $3$. And you are done.
answered 22 mins ago
DeepSea
69.7k54386
answered 22 mins ago
DeepSea
69.7k54386
answered 22 mins ago
DeepSea
69.7k54386
answered 22 mins ago
DeepSea
69.7k54386
69.7k54386
add a comment |Â
add a comment |Â
up vote
0
down vote
The remainder of every integer in dividing by $3$ is either $0$,$1$,or $2$.
Thus the remainder of a square in dividing by $3$ is either $0$ or $1$.
Now we have $5$ perfect squares that means a set of $5$ remainders each of which is either a $0$ or a $1$.
The Pigeon hole principle says there are at least three of the same kind in the set of remainders.
Well, we either have $1+1+1$ or $0+0+0$ in our sum of the squares and in either case the sum is divisible by $3$
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
add a comment |Â
up vote
0
down vote
The remainder of every integer in dividing by $3$ is either $0$,$1$,or $2$.
Thus the remainder of a square in dividing by $3$ is either $0$ or $1$.
Now we have $5$ perfect squares that means a set of $5$ remainders each of which is either a $0$ or a $1$.
The Pigeon hole principle says there are at least three of the same kind in the set of remainders.
Well, we either have $1+1+1$ or $0+0+0$ in our sum of the squares and in either case the sum is divisible by $3$
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The remainder of every integer in dividing by $3$ is either $0$,$1$,or $2$.
Thus the remainder of a square in dividing by $3$ is either $0$ or $1$.
Now we have $5$ perfect squares that means a set of $5$ remainders each of which is either a $0$ or a $1$.
The Pigeon hole principle says there are at least three of the same kind in the set of remainders.
Well, we either have $1+1+1$ or $0+0+0$ in our sum of the squares and in either case the sum is divisible by $3$
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
The remainder of every integer in dividing by $3$ is either $0$,$1$,or $2$.
Thus the remainder of a square in dividing by $3$ is either $0$ or $1$.
Now we have $5$ perfect squares that means a set of $5$ remainders each of which is either a $0$ or a $1$.
The Pigeon hole principle says there are at least three of the same kind in the set of remainders.
Well, we either have $1+1+1$ or $0+0+0$ in our sum of the squares and in either case the sum is divisible by $3$
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
answered 9 mins ago
Mohammad Riazi-Kermani
35.6k41955
35.6k41955
add a comment |Â
add a comment |Â
up vote
0
down vote
Basic pigeon hole. If all integers fall into either type $A$ or type $B$ and you have $n$ integers. Then at least $lceil frac n2 rceil$ will be of the same type.
I hope you can convince yourself of that on your own.
...
Let $x_i = 3*M_i + r_i$ where $r_i = 0, 1,$ or $-1$. All numbers will be one of these three options.
Then $x_i^2 = 9*M_i^2 + 6*M_i*r_i + r_i^2$. Let $V_i = 3*M_i^2 + 2*M_i*r_i$ so $x_i^2 = 3V_i + r_i^2$ where $r_i^2 = 0$ or $1$. All numbers will be one of these $2$ options.
Let all integers, $x_i$ where $r_i^2 = 0$ by of type $A$ and let all integers, $x_j$ where $r_j^2 =1$ by of type $B$.
So if you have $5$ integers and each is of type $A$ or type $B$ then by pigeon hole you must have at least $3$ of same type.
So suppose $x_a, x_b, x_c$ are three that are of one of these two types.
If the three are of the type where $A$ where $r_i^2 = 0$ then you will $x_a^2 + x_b^2 + x_c^2 = 3V_a + 0 + 3V_b + 0 + 3V_c + 0$. And that is divisible by $3$.
If the three are of the type $B$ where $r_i^2 = 1$ then you will have $x_a^2 + x_b^2 + x_c^2 = 3V_a + 1 + 3V_b+1 + 3V_c + 1 = 3V_a + 3V_b + 3V_c + 3$ which is divisible by $3$.
So you will always have at least three integers whose sums of squares is divisible by $3$.
answered 13 mins ago
fleablood
63.4k22679
add a comment |Â
up vote
0
down vote
Basic pigeon hole. If all integers fall into either type $A$ or type $B$ and you have $n$ integers. Then at least $lceil frac n2 rceil$ will be of the same type.
I hope you can convince yourself of that on your own.
...
Let $x_i = 3*M_i + r_i$ where $r_i = 0, 1,$ or $-1$. All numbers will be one of these three options.
Then $x_i^2 = 9*M_i^2 + 6*M_i*r_i + r_i^2$. Let $V_i = 3*M_i^2 + 2*M_i*r_i$ so $x_i^2 = 3V_i + r_i^2$ where $r_i^2 = 0$ or $1$. All numbers will be one of these $2$ options.
Let all integers, $x_i$ where $r_i^2 = 0$ by of type $A$ and let all integers, $x_j$ where $r_j^2 =1$ by of type $B$.
So if you have $5$ integers and each is of type $A$ or type $B$ then by pigeon hole you must have at least $3$ of same type.
So suppose $x_a, x_b, x_c$ are three that are of one of these two types.
If the three are of the type where $A$ where $r_i^2 = 0$ then you will $x_a^2 + x_b^2 + x_c^2 = 3V_a + 0 + 3V_b + 0 + 3V_c + 0$. And that is divisible by $3$.
If the three are of the type $B$ where $r_i^2 = 1$ then you will have $x_a^2 + x_b^2 + x_c^2 = 3V_a + 1 + 3V_b+1 + 3V_c + 1 = 3V_a + 3V_b + 3V_c + 3$ which is divisible by $3$.
So you will always have at least three integers whose sums of squares is divisible by $3$.
answered 13 mins ago
fleablood
63.4k22679
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Basic pigeon hole. If all integers fall into either type $A$ or type $B$ and you have $n$ integers. Then at least $lceil frac n2 rceil$ will be of the same type.
I hope you can convince yourself of that on your own.
...
Let $x_i = 3*M_i + r_i$ where $r_i = 0, 1,$ or $-1$. All numbers will be one of these three options.
Then $x_i^2 = 9*M_i^2 + 6*M_i*r_i + r_i^2$. Let $V_i = 3*M_i^2 + 2*M_i*r_i$ so $x_i^2 = 3V_i + r_i^2$ where $r_i^2 = 0$ or $1$. All numbers will be one of these $2$ options.
Let all integers, $x_i$ where $r_i^2 = 0$ by of type $A$ and let all integers, $x_j$ where $r_j^2 =1$ by of type $B$.
So if you have $5$ integers and each is of type $A$ or type $B$ then by pigeon hole you must have at least $3$ of same type.
So suppose $x_a, x_b, x_c$ are three that are of one of these two types.
If the three are of the type where $A$ where $r_i^2 = 0$ then you will $x_a^2 + x_b^2 + x_c^2 = 3V_a + 0 + 3V_b + 0 + 3V_c + 0$. And that is divisible by $3$.
If the three are of the type $B$ where $r_i^2 = 1$ then you will have $x_a^2 + x_b^2 + x_c^2 = 3V_a + 1 + 3V_b+1 + 3V_c + 1 = 3V_a + 3V_b + 3V_c + 3$ which is divisible by $3$.
So you will always have at least three integers whose sums of squares is divisible by $3$.
answered 13 mins ago
fleablood
63.4k22679
Basic pigeon hole. If all integers fall into either type $A$ or type $B$ and you have $n$ integers. Then at least $lceil frac n2 rceil$ will be of the same type.
I hope you can convince yourself of that on your own.
...
Let $x_i = 3*M_i + r_i$ where $r_i = 0, 1,$ or $-1$. All numbers will be one of these three options.
Then $x_i^2 = 9*M_i^2 + 6*M_i*r_i + r_i^2$. Let $V_i = 3*M_i^2 + 2*M_i*r_i$ so $x_i^2 = 3V_i + r_i^2$ where $r_i^2 = 0$ or $1$. All numbers will be one of these $2$ options.
Let all integers, $x_i$ where $r_i^2 = 0$ by of type $A$ and let all integers, $x_j$ where $r_j^2 =1$ by of type $B$.
So if you have $5$ integers and each is of type $A$ or type $B$ then by pigeon hole you must have at least $3$ of same type.
So suppose $x_a, x_b, x_c$ are three that are of one of these two types.
If the three are of the type where $A$ where $r_i^2 = 0$ then you will $x_a^2 + x_b^2 + x_c^2 = 3V_a + 0 + 3V_b + 0 + 3V_c + 0$. And that is divisible by $3$.
If the three are of the type $B$ where $r_i^2 = 1$ then you will have $x_a^2 + x_b^2 + x_c^2 = 3V_a + 1 + 3V_b+1 + 3V_c + 1 = 3V_a + 3V_b + 3V_c + 3$ which is divisible by $3$.
So you will always have at least three integers whose sums of squares is divisible by $3$.
answered 13 mins ago
fleablood
63.4k22679
edited 2 mins ago
answered 13 mins ago
fleablood
63.4k22679
answered 13 mins ago
fleablood
63.4k22679
answered 13 mins ago
fleablood
63.4k22679
63.4k22679
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2965193%2fprove-that-given-any-%25ef%25ac%2581ve-integers-there-will-be-three-for-which-the-sum-of-the%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password