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?
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.
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$
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 + 6k + 1$
- $9k^2 + 12k + 4$
If we then look at the remainders of these when divided 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$
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.
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.
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$.