Given 20 diff jewelry, wear 5 per day. proof that after 267 days at least one pair of jewelry would be wear in 15 diff days.

combinatoricsdiscrete mathematicsnumber theorypigeonhole-principle

Given 20 different jewels.
which 5 of them can be wear per single day.

proof that after 267 days, there would be at least one pair of jewelry that wears together (in other combination) in 15 different days.

I need to prove this claim using the pigeonhole principle.
I've tried to come with a solution by taking all the possible pairs fitting them into the 5 possible positions of the jewelry who can be wear per day.
then, to prove that the 5th jewel will provide a combination which has been already used in the last 15 days.
I having a hard time to provide a combinatorial solution and declaring what is the pigeonholes and what is the pigeon number.

Best Answer

For each day, $\binom52=10$ of the $\binom{20}2=190$ possible pairs of jewels will be worn. Over $267$ days, this makes $2670$ pairs worn, but $\frac{2670}{190}=14.05\ldots>14$. This means that at least one pair must have been worn at least $15$ times.

The holes are the possible pairings of jewels and the pigeons are the pairs actually worn together on some day.

Related Question