Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Discrete math with IMO.
Replies: 5   Last Post: Feb 2, 2013 4:51 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
fom

Posts: 1,968
Registered: 12/4/12
Re: Discrete math with IMO.
Posted: Feb 2, 2013 4:51 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

>




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.