Labeling Subsets

Problem

Labeling Subsets

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 Bogomolny

72083909