wu :: forums « wu :: forums - 3 Enemies » Welcome, Guest. Please Login or Register. Sep 18th, 2018, 9:11am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, towr, Eigenray, SMQ, Grimbal, william wu, Icarus)    3 Enemies « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: 3 Enemies  (Read 5315 times)
snags697
Newbie

Gender:
Posts: 14
 3 Enemies   « on: Aug 12th, 2002, 7:22am » Quote Modify

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.

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.

 « Last Edit: Aug 13th, 2002, 10:49am by snags697 » IP Logged
AlexH
Full Member

Posts: 156
 Re: 3 Enemies   « Reply #1 on: Aug 12th, 2002, 10:45am » Quote Modify

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.
 « Last Edit: Aug 12th, 2002, 10:45am by AlexH » IP Logged
snags697
Newbie

Gender:
Posts: 14
 Re: 3 Enemies   « Reply #2 on: Aug 12th, 2002, 11:03am » Quote Modify

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.
 IP Logged
AlexH
Full Member

Posts: 156
 Re: 3 Enemies   « Reply #3 on: Aug 12th, 2002, 11:20am » Quote Modify

No. Once you've put a in g1 and b in g2, which your algorithm allows, you're doomed.
{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.
 IP Logged
tim
Junior Member

Posts: 81
 Re: 3 Enemies   « Reply #4 on: Aug 12th, 2002, 11:22pm » Quote Modify

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.

 IP Logged
AlexH
Full Member

Posts: 156
 Re: 3 Enemies   « Reply #5 on: Aug 13th, 2002, 12:59am » Quote Modify

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.
 IP Logged
tim
Junior Member

Posts: 81
 Re: 3 Enemies   « Reply #6 on: Aug 13th, 2002, 1:21am » Quote Modify

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
 IP Logged
tim
Junior Member

Posts: 81
 Re: 3 Enemies   « Reply #7 on: Aug 13th, 2002, 1:41am » Quote Modify

More brute-force solution:
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.

 IP Logged
AlexH
Full Member

Posts: 156
 Re: 3 Enemies   « Reply #8 on: Aug 13th, 2002, 2:26am » Quote Modify

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).
 IP Logged
snags697
Newbie

Gender:
Posts: 14
 Re: 3 Enemies   « Reply #9 on: Aug 13th, 2002, 6:48am » Quote Modify

on Aug 12th, 2002, 11:20am, AlexH wrote:
 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.

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.
 « Last Edit: Aug 13th, 2002, 10:49am by snags697 » IP Logged
S. Owen
Full Member

Gender:
Posts: 221
 Re: 3 Enemies   « Reply #10 on: Aug 13th, 2002, 9:03am » Quote Modify

... 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.
 « Last Edit: Aug 13th, 2002, 9:06am by S. Owen » IP Logged
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: 3 Enemies   « Reply #11 on: Aug 29th, 2002, 6:05am » Quote Modify

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.
 « Last Edit: Aug 29th, 2002, 6:37am by James Fingas » IP Logged

titan
Newbie

Posts: 33
 Re: 3 Enemies   « Reply #12 on: Oct 16th, 2013, 1:18am » Quote Modify

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?
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: 3 Enemies   « Reply #13 on: Oct 16th, 2013, 5:50am » Quote Modify

on Oct 16th, 2013, 1:18am, titan wrote:
 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?

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.
 IP Logged
titan
Newbie

Posts: 33
 Re: 3 Enemies   « Reply #14 on: Oct 16th, 2013, 6:16am » Quote Modify

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.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7408
 Re: 3 Enemies   « Reply #15 on: Oct 16th, 2013, 9:12am » Quote Modify

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.
 « Last Edit: Oct 18th, 2013, 6:53am by Grimbal » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: 3 Enemies   « Reply #16 on: Oct 17th, 2013, 9:03am » Quote Modify

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.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7408
 Re: 3 Enemies   « Reply #17 on: Oct 18th, 2013, 7:10am » Quote Modify

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

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.
 « Last Edit: Oct 18th, 2013, 7:11am by Grimbal » IP Logged
ashmish2
Newbie

Posts: 12
 Re: 3 Enemies   « Reply #18 on: Oct 22nd, 2013, 11:16am » Quote Modify

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?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13638
 Re: 3 Enemies   « Reply #19 on: Oct 22nd, 2013, 10:52pm » Quote Modify

on Oct 22nd, 2013, 11:16am, 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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »