wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 3 Enemies
        
(Message started by: snags697 on Aug 12^th, 2002, 7:22am)

Title: 3 Enemies
Post by snags697 on Aug 12^th, 2002, 7:22am

The problem from the Hard riddles:

There are two houses of parliament in the land of Orange Milano. Each member of parliament has at most 3 enemies. PROVE that all the members can be placed in a house such that each member will have at most one enemy in the same house.

I started thinking about different configurations of enemies, and it got confusing quickly. Then I realized that there's an easy way to prove it. Consider adding the MPs to one house or the other, one by one.

If you want to continue thinking about this on your own, stop reading now. Otherwise, highlight the rest...

As you add the MPs, each one will have zero, one, two, or three enemies already placed in parliament. There has to be one house or the other with only one or zero enemies already it, so you can place the MP there. Repeat for every MP and you're done.

Update: This doesn't work, see discussion below.

Title: Re: 3 Enemies
Post by AlexH on Aug 12^th, 2002, 10:45am

You've failed to consider the people already in parliament in your method. For example consider people a,b,c,d,e where a,b are both enemies with each of c,d,e and there are no other enemies. You could add a->1 b->2 in your algorithm, then you'd get stuck when you go to add e.

Title: Re: 3 Enemies
Post by snags697 on Aug 12^th, 2002, 11:03am

Either you're saying E has 4 enemies, or you're worrying about C and D when you only need to consider A and B when placing E.

Title: Re: 3 Enemies
Post by AlexH on Aug 12^th, 2002, 11:20am

No. Once you've put a in g1 and b in g2, which your algorithm allows, you're doomed.
{a},{b} add c to get
{a,c},{b} add d to get
{a,c},{b,d} add e to get ????

You have to split c and d, but then when e comes a and b both already have 1 enemy in their house.

Title: Re: 3 Enemies
Post by tim on Aug 12^th, 2002, 11:22pm

Hint:

What would happen if each MP had only 2 enemies?

Solution:

1) Remove one enemy from each MP who has 3 enemies, so that no MP has more than 2.

2) It is then obviously possible to split them into houses so that each MP has no enemies in the same house by using an odd/even split among "chains" of enemies. To put it another way: the enemy of their enemy is, if not their friend, at least tolerable :)

3) Add back the enemies you removed in step 1.

Title: Re: 3 Enemies
Post by AlexH on Aug 13^th, 2002, 12:59am

You have a problem in step 1 Tim. If you aren't careful with the edges you remove from the degree 3 verticies you can wind up removing multiple edges from some verticies, thereby getting multiple enemies in the same house in step 3.

Title: Re: 3 Enemies
Post by tim on Aug 13^th, 2002, 1:21am

I thought it was obvious how you would avoid considering the same MP twice in the first step.

However, there is a worse problem in step 2: I didn't consider cycles in the 2-enemy case :(

Title: Re: 3 Enemies
Post by tim on Aug 13^th, 2002, 1:41am

More brute-force solution:
Start with any arrangement of MPs between houses.
For any member X who has two enemies within their house, move X to the other house.
This decreases the number of emnities in the original house by two, and increases the number of emnities in the new house by at most one. Since the total number of emnities was initially finite, this procedure must terminate.

Title: Re: 3 Enemies
Post by AlexH on Aug 13^th, 2002, 2:26am

What is the obvious way to fix step 1 from the original method? I may be missing something but to me it looks less obvious than solving the whole problem in the first place. The "more brute force solution" of enmity-counting is more elegant IMO (plus its correct).

Title: Re: 3 Enemies
Post by snags697 on Aug 13^th, 2002, 6:48am

on 08/12/02 at 11:20:05, AlexH wrote:

This assumes that a,c,b, and d are all enemies of e. But e can only have 3 enemies. So one of the first four is not an enemy, and e can go in that house.

Update: Whoops, I see where the snag comes in. For some reason, I thought I had elimated the possibility of additional conflicts with already placed MPs. tim's brute-force solution works, though I'd love to see one where you initally correctly place the members as you go.

Title: Re: 3 Enemies
Post by S. Owen on Aug 13^th, 2002, 9:03am

... but then either a or b must have 2 enemies (c and e, or d and e respectively) in the same house.

What you're not considering in placing people are potential conflicts created by future placements.

Title: Re: 3 Enemies
Post by James Fingas on Aug 29^th, 2002, 6:05am

The mistake that was made was that we placed A and B in the houses first. What if we prioritized by placing people with the most enemies already in-house?

Update: Sorry, I don't think that works. You could still be unlucky.

Title: Re: 3 Enemies
Post by titan on Oct 16^th, 2013, 1:18am

Consider any arrangement o MPs in two houses.
If any member M has 1 enemy in the house A, don't touch.
If any member has 2 enemies in house A, move it to house B bcoz max. no. of enemies possible are 3. So, it will have atmost 1 enemy in house B.
If any member has 3 enemies in A, move it to B.

Now shud this process terminate at all? Isn't it kinda very vague solution?

Title: Re: 3 Enemies
Post by rmsgrey on Oct 16^th, 2013, 5:50am

on 10/16/13 at 01:18:09, titan wrote:

As discussed earlier in the thread, when M moves from A to B, the number of enmities in A drops by at least 2, while the number in B increases by at most 1, so the total number of enmities across both houses reduces by at least 1. Since the total number of enmities across both houses cannot be greater than the 3/2 times the number of MPs, and cannot be less than 0, it must become impossible to decrease the enmities in this way after a finite number of steps.

Since the decrease only requires at least one MP to share a house with at least two of their enemies, for it to be impossible, there must be no MPs which share a house with at least two of their enemies, or, equivalently, each MP must share a house with at most one of their enemies.

Title: Re: 3 Enemies
Post by titan on Oct 16^th, 2013, 6:16am

Quote:

Since the total number of enmities across both houses cannot be greater than the 3/2 times the number of MPs,

Why is it 3/2 times total MPs?
Each MP has atmost 3 enemies, so, shudn't the total no. of enemies be 3x(total MPs)?

But, each case is counted twice here. B'coz when A n B r enemies, we r saying A is an enemy to B n B is an enemy to A. Hence, dividing by 2.

Title: Re: 3 Enemies
Post by Grimbal on Oct 16^th, 2013, 9:12am

I am not sure it was stated, but you have to assume being an enemy is a ~~reflexive~~ symmetric property.

You have to count the number of couples that are enemies.

If you count the enmity from both sides, you multiply everything by 2. By moving out a MP with 2 enemies you reduce the count by 4, 2 for the outgoing MP, 2 for the 2 enemies who see an enemi leave. On the other side, you might increase it by 2.

Title: Re: 3 Enemies
Post by rmsgrey on Oct 17^th, 2013, 9:03am

If enmity is not a symmetric relation - that is, if A can be B's enemy without B automatically being A's enemy, then it may not be possible to avoid having someone with two enemies in the same house as them.

In fact, there are arrangements where it's impossible:

If you have 6 MPs, 5 of whom have a common enemy, F, while among the 10 pairs of A, B, C, D, E one in each pair is the other's enemy (for example, B and C are A's enemies, C and D are B's, and so on). You can't have all of A, B, C, D and E in the same house, nor any four of them - six pairs, each of which has one enmity means that there are still six instances of someone having an enemy with them. Six enemies among four people means at least one must have at least two enemies present.

With a 3-2 split before F is added, both houses must have at least one person with at least one of their enemies already present, so whichever house F is added to, that person will then have 2 of their enemies present.

Title: Re: 3 Enemies
Post by Grimbal on Oct 18^th, 2013, 7:10am

I mixed up reflexive and symmetric. Reflexive would mean that each MP is his own enemy. ;D.

This made me think: if people can be their own enemy, then there is a simple configuration that cannot be split. 3 MPs are their own enemy and each other's.

So enmity should be assumed symmetric and anti-reflexive.

Title: Re: 3 Enemies
Post by ashmish2 on Oct 22^nd, 2013, 11:16am

if enmity is symmetric, then its not possible to divide in come cases.
e.g --> suggest thier enemy
A --> B, C, D
B --> A, D, E
C --> A, E, D
D --> A, C, B
E --> B, C
this is group with atmost 3 enemy

How will you divide the parliament? :-/

Title: Re: 3 Enemies
Post by towr on Oct 22^nd, 2013, 10:52pm

on 10/22/13 at 11:16:14, ashmish2 wrote:

How will you divide the parliament? :-/

By following the algorithm outlined above, which results in ADE and BC; only AD are enemies in the same house, but it's one, so that's allowed.