Library / /9 of 10

, 2023

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Switzerland

Problem:

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.

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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