MathDB

Santa and Desirable Gifts

Source: 2013 Baltic Way, Problem 6

December 31, 2013

inductiongraph theorycombinatoricsmatchingsHall s marriage theorem

Problem Statement

Santa Claus has at least

n

gifts for

n

children. For

i\in\{1,2, ... , n\}

, the

i

-th child considers

x_i > 0

of these items to be desirable. Assume that

\dfrac{1}{x_1}+\cdots+\dfrac{1}{x_n}\le1.

Prove that Santa Claus can give each child a gift that this child likes.