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



fom
Posts:
1,968
Registered:
12/4/12


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


On 2/2/2013 3:39 AM, mina_world wrote: >> 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. >
Indeed.
I had not seen that you resolved it on your own.
> >> 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. >
No. It is correct.
It fixes A.
It identifies the possible endpoints for arcs that can have their order inverted in terms of A's friends.
It does the correct combinatorics to assert the existence of at least one arc that reduces H
> >> 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. >



