0
$\begingroup$

Each of the guests know: a) more than half of the guests b) at least half of the guests. Prove that in both of these cases it is possible to arrange them to sit around a round table so that everyone knows the two people next to them.

I believe that if we prove b) then we have at the same time proven a) as well. Can anyone give me a hint? I've tried drawing, but I'm not sure how to formally prove it. I was considering relationship properties, such as symmetry and transition, but couldn't work it out. Thanks in advance.

$\endgroup$

1 Answer 1

0
$\begingroup$

Construct a graph with $n$ vertices representing the people and connect two vertices if the two people they represent know each other. For a), the degree of each vertex if greater than $\frac{n}{2}$, By dirac's theorem, there is a Hamiltonian cycle. And this implies we can arrange the people in a circle so that each person knows the ones sitting next to them. Same for b). I think.

Or consider first a random arrangement of the people around the table, Suppose a neighboring pair $(A,B)$ is a hostile couple with $B$ sitting to the right of $A$, then if we can find a neighboring pair $(A'B')$ with $B'$ sitting to the right of $A'$ and $B'$ is friend with $B$ and $A'$ is a friend of $A$. we can then swap $B$ with $A'$ and that will reduce the number of hostile neighboring couples. So it remains to show $(A'B')$ exists. Well $A$ has at least $n$ friends sitting to his right, and there are $n$ sits to the right of frinds of $A$. $B$ has at most $n-1$ enemy, So there is a friend of $A$,$A'$, with $B'$ sitting right to him, a friend of $B$. Done?

$\endgroup$
2
  • $\begingroup$ Is it possible to explain this in any other way, because we never used Dirac's theorem nor Hamiltonian cycle in our course? $\endgroup$
    – ponikoli
    Dec 11, 2018 at 16:27
  • $\begingroup$ It is the "Ambassadors at a Round Table" problem!! $\endgroup$
    – user614287
    Dec 11, 2018 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .