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?

  • 1
    Here's a horrible solution, that a computer would find, that actually works: start with the polynomial $\prod_{1\le i<j<k\le 5} (x_i^2+x_j^2+x_k^2)$; divide it by $x_1^3-x_1$ and keep only the remainder; divide that remainder by $x_2^3-x_2$ and keep only the remainder; do the same for $x_3^3-x_3$, $x_4^3-x_4$, and $x_5^3-x_5$; and check that the resulting polynomial has all its coefficients divisible by $3$. (Other than being perverse, I mention it because it's a good algebra exercise to understand why this really is a solution.) – Greg Martin Oct 22 at 6:07
  • Hint: $ $ Pigeonhole Principle $ $ If we place $> n^2$ objects into $n$ boxes then some box has $> n $ objects. Here $\,n = 2\,$ is the number of values taken by $x^2\pmod{\!3},\,$ viz $\,0,1\ \ $ – Bill Dubuque Oct 22 at 21:57

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.

  • 19
    Interesting note: You don't even need to square the integers. The statement "Of five integers, three of them will add to a number divisible by 3" is also true by a slightly longer argument. – Carl Oct 22 at 6:56
  • 7
    That's also the reason that any set of 5 cards in the board game Risk contains a cashable set. Given two cards of one kind and two cards of another, the 5th card has to either complete a 3-of-a-kind or complete the set-of-all-3. (Call the three kinds 0, 1, and 2, and you can see that the sum of a cashable set is always divisible by 3.) – chepner Oct 22 at 15:52

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

QED

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.