Given 7 arbitrary integers,sum of 4 of them is divisible by 4

Given 7 arbitrary integers,show that sum of 4 of them is divisible by 4.

It's possible to consider different cases of congruence of 4 given numbers modulo 4 and solve the problem,but is there an easy way using pigeon hole principle?

Solution 1:

I have chosen to do it this way because it generalises quite easily

Oh, and it's a simple repeated application of the pigeonhole principle...

Firstly, we'll prove that in any group of three numbers there exists two where the sum is divisible by 2. Actually this is quite straightforward - either two of the numbers are 0 mod 2 or two are 1 mod 2 so by pigeonhole we're done.

Now, take out the two numbers with sum 0 mod 2 and put them aside as a pair. Now we have 5 numbers left. Repeat: take out two numbers with sum 0 mod 2. Now we have 3 numbers left. Do it one last time: take out two numbers with sum 0 mod 2.

Now we have three pairs of numbers, each of which has a sum of 0 mod 2. But, mod 4, we must have either two pairs which are both 0 or two pairs which are both 2 (yet again by pigeonhole). $\square$

Now this may seem like a bash, but it is pretty much the only way to solve harder problems (such as the follow-up) without using a computer.

Follow-up question:

Find the smallest positive integer N such that in any list of N positive integers, all of which have only 2,3 or 5 as factors, that there exists a group of 4 numbers with a product which is a perfect fourth power.