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


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


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


On 2/1/2013 9:50 AM, 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. > >  > > 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.
So, H is a function of some cyclic ordering of the ambassadors.
H:S_2n > N
The admissible operation on the configuration is to reverse the order of seating for any single proper arc
The operation need not change the value of H. It can, in fact, increase that valuation.
The assertion claims that such an order reversal will never increase H so long as the pairs of ambassadors at the endpoints of the two complementary arcs after the operation are not enemies.
This is an added criterion on the admissibility of the operation. Now an application of the original operation is inadmissible if the endpoints of the complementary arcs are enemies.
Moreover, the new operation will reduce H if the initial configuration contains at least one pair of enemies at the endpoints of the complementary arcs.
So H now governs the application of an operation representable as a monotone decreasing function. The question becomes whether or not H can be made to vanish under repeated operations.
H can be reduced only so long as an admissible operation can be performed. So, for any given pair of enemies, it must shown that there exist another pair of ambassadors who delineate the second endpoint of an arc.
Since an admissible operation requires friendly ambassadors to be seated with one another, choose one of the enemies, say A, and look for the friends of this ambassador. By virtue of the combinatoric relationships, A has at least n friends (2n  1(self)  (n1)(max{enemies})).
Any admissible operation can only occur with respect to where A is seated and where one of A's friends are seated. Since A has more friends (n or more) than B has enemies (n1 or less), at least one of A's friends is seated to an ambassador who is not an enemy of B.
Thus, there is an admissible operation and H can be reduced.



