© Friederike Hofmann, MATH+
Authors: Olaf Parczyk, Silas Rathke (FU Berlin)
Project: Learning Extremal Structures in Combinatorics (EF 1-12)
Challenge
In the technical department, ten elves work in ten offices on various technical problems that may arise in the world’s largest gift production. However, due to climate change and the associated rise in sea levels, three offices have suffered water damage and are now unusable. So, we have ten elves but only seven offices. What should be done now?
The solution is found quickly: only seven elves come to the technical department each day, and the other three work from home. Security elf Willi has the important task of equipping ten elves with keys for offices. Each key fits only one specific office lock and is given to an elf. An elf can even receive multiple keys. Importantly, offices can also be opened by multiple keys.
Willi has a clear rule for key distribution: after the keys are distributed, it should not matter which seven elves come to the technical department. It must always be possible to assign the seven elves to the seven functional offices, such that each elf has access to an office with the corresponding key. Exchanging or borrowing keys is strictly prohibited.
Of course, Willi could give each elf a key for each office, meaning he would need to make a total seventy keys. However, Willi is considering whether it is possible with fewer keys. He is looking for the smallest number, k , of keys he must distribute in total to fulfill the previous rule. Which statement about k is correct?
Answer Options:
- k < 20
- 20 \le k < 25
- 25 \le k < 30
- 30 \le k < 35
- 35 \le k < 40
- 40 \le k < 45
- 45 \le k < 50
- 50 \le k < 55
- 55 \le k < 60
- 60 \le k
Project Context:
In the project “Learning Extremal Structures in Combinatorics”, we use approaches from the field of artificial intelligence and machine learning to find new constructions for graphs with specific properties. The presented task can be well formulated as an extremal problem in graph theory, similar to the problems we study in this project.