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...