1

Problem: $2n$ ambassadors are invited to a banquet. Every ambassador has at most $n−1$ enemies. Prove that the ambassadors can be seated around a round table, so that nobody sits next to an enemy.

Solution: First, we seat the ambassadors in any way. Let $H$ be the number of neighboring hostile couples. We must find an algorithm which reduces this number whenever $H > 0$. Let $(A, B)$ be a hostile couple with B sitting to the right of $A$. We must separate them so as to cause as little disturbance as possible. This will be achieved if we reverse some arc $BA'$ . H will be reduced if $(A, A' )$ and $(B,B' )$ are friendly couples. it remains...

My question: Suppose B has in its right a friend $B''$ which is an enemy of $A'$ then after switching $A'$ and $B$, the number $H$ won't decrease or if the same situation happens for $A'$ (has a friend in its left which is an enemy of B) it will even increase!
How should I fix this?

I'm assuming being enemy is not a transitive relation. Is it right ? or there are some unmentioned properties for this relation ?

arnav_de
  • 699
Davood Karimi
  • 487
  • Possible duplicate of $2n$ ambassadors problem – PinkyWay May 09 '22 at 06:36
  • Do you mean we switch from $...ABB''...A'B'...$ to $...AA'...B''BB'...$? (The range $BB''...A'$ gets reversed.) Per assumption $(A,B)$ are enemies; $(A,A')$ are friends, $(B,B')$ are friends, $(B,B'')$ are friends, $(B'',A')$ are enemies? Then we have one hostile pair $(A,B)$ and possibly another $(A',B')$ converted into two friendly pairs $(A,A'), (B, B')$ without introducing any further hostilities. I am not sure what is confusing you. –  May 09 '22 at 06:38
  • @ Invisible I don't think so – Davood Karimi May 09 '22 at 06:38
  • @ Striking Bishop we switch from $...ABB''...A'B'...$ to $...AA'B''...BB'$ and it's not clear that $(B'',A')$ are friends or enemies – Davood Karimi May 09 '22 at 06:46
  • 1
    @DavoodKarimi I believe the "switch" is meant to be what I had in my comment above, i.e. you don't just switch the ends of the arc, you flip the whole arc. –  May 09 '22 at 08:21
  • @ Striking Bishop oh, thank you. it resolves my problem. – Davood Karimi May 09 '22 at 09:33

1 Answers1

1

It depends on how the list of $ n-1 $ enemies is defined. Let's say, for instance, that every ambassador has the same list of enemies except for those $ n-1 $, whose list is the same but for one element, namely, themselves. Then in that case, it is not possible to sit them around the table and refute the affidavit.

However, in a more equitable distribution of enemies we can refute it as true statement, because every ambassador sits next to two different ambassador and the list of enemies is splitted by less than a half. But again, there must be some limit on how the list should be defined.

Conclusion. This problem is vaguely defined.

SNR
  • 235