© Vira Raichenko, MATH+
Authors: Olaf Parczyk, Silas Rathke
Project: EF 1-12
Challenge
Politics is not easy! Not even at the North Pole. There, ten elected bureaucracy elves decide on the laws in the eternal ice. But now, a huge dispute has arisen about what should be spent on next year. Some want to use the money to make better gifts for the children. Others prefer to invest it in a lighter sleigh to relieve the reindeer, and still, others want to equip the elf village with more modern heaters. The dispute has become so bitter that a total of 20 hostilities have arisen. A hostility always consists of exactly two bureaucracy elves who have clashed so much that they no longer speak to each other. To smooth things over, Chief Elf Olav invites the ten bureaucracy elves to a working meeting at the Elf Office. There, solutions should be worked on in different rooms. Unfortunately, a single room is not enough for this because feuding bureaucracy elves cannot work in the same room. Additionally, Olav has lost track of who is feuding with whom – he only knows that there are exactly 20 hostilities. Therefore, Olav wants to distribute the rooms in such a way that they would be sufficient for all possible types of hostilities.
What is the smallest number k of rooms that Olav needs, such that he can divide the ten bureaucracy elves into k rooms in any case with 20 hostilities, without feuding elves ending up in the same room?
Possible Answers
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Project Context
In the project “Learning Extremal Structures in Combinatorics,” we employ approaches from the field of artificial intelligence and machine learning to discover new constructions for graphs with specific properties.The task at hand can be effectively formulated as an extremal problem in graph theory, akin to the problems we investigate in this project.