Let X be a set with 9 elements. Given a partition π of X, let π(h) be the number of elements in the part containing h. Given any two partitions π1 and π2 of X, show that we can find h ≠ k such that π1(h) = π1(k) and π2(h) = π2(k).
Solution
Easy.
At least 4 elements x must have the same value of π1(x). For if not, then certainly every part (in the partition by π1) has size 3 or less. Moreover, there can only be one part size 3 and one part size 2 (since 2·3 and 2·2 ≥ 4), and three parts size 1, but that only covers 3 + 2 + 3 = 8 elements. Contradiction.
These 4 elements cannot all have different values of π2, because 1 + 2 + 3 + 4 > 9, so π2 cannot have 4 or more different sized parts. So at least two of the 4 elements have the same value of π2.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998