Pigeonhole principle theory pending

PHP1: n holes, n+1 pigeons, at least 1 hole with > 1 pigeons.
PHP2: n holes, nk+1 pigeons, at least 1 hole with > k pigeons.


Q1. Pr. th. If there are 5 points inside a unit square, then the distance between at least any two points is less than 1/sqrt(2).
A1. Divide in 4 smaller squares => at least 2 will be inside one square. Max distance inside that square is 1/sqrt(2).
Q2. There are 14 sock pairs in a basket. How many you need to pick to be sure that you have 1 pair at least.
A2. 15.

PHP3: If mean of n +ive integers is k then at least 1 of them is >= k and at least 1 of them is <= k.
Proof:
If a1 = a2 = ... an = k then H.P.
If a1 <= a2 <= a3 ... <= an
then if a_i > k => a_j < k H.P.

Q3.

Suppose numbers from 1 through 20 are placed in some order around a circle.

Prove that

i) The sum of some three consecutive numbers must be at least 32.

ii) The sum of some four consecutive numbers must be at least 42.

Let the triplets be (a1,a2,a3) (a2,a3,a4) ... (a20,a1,a2)
S1 = a1+a2+a3
S2 = a2 + a3 + a4
....
Sigma(ai) = 210
Sigma(Si) = 210*3 = 630

By PHP3, At lest one Si >= 630/20 = 31.5
Similarly for the 4-tuple case Si >= 840/20 = 42
H.P.

Q4) There are 50 consecutive integers. Can we choose any four of them, such that (a1 - a2)(a3 - a4) is a multiple of 2009.
S4.
2009 = 41*49
Since there are 50 integers and if we take modulo wrt 49 there are only 49 distinct values.
So there will be at least 2 integers with same remainder wrt 49.
If we pick them as a1,a2 we have a1-a2 as a multiple of 49.
In this case though, there is only 1 possible pair which is 1,50.

Now apply PHP again on the remaining 48 integers.
Again there are only 41 possible remainders wrt 41 and using PHP we can again pick a3,a4 s.t. a3-a4 is a multiple of 41.
H.P.