wu :: forums
« wu :: forums - 3 Enemies »

Welcome, Guest. Please Login or Register.
Sep 18th, 2018, 9:11am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, towr, Eigenray, SMQ, Grimbal, william wu, Icarus)
   3 Enemies
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 3 Enemies  (Read 5315 times)
snags697
Newbie
*




Mad Physicist

   


Gender: male
Posts: 14
3 Enemies  
« on: Aug 12th, 2002, 7:22am »
Quote Quote Modify 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.
 
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.
 
« Last Edit: Aug 13th, 2002, 10:49am by snags697 » IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: 3 Enemies  
« Reply #1 on: Aug 12th, 2002, 10:45am »
Quote Quote Modify 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
*




Mad Physicist

   


Gender: male
Posts: 14
Re: 3 Enemies  
« Reply #2 on: Aug 12th, 2002, 11:03am »
Quote Quote Modify 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
***





   
Email

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

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 Huh?
 
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 Quote Modify 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 Smiley
 
3) Add back the enemies you removed in step 1.

IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: 3 Enemies  
« Reply #5 on: Aug 13th, 2002, 12:59am »
Quote Quote Modify 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 Quote Modify 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 Sad
IP Logged
tim
Junior Member
**





   


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

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.

IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: 3 Enemies  
« Reply #8 on: Aug 13th, 2002, 2:26am »
Quote Quote Modify 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
*




Mad Physicist

   


Gender: male
Posts: 14
Re: 3 Enemies  
« Reply #9 on: Aug 13th, 2002, 6:48am »
Quote Quote Modify 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 Huh?
 
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: male
Posts: 221
Re: 3 Enemies  
« Reply #10 on: Aug 13th, 2002, 9:03am »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: 3 Enemies  
« Reply #11 on: Aug 29th, 2002, 6:05am »
Quote Quote Modify 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

Doc, I'm addicted to advice! What should I do?
titan
Newbie
*





   


Posts: 33
Re: 3 Enemies  
« Reply #12 on: Oct 16th, 2013, 1:18am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: 3 Enemies  
« Reply #13 on: Oct 16th, 2013, 5:50am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 7408
Re: 3 Enemies  
« Reply #15 on: Oct 16th, 2013, 9:12am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: 3 Enemies  
« Reply #16 on: Oct 17th, 2013, 9:03am »
Quote Quote Modify 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: male
Posts: 7408
Re: 3 Enemies  
« Reply #17 on: Oct 18th, 2013, 7:10am »
Quote Quote Modify Modify

I mixed up reflexive and symmetric.  Reflexive would mean that each MP is his own enemy. Grin.
 
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 Quote Modify 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?   Undecided
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


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

on Oct 22nd, 2013, 11:16am, ashmish2 wrote:
How will you divide the parliament?   Undecided
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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board