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) As 7 integers can be any integers, we know if the squares are of mixed parity odd or even like if out of 4 squares 1,2 or 3 are odd and rest are even the sum will not be divisible by 4. So, all the 4 squares should be either odd or even.

So, in the selected 7 integer squares majority will be either odd or even giving us the required 4 squares whose sum is divisible by 4.

b) there are 52 integers means 52 pigeons and 51 boxes

So, atleast one box must have 2 pigeons/integers.

consider the box with 2 integers to have integers whose sum or diffrence is divisible by 100 like ,

(0,100),(1,99)(2,98),.....(0,0),(50,50)(100,100)(200,100)

Lets say the 1 integer selected is x

the two integers whose su or difference is divisible by 100 are (x,x) (x, 100-x) (x, 100+x)

which means two integers either to be same, or their sum or diffrence to be 100