Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Discrete math with IMO.
Posted:
Feb 2, 2013 3:23 AM


On Sat, 2 Feb 2013, mina_world wrote:
> Hello~ teacher... > > 2n ambassadors are invited to a banquet. > Every ambassador has at most (n1) enemies.
> Prove that the ambassadors can be seated around a round table, > so that nobody sits next to an enemy.
Let n = 2 and a,b,c all have the enemy d while d has no enemies.
For example, Alice, Betty, Carol and Diane all are after John. D dates J and now A,B,C have the enemy D while D, out with J, has no enemy; she has J.
Who will sit next to d?
> 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. > > It remains to be shown that > such a couple always exists with B' sitting to the right of A'. (***) > > 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 (n1) > enemies. > Thus, there is a friend A' of A with right neighbor B', a friend of B. > >  > Hm... can you understand this solution ? > > I need your explanation. specially (***) part. > > For reference(text copy) > http://board2.blueweb.co.kr/user/math565/data/math/olimo.jpg > >



