Author |
Topic: 3 Enemies (Read 6026 times) |
|
snags697
Newbie
Mad Physicist
Gender: 
Posts: 14
|
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
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
Mad Physicist
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},{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.
|
|
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:
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
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
Mad Physicist
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 |
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 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: 2872
|
|
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: 7526
|
|
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: 2872
|
|
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: 7526
|
|
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: 13730
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print