A school has 2021 students, each of which knows at least 45 of the other students (where "knowing" is mutual). Show that there are four students who can be seated at a round table such that each of them knows both of her neighbours.
Problem
Source: Bundeswettbewerb Mathematik 2021, Round 2 - Problem 2
Tags: combinatorics, combinatorics proposed, graph theory, graph cycles
22.09.2021 14:53
This is a well known result due to rieman. It appeared in the Indian TST .
22.09.2021 14:56
Let the corresponding acquaintance graph be $G$. It is enough to have that (by a well known result of Reiman) \[|e(G)| > \frac{2021}{4}(2021+\sqrt{4 \cdot 2021 - 3}) \]or that $|e(G)| \geqslant 32790$. We have $|e(G)| \geqslant \frac{2021 \cdot 45}{2} > 32790$ and we're done.
29.09.2021 18:24
Tintarn wrote: A school has 2021 students, each of which knows at least 45 of the other students (where "knowing" is mutual). Show that there are four students who can be seated at a round table such that each of them knows both of her neighbours. It impossible that there are 2021 vertices with degree 45 (the number of vertices with an odd degree is even). Thus there is a vertice $X$ with $\deg(X)\geq46$. Let $O$ be a set of 46 neighbours of $X$. If two different elements of $O$ have a common neighbour different from $X$ we have a cycle of lenght 4. If any two different vertices in $O$ haven't a common neighbour different from $X$ thre are at least $1+46\cdot44=2025$ vertices which is impossible.
20.10.2021 17:49
starchan wrote: Let the corresponding acquaintance graph be $G$. It is enough to have that (by a well known result of Reiman) \[|e(G)| > \frac{2021}{4}(2021+\sqrt{4 \cdot 2021 - 3}) \]or that $|e(G)| \geqslant 32790$. We have $|e(G)| \geqslant \frac{2021 \cdot 45}{2} > 32790$ and we're done. Sadly, Reiman fails in this problem. We need $\frac{2021 \cdot 45}{2} > \frac{2021}{4}(1+ \sqrt{4 \cdot 2021-3})$, which turns out to be false ($45472.5<45924.387$). Maybe recheck your calculation. All $2021$ people cannot know exactly 45 students because $\frac{2021 \cdot 45}{2}$ is not an integer, hence one student knows at least $46$ students. Assume that Alice knows at least $46$ students. Consider these $46$ students. Since $44 \cdot 46 = 2024 > 2021-1$, two people, called Bob and Carl, knows at one student in common, which is Daniel. Put Alice, Bob, Daniel, Carl in a circle, we are done.