Putnam 1995, Problem B-1

For a partition \( \pi \) of \( \{1,2,3,4,5,6,7,8,9\} \), let \( \pi(x) \) be the number of elements in the part containing \( x \). Prove that for any two partitions \( \pi \) and \( \pi' \), there are two distinct numbers \( x \) and \( y \) in \( \{1,2,3,4,5,6,7,8,9\} \) such that \( \pi(x) = \pi(y) \) and \( \pi'(x) = \pi'(y) \). [A partition of a set \( S \) is a collection of disjoint subsets (parts) whose union is \( S \).]

Solution:
For a given \( n \), no more than three different values of \( \pi(x) \) are possible (four would require one part each of size at least 1,2,3,4, and that's already more than 9 elements). If no such \( x, y \) exist, each pair \( (\pi(x), \pi'(x)) \) occurs for at most 1 element of \( x \), and since there are only \( 3 \times 3 \) possible pairs, each must occur exactly once. In particular, each value of \( \pi(x) \) must occur 3 times. However, clearly any given value of \( \pi(x) \) occurs \( k \pi(x) \) times, where \( k \) is the number of distinct partitions of that size. Thus \( \pi(x) \) can occur 3 times only if it equals 1 or 3, but we have three distinct values for which it occurs, contradiction.