How to seat $2n$ people, where each person hates at most $n-1$ people, such that everyone sits besides his/her friends in a circle?

124 Views Asked by At

This question is a homework question. My professor says to make use of the extremal principle. I attempted to solve. I have seen a similar question on this website, but it's solution makes use of graph theory, and I know very little of graph theory.

Consider the person who hates the most amount of people, call him Bob. Bob hates at most $n-1$ people and thus has at least $n$ friends.

Suppose that that all of Bob's friends are friends of each other. But then the people outside of the friend group are hated by all the people in the 'in' group. If you are a member of the out group, you are hated by at least $n$ people; thus, we have arrived at a contradiction. So you can't have friends of a person liking each of Bob's friend.

I don't know how to continue this line of thinking. I feel it has to do with the selection of the friend who doesn't like the other friends and working from there. Other ideas I have considered is a friend group who have the most mutual hate, a group that has the most mutual friends, pairs of people, a person who has the most amount of friends (but I don't think that's useful).

Another idea is to consider the arrangement with minimal pairs of enemies who sit together. Suppose there is a pair of enemies who sit together. I'm working on this reasoning.

1

There are 1 best solutions below

1
On

Given a circular arrangement of the $2n$ people, there is some number neighbour pairs made of enemies. Among all arrangements, consider one that minimizes this number.

Assume that in this arrangement, there is at least one neighbour pair of enemies, i.e., the circular arrangement looks $$\tag1x_1,x_2,\stackrel\longrightarrow\ldots, x_{2n},(x_1) $$ where $x_1,x_2$ are enemies. Assume $x_1,x_k$ are friends where $3\le k\le2n-1$. Then we can flip part of $(1)$ to obtain $$\tag2 x_1,x_k,\stackrel\leftarrow\ldots,x_2,x_{k+1},\stackrel\longrightarrow\ldots, x_{2n},(x_1).$$ By minimality of $(1)$, we conclude that $x_2,x_{k+1}$ must be enemies. Thus, the number of $x_2$'s enemies among $x_4,\ldots,x_{2n}$ is at least as big as the number of $x_1$'s friends among $x_3,\ldots,x_{2n-1}$. This latter number is at least $n-1$ so that $x_2$ has (including $x_1$) at least $n$ enemies, contradiction. Thus our minimal arrangement has no neighbour pair of enemies.