In a class of $ n\geq 4$ some students are friends. In this class any $ n - 1$ students can be seated in a round table such that every student is sitting next to a friend of him in both sides, but $ n$ students can not be seated in that way. Prove that the minimum value of $ n$ is $ 10$.
Problem
Source: Turkey TST 2009, Problem 6
Tags: combinatorics unsolved, combinatorics
09.04.2009 17:35
Why nobody is interested? I think this is a nice problem. It doesn't involve a special idea I know, but it is enjoying to deal with cases.
19.04.2009 12:13
Nice problem! Solution: Case 1:$ n\le 6$ If n satisfies the conditon, Because every $ n-1$ students forms a circle, so each student has at least $ 2$ friends. In addition if a student has only $ 2$ friends, then consider the $ n-1$ students that only includes $ 1$ friends of him/her, the $ n-1$ students cannot form a circle, a contradiction. Therefore each student has at least $ 3$ friends. Choose a student arbitrarily and call him/her $ A$, the other $ n-1$ students forms a circle. Since $ n-1\le 5$ and $ A$ has at least $ 3$ friends, $ A$ must have $ 2$ friends who are adjacent on the circle, and then we can add $ A$ to the circle i.e. we get a circle of the all $ n$ students, a contradiction. Case 1 is done. Case 2:$ n=7$ If $ n=7$ satisfies the conditon, The same as in Case 1 we have that each student has at least $ 3$ friends. But $ 7$ is an odd number, so there exist a student who has at least $ 4$ friends. Call him $ B$. Consider the circle formed by other $ 6$ students,.Since $ B$ has at least $ 4$ friends, he must have $ 2$ friends who are adjacent on the circle, and then we can add $ B$ to the circle i.e. we get a circle of the all $ 7$ students, a contradiction. Case 2 is done. Case 3:$ n=8$ If $ n=8$ satisfies the conditon, The same as in Case 1 we have that each student has at least $ 3$ friends. Choose a student arbitrarily and call him/her $ C$, then $ C$ has at least $ 3$ friends. Due to the condition the other $ 7$ students form a circle.Assume these students are $ 1,2,3,4,5,6,7$, respectively. And they are the same order on the circle. If $ C$ has at least $ 4$ friends, then there will be $ 2$ of them who are adjacent on the circle, and then we can add $ C$ to the circle i.e. we get a circle of the all $ 8$ students, a contradiction. So $ C$ has exactly $ 3$ friends. Since $ C$ is chosen arbitrarily, each student has exactly $ 3$ friends. w.l.o.g we can assume $ C$'s friends are $ 2,4,6$, then $ C,2,4,6$ have no more friends, and $ 1,3,5,7$ each has one more friend. Because $ 1$ and $ 7$ are already friends, so there are only two possible cases: (1) $ 1$ and $ 5$, $ 3$ and $ 7$ are friends respectively. But then we have a circle of all $ 8$ students: $ 6-C-2-3-4-5-1-7-6$, a contradiction. (2) $ 1$ and $ 3$, $ 5$ and $ 7$ are friends respectively. But then we have a circle of all $ 8$ students: $ 6-C-4-3-2-1-7-5-6$, a contradiction, too. Case 3 is done. Case 4:$ n=9$ If $ n=9$ satisfies the conditon, we have that each student has at least $ 3$ friends and $ 9$ is an odd number, so there exists a student who has at least $ 4$ friends.Call him/her $ D$. Due to the condition the other $ 8$ students form a circle.Assume these students are $ 1,2,3,4,5,6,7,8$, respectively. And they are the same order on the circle. If $ D$ has at least $ 5$ friends, similar to previous case we get that two of them are adjacent on the circle which leads to a contradiction. So we assume $ D$ has exactly $ 4$ friends, and w.l.o.g we assume that they are $ 1,3,5,7$, respectively. Next color students $ 1,3,5,7,D$ black and color students $ 2,4,6,8$ white. Then all known pair of friends are one black student and one white student. Take $ 5$ black students and $ 3$ white students. Due to the condition they form another circle. Since there are only $ 3$ white students on the latter circle, we have that there exists two adjacent students on this circle who are both black. w.l.o.g there are only two possible relative position of them on the former circle: (1) $ 1$ and $ 3$ ; (2) $ 1$ and $ 5$. (1) $ 1$ and $ 3$ are friends.But then we have a circle of all $ 9$ students:$ 2-D-8-7-6-5-4-3-1-2$, a contradiction. (2) $ 1$ and $ 5$ are friends.But then we have a circle of all $ 9$ students:$ 8-D-4-3-2-1-5-6-7-8$, a contradiction, too. Case 4 is done. Now we have proved that $ n$ is at least $ 10$.Finally we construct an example to show that $ n=10$ satisfies the condition. The example is: Ten students are $ 1,2,3,4,5,6,7,8,9,10$, respectively. $ 1-2-3-4-5-6-7-8-9-1$ is a circle. All other pairs of friends are $ 10-3$, $ 10-6$, $ 10-9$, $ 1-5$, $ 2-7$, $ 4-8$.It is not hard to check that this example satisfies the condition. END
29.09.2021 20:14
Cute and nice problem. I think I found an alternative that gives more intricate details about the degrees and skips the casework mostly. Firstly let $n \le 9$. Let the number of edges in the graph be $e$. Then consider the vertex $v$ with the greatest degree and the cycle of the remaining $n-1$ vertices. We see that the our vertex cannot be connected with two adjacent vertices in the $n-1$ cycle. Thus we see that by the pigeonhole principle, $deg(v) \le [\frac{n+1}{2}]$ Therefore, $e \le [\frac{n}{2}[\frac{n+1}{2}]]$ By considering two chosen cycles that a vertex is a part of ,we see that $\delta(G) \ge 3$. We now claim that $G$ contains a 4-cycle. For this consider the vertex with smallest degree $u$. Call three of its adjacent vertices $A,B,C$. Now, as $e \le [\frac{n}{2}[\frac{n+1}{2}]] < [\frac{n^2}{4}]$, $G$ is triangle free. Thus no two of $A,B,C$ are adjacent. Now, we prove that at least two $A,B,C$ have a common neighbour apart from $u$ which will give the claim. For this assume the contrary. Then we would get that since their neighborhoods apart form $u$ are disjoint $n \ge 2+2+2+4=10$ ,a contradiction. Thus $G$ contains a $4-cycle$. Thus, by a well known result $e > \frac{n}{4} (1+ \sqrt{4n-3})$ However this just gives that $n$ upto $8$ dont' work. So,we for $n=9$ we just proceed as above or can adapt an alternative since we got more structure. This bound just implies $n=9$, then there are atleast $5$ vertices of degree $4$ which is just extra info it gives(may or may not use for the casework ). FInish by giving a construction,which isn't too difficult.