K1) The SMO country has 1111 inhabitants. The eleven players of the Liechtenstein national team distribute autographs to all inhabitants, whereby no inhabitant receives an autograph twice (i.e. each inhabitant receives either no autograph or one autograph from each player).
(a) How many possibilities are there for a resident to obtain an autograph?
(b) After the distribution, the inhabitants realize that no two of them have received autographs from exactly the same players. Show that there are two inhabitants who together have exactly one autograph from each player.
This one wants a proof. Work it on paper, read the official solution, then mark
yourself honestly — the ladder only means something if the record is true.
Official solution
## Solution (Patrick):
Subtask a) Each inhabitant can either receive an autograph from each player or not receive an autograph. This means that there are a total of 211=2048 different ways to obtain autographs.
Subtask b) Now the task is to distribute these 2048 possibilities among the 1111 inhabitants so that each inhabitant receives a different possibility. It must now be shown that 2 of these 1111 inhabitants complement each other in such a way that together they have each autograph exactly once.
Since 2 possibilities always complement each other, one can imagine 1024 drawers, whereby each drawer represents one possibility as well as the inverse possibility, i.e. the possibility that contains exactly every other autograph once. Since 1111 possibilities are now distributed across these 1024 drawers, at least one drawer contains 2 possibilities, so there are also 2 inhabitants who together have all autographs once.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic, difficulty and ordering added
by this site.