Track / Stage 7 / 66 of 300 #1946 of 2444

Problem 1946

National Olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.1 Prove it Switzerland — Second Round · Switzerland · 2023

during the World Cup, there are $n$ different Panini stickers to collect. Marco's friends are trying to complete their collection, but nobody has a full set of stickers yet! A pair of his friends are said to be wholesome if their combined collection has at least one of each sticker. Marco knows the contents of everyone's collections, and wants to take them all to a restaurant for his birthday. However, he doesn't want any wholesome pairs sitting at the same table.

a. Show that Marco might need to reserve at least $n$ different tables.

b. Show that $n$ tables will always be enough for Marco to achieve his goal.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

to show that at least $n$ different tables are necessary, suppose we had $n$ people, each of which are only missing a sticker, with each person missing a different sticker. Any two of these people are wholesome together, so they must be seated at different tables.

Now, to show that $n$ is always sufficient, simply distribute the friends as follows: associate each type of sticker to a table. The people owning this sticker will not be seated at this table. Make the table instead available to everyone not owning that sticker, and let each person choose whichever table they want to sit in of the options available to them (i.e., the tables corresponding to the stickers they don't own) or just pick it for them. This way, two people who are wholesome cannot be sitting in the same table because if this was the case, they would be missing the same sticker, a contradiction.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.