34 Use the pigeonhole principle to prove each of the followi

34. Use the pigeonhole principle to prove each of the following statements about numbers:

(a) Given any seven integers, there will be four for which the sum of the squares of those integers is divisible by 4.(Consider squaring the elements in Z4).

(b) show that among any 52 integers, there are two whose sum or difference is divisible by 100.(use Z100)

Solution

a) If one, two or three squares are odd then 4 does not divide the sum of the four squares. Therefore either all are odd or all are even. So, in seven squares there is a majority of either evens or odds giving us the required four of either which sum is divisible by 4.

b)It suffices to just consider 52 of the remainders mod 100. If two of the 52 integers are equal, then 100 divides their
difference. If all of the integers are distinct, call them Ai, i=1,2,..,52 then either 100 divides a sum of two, or
all 100-Ai are absent from the list. So 52 integers are present and 52 integers are absent for a total of at least 104
remainders mod 100 when there are only 100 remainders. Therefore, there are two remainders such that
Ai = Aj, or Ai = 100 - Aj giving 100 |Ai+Aj or 100|Ai-Aj