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,033
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 (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.
>
> 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) = n-2
>
> And there is at least n friends of A.
> B_1, B_2, ... , B_(n-1), B_n
> Since remainder chairs (n-2) < 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 (n-1)
>> enemies.
>>
>> Thus, there is a friend A' of A with right neighbor B', a friend of B.
>
|
|
|
|
