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,031
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 (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.
>
> 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 (n-1)
> 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) - (n-1)(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 (n-1 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.
|
|
|
|
