-1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But you can't be sure all the numbers you mentioned are 0 mod 2!! $\endgroup$ – Hamid Reza Ebrahimi Dec 14 '17 at 8:44
  • $\begingroup$ But the sums of the pairs of numbers are $\endgroup$ – Wen Dec 14 '17 at 8:45
  • $\begingroup$ I don't get it: how could you complete your proof? Please explain more after having 3 pairs of numbers whose sum are 0 mod 2 $\endgroup$ – Hamid Reza Ebrahimi Dec 14 '17 at 8:49
  • 1
    $\begingroup$ Each pair must be either 0 or 2 mod 4, since they are even. By pigeonhole, either (2 are 0 mod 4) or (2 are 2 mod 4) so adding those two pairs together gives four numbers which sum to 0 mod 4 $\endgroup$ – Wen Dec 14 '17 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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