# Labeling Subsets

### Problem

### Solution

Assume to the contrary that $T$ does not exist. In other words, every ten-element subset $T=X\cup\{Label(X)\}$ for some nine-element $X.$ Importantly, $X\cup\{Label(X)\}$ is a ten-element subset of $S.$ So, consider all nine-element subsets of $S$ with their labels, say, $U=\{(X,Label(X)):\;X\subset S,\,|X|=9\}.$

The number of nine-element subsets of $S$ is less than the number of ten-element subsets because $\displaystyle {20\choose 9}\lt {20\choose 10}.$ Thus, there is a ten-element $T$ which is not in $U,$ i.e., there is a ten-element $T$ which is not in the form $X\cup\{Label(X)\}$ for any nine-element $X.$

### Acknowledgment

This is an extension of problem 13 from the 1987 AIME. The problem itself was discussed in R. Honsberger's *From Erdös To Kiev* (MAA, 1996, 55-56). The problem was offered at the 1988 USA Math Olympiad and posed the same year at Crux Mathematicorum.

|Contact| |Up| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny64257526 |