Induction: Prove that it is possible to seat people in a circle so that everyone sits beside a friend

Question

Use induction to prove the following:

If each person in a group of $n$ people is a friend of at least half the people in the group, then prove that it is possible to seat them in a circle so that every one sits next to a friend of his/hers.

No idea how to solve this problem.

Answer 1

My attempt or more of a hint: for n=2 and 3 the proof is trivial. n=2: persons A, B both are friends and hence statement is true. n=3: persons A, B, C. Let AC,BC be pairs of friends. Clearly: A, B, C, A is a solution.

Let it be true for n=k-1 and n=k. When we add the (K+1) person, take a pair of that person's friends (say, $p_m$, $p_{m+1}$) and let $p_{k+1}$ be in their middle. By induction, $p_m$ and $p_{m+1}$ were already seated next to their friends, so:

1. $p_m$ and $p_{m+1}$ are friends
2. $p_m$ and $p_{m-1}$ are friends
3. $p_{m+1}$ and $p_{m+2}$ are friends

With the new configuration after placing $p_{k+1}$ between $p_m$ and $p_{m+1}$, all the three have two friends, 1 on each side:

1. $p_m$ has $p_{m-1}$ and $p_{k+1}$
2. $p_{k+1}$ has $p_m$ and $p_{m+1}$
3. $p_{m+1}$ has $p_{m+2}$ and $p_{k+1}$

[Edit] to prove that $p_m$ and $p_{m+1}$ can be found (that is two people friends of each other and also of $p_{k+1}$: assume them ($p_m$ and $p_{m+1}$) as one person and then by induction, since the statement is true for n=k-1, we have proved that two such people can be found.

Answer 2

Sit $k$ people down satisfying such a condition. We must find a place to insert a new person (P) that knows at least half of the people so as to not break the rule.

Now split into two cases:

$1$) Person P knows $\lceil \frac{k}{2}\rceil + 1$ or more people. In this case, by the pigeonhole principle there must be two people that P knows sitting together. So we can seat P in between those.

$2$) Person P knows exactly $\lceil \frac{k}{2} \rceil$ people. If it is still the case that P knows two people sitting together then we are done.

The only remaining possibility is that the people person P knows are sat in an alternating fashion between people that P doesn't know. But here we can seat P anywhere and we still have not broken the rule.

Answer 3

Base Case: The statement is true for $2$ people (and less than two doesn't count as a group). Because each must be friends with the other.

Induction Hypothesis: Let the statement be true for $n$ people.

Inductive Step: If true for $n \ge 2$ people and a new one arrives, consider separately $n$ even or odd.

If $n = 2k$, then the new arrival makes a group of $2k + 1$, and by the premise of the problem, everyone in this new group must be friends with at least $k + 1$ of the group. So the new arrival has $k + 1$ friends already seated and at most $k - 1$ people separating them so he must have two adjacent friends he can be placed between.

If $n = 2k + 1$ his arrival makes $2k + 2$ and he must have $k + 1$ friends in that group. Again they are already seated with at most $k$ people separating them so there must be two adjacent that he can be seated between.

So, in either case the statement is true for $n + 1$, and is therefore true for all $n \ge 2$.

The key to the solution is that with the arrival of a new person he has in any case a minimum of $k + 1$ friends among $2k$ or $2k + 1$ people already seated.