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.
 A: 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. 
A: 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.
A: 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:


*
 
* $p_m$ and $p_{m+1}$ are friends 
 
* $p_m$ and $p_{m-1}$ are friends 
 
* $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:


*

* $p_m$ has $p_{m-1}$ and $p_{k+1}$

* $p_{k+1}$ has $p_m$ and $p_{m+1}$

* $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.
