Prove that given any five integers, there will be three for which the sum of the squares of those integers is divisible by 3.

Question

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?

Answer 1

Any square integer must be congruent to either 0 or 1 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+0\equiv 0$ or $1+1+1\equiv0$ mod 3.

Answer 2

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.

Answer 3

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

Answer 4

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$

Answer 5

Any integer is in one of 3 sets:

• multiples of 3
• integers of the form $3k+1$ where $k$ is an integer
• integers of the form $3k+2$ where $k$ is an integer

These are the congruency classes, modulo 3. Think of these as your pigeonholes.

Of the 5 integers $x_i^2$, if any 3 of them are all in the same congruency class, the sum of those 3 integers is divisible by 3.

If any 3 of them are 1 in each of the 3 congruency classes, their sum is divisible by 3.

Otherwise, your given integers are in at most 2 congruency classes, with at most 2 in any congruency class. This means you have at most $2\cdot2=4$ integers. But you have five. Contradiction. This proves your result.

Alternatively: you have 5 integers and 3 pigeonholes to put them in, and you may not put more than 2 integers into the same hole. Two each in 2 holes is 4. Thus you must use all 3 holes. And the sum of 3 integers, one in each hole, is divisible by 3.

In fact it proves a stronger result because it works for any 5 integers. You don't need to know that no integer's square is congruent to 2.

Answer 6

Any integer is of one of the following forms:

• $3k + 0$ (these are the multiples of 3)
• $3k + 1$
• $3k + 2$

where $k$ is an integer.

---

If we square these, we get

• $9k^2$
• $9k^2 + 6k + 1$
• $9k^2 + 12k + 4$

If we then look at the remainders of these when divided by $3$, because $9$, $6$, and $12$ are all divisible by $3$, we see that

• $9k^2 \equiv 0 \pmod 3$
• $9k^2 + 6k + 1 \equiv 1 \pmod 3$
• $9k^2 + 12k + 4 \equiv 1 \pmod 3$

So any squared integer is equivalent to $0$ or $1$, modulo $3$.

These will be our two pigeon holes.

---

Applying the pigeonhole principle to the squares of our 5 integers, we see that either at least 3 have remainder $0$, or at least 3 have remainder $1$. Let's call these 3 integers $x_1$, $x_2$, and $x_3$.

In the former case, $x_i^2 \equiv 0 \pmod 3$ and so the sum of these $x_1^2 + x_2^2 + x_3^2 \equiv 0 + 0 + 0 \pmod 3 \equiv 0 \pmod 3$

In the latter case, $x_i^2 \equiv 1 \pmod 3$ and so the sum of these $x_1^2 + x_2^2 + x_3^2 \equiv 1 + 1 + 1 \pmod 3 \equiv 0 \pmod 3$

QED