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

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.

• Given that you are to use induction, where would you start? In other words, what is the general principle behind induction? Commented May 25, 2014 at 12:58
• Assumptions (1) friendship is reciprocal. (2) If I am in a group of n people (n > 1) then I am friends with at least half the group rather than at least half of the other people in the group (which would be a more common form of expression) i.e. $\lceil \frac{n}{2}\rceil$ rather than $\lceil \frac{n-1}{2}\rceil$ Commented May 25, 2014 at 16:13

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.

• what was wrong with this and this
– S L
Commented May 25, 2014 at 13:44
• @SantoshLinkha It is perfectly alright. You just need to generalize it.
– eem
Commented Aug 18, 2019 at 15:39
• if n = 2k + 1, then all people only have k+1 friends, some of them are friends of Person (n+1). Taking Person (n+1) out of the group, then the number of friends that friends of Person(n +1) have is k, which is less than (2k +1) /2, n/2. The rest of the people cannot sit in a circle, per assumption of the statement. Your clause regarding n=2k+1 doesn't cover this case. Commented Apr 7, 2020 at 19:37

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.

• Yes you have. Suppose A sits next to B being friends and P is friends with B but not A: then in a sequence A, P, B poor A will be lonely . (Assuming that A is not friends with his other neighbour) Commented May 25, 2014 at 13:21
• Won't A still be sat next to B? This is a circular table. Commented May 25, 2014 at 13:22
• No, I'm seating P anywhere - in particular between A and B. Commented May 25, 2014 at 13:23
• Oh I see what you mean, yeah this isn't as simple as I thought. Commented May 25, 2014 at 13:24
• Agreed. See my comment on other answer: differentiate between even and odd already present. Commented May 25, 2014 at 13:25

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}$

 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.

• if n = 2k + 1, then all people only have k+1 friends, some of them are friends of Person (n+1). Taking Person (n+1) out of the group, then the number of friends that friends of Person(n +1) have is k, which is less than (2k +1) /2, n/2. The rest of the people cannot sit in a circle, per assumption of the statement. Your clause regarding n=2k+1 doesn't cover this case. Commented Apr 8, 2020 at 2:22
• if you remove one person, then "n" becomes 2k.. half of that would be k. Still valid, right? 2k people need only k friends. (to avoid any confusion, I am using complete induction) Commented Apr 14, 2020 at 12:09