'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Friday, August 26, 2005

A Pigeon Hole Puzzle

Found a nice puzzle at 'geomblog', maintained by Suresh Venkatasubramanian ( or should one say "sue - raysh ven-cut-a-sub-ra-money-un"?).

In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems.

Spoiler Warning:
If you want to try the puzzle, desist from reading further. What follows is a (tentative) solution (thanks to 'enu' for discussions; enu has an independent solution posted here as a comment).
Let the problems be numbered 1-6 and the sets of solvers of each problem be S1 to S6. Let there be N candidates.
Define roof(x) = the smallest integer strictly greater than x. eg: roof (3) = 4. roof(2.5) = 3. Note that this definition is a bit unconventional. Those guys who got exactly 5 are called special solvers.
The 'Cardinality' of a set is the number of elements in it.

A special case first:
Let N be so that 2N/3 is an integer and let there be exactly 4N correct answers totally (ie sum over problems of number of solvers of each problem). let each problem have exactly 2N/3 crackers.

Consider roof(2N/5). This is the least overlap between each pair of the sets of solvers (statement of problem).
The 'worst case' is when 5*roof(2N/5) (which is anyway greater than 2N) is as close to 2N as possible. This happens when fractional part of 2N/5 is 4/5 and 5*roof(2N/5) exceeds 2N by just 1. It will eventually be argued that the greater 5*roof(2N/5) exceeds 2N by, the more the special solvers.

We look at the overlaps of 5 sets each of cardinality roof(2N/5) on top of any one of the S's (say S1)each of which has 2N/3 elements - note that these 5 sets are intersections of the chosen S1 with solver sets of other problems. Obviously, these overlap sets can overlap among themselves but ** the SUM of the cardinalities of the 5 overlaps is at least one more than THREE TIMES cardinality of S1(which has 2N/3 elements) ** - because as in prev. para, 5*roof(2N/5) = 2N +1 at least.

So we CANNOT have the 5 overlaps so that the overlaps cover NO element of S1 MORE THAN 3 TIMES. In worst case, at least one element of S1 gets covered 4 times by the overlaps. this element corresponds to one guy in S1 who has cracked 5 problems.
(Note: If 5*roof(2N/5) exceeds 2N by more than 1, at least 2 elements in S1 are covered more than 3 times - so, we have 2 solvers in S1 who have got 5 problems. Nothing more to prove).

Now, this same argument goes for each of the six sets S1 to S6 (all have the same cardinality as we assumed)=> a solver who got 5 is present in each of the six sets. And all the six sets cannot share the same special solver (then he would have got all six problems; impossible!). So there ought to be at least two such special guys who got exactly 5. Special case settled.

1.If one of the S's, say Si had LESS THAN 2N/3 elements, the sum of the cardinalities of the 5 overlap sets overlaying set Si (with roof(2N/5) elements each overlap) will exceed thrice the cardinality of Si by MORE than 1. Then from among the crackers of problem of Si, we readily have at least 2 guys who solved 5 (recall, nobody solved 6). So, no problem can have a solver set of less than 2N/3 guys.

2. The sum of total correct answers (summed over all problems and all solvers) can be 4N+1 at the most -in the above special case, we had 4N (also note that if there are a total of 4N+2 or more correct answers, there already are two or more special solvers and the problem disappears). But this case of 4N+1 correct answers need not be dealt with specially - with 'only' 4N answers we already have the required number of at least 2 special solvers. 1 more correct answer from someone will only increase the number of special solvers. Nothing to worry.

3. The sum of total correct answers can of course be less than 4N but that would lead to one or more of the S's having less than 2N/3 elements - this is already done above in (1).

4. If 2N/3 is fractional, we would have necessarily have to have some sets of solvers with floor(2N/3) elements or less. let Si be such a set. Then, 3* cardinality (Si) is STRICTLY less than 2N. of course 5 *roof(2N/5) is always strictly greater than 2N. So, the sum of the cardinalities of the 5 overlapping sets on Si will be at least two more than thrice the cardinality of Si => at least 2 special solvers in Si itself.

With that we seem to have exhausted all possibilites :)


Post a Comment

<< Home