Find the maximum number of 5-element subsets of the set such that the intersection of any pair of these subsets has exactly one element.
Iranian Mathematical Olympiad
Solution
The answer is . For the example consider the following family of -element subsets.
Next, we prove that there is no such family with subsets. Without loss of generality we can assume that is among the subsets. By pigeonhole principle there are at least four subsets such that intersection of each of them with is the same. Without loss of generality call these four subsets and , and assume that for all integer numbers , . So by assumption we also know that for all integer numbers . Hence has elements which is a contradiction. ■
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.