MathDB

1988 USAMO Problem 3

Source:

July 27, 2011

USA(J)MOUSAMOpigeonhole principleceiling functionfunctionboolean lattice method

Problem Statement

A function

f(S)

assigns to each nine-element subset of

S

of the set

\{1,2,\ldots, 20\}

a whole number from

1

to

20

. Prove that regardless of how the function

f

is chosen, there will be a ten-element subset

T\subset\{1,2,\ldots, 20\}

such that

f(T - \{k\})\neq k

for all

k\in T

.

Back to Problems View on AoPS