```Date: Feb 2, 2013 4:39 AM
Author: mina_world
Subject: Re: Discrete math with IMO.

> 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 ? sitting to the right of A(Fig. > 1.3).>> We must separate them so as to cause as little disturbance as possible.>> This will be achieved if we reverse some arc ? A' getting Fig. 1.4.>> H will be reduced(***) if (A, A') and (?, ?') in Fig. 1.4 are friendly> couples.I know that..It's really reduced.Because, reverse some arc ? A'.In fact, I thought only B and A' (reverse).Arc is a important key in this problem.> It remains to be shown that>> such a couple always exists with B' sitting to the right of A'. (***)Yes, it's true.Because,there is 2n chairs around the table.Fix A and B. (A, B) as given problem.There is at least n friends of A.We start in A and go around the table counterclockwise.A, B,  A_1, A_2, ... , A_n (counterclockwise)so, n+2remainder chairs (2n)-(n+2) = n-2And there is at least n friends of A.B_1, B_2, ... , B_(n-1), B_nSince remainder chairs (n-2) < Friends of B (n),there is at least two as A_i = B_j , A_k = B_mIt means that always exists with B' sitting to the right of A'Hm, no problem ?I think that lower explanation is wrong.> We start in A and go around the table counterclockwise.>> We will encounter at least n friends of A.>> To their right, there are at least n seats.>> They cannot all be occupied by enemies of ? since ? has at most (n-1)> enemies.>> Thus, there is a friend A' of A with right neighbor B', a friend of B.
```