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


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Discrete math with IMO.
Replies:
5
Last Post:
Feb 2, 2013 4:51 AM




Re: Discrete math with IMO.
Posted:
Feb 2, 2013 4:39 AM


> 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. > > > >  > > 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+2 remainder chairs (2n)(n+2) = n2
And there is at least n friends of A. B_1, B_2, ... , B_(n1), B_n Since remainder chairs (n2) < Friends of B (n), there is at least two as A_i = B_j , A_k = B_m It 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 (n1) > enemies. > > Thus, there is a friend A' of A with right neighbor B', a friend of B.



