Prisoners and their enemies

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Prisoners and their enemies

Postby wraith » Sat Sep 06, 2014 9:02 pm UTC

Each prisoner in a prison has up to three enemies. If two enemies face each other, nothing serious will happen, because the odds of winning in a fight would be even, but if a prisoner faces two or three of his enemies, they'll team up, beat him, and quite possibly kill him.

The guards know about this and they also know the enemies of each prisoner. To avoid fights and riots they want to divide the prisoners in the prison's two blocks in such a way that no prisoner has more than one enemy in his block.

Is this always possible?

PS "Enmity" is always mutual - each prisoner is an enemy to his enemies
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Prisoners and their enemies

Postby ahammel » Sun Sep 07, 2014 12:55 am UTC

Spoiler:
It's impossible when there are five prisoners with three enemies each.
He/Him/His/Alex
God damn these electric sex pants!

User avatar
somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

Re: Prisoners and their enemies

Postby somehow » Sun Sep 07, 2014 1:50 am UTC

ahammel wrote:
Spoiler:
It's impossible when there are five prisoners with three enemies each.


Spoiler:
It's impossible for there to be five prisoners with three enemies each. Since enmity is mutual, we can think of this as a graph in which each node represents a prisoner and an edge between two nodes means that the prisoners corresponding to the two nodes are enemies. Then the sum over all the prisoners of the number of enemies of each prisoner is equal to twice the number of edges, and therefore must be even. In your scenario, that sum is 15.
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Prisoners and their enemies

Postby jestingrabbit » Sun Sep 07, 2014 10:51 pm UTC

wraith wrote:Each prisoner in a prison has up to three enemies. If two enemies face each other, nothing serious will happen, because the odds of winning in a fight would be even, but if a prisoner faces two or three of his enemies, they'll team up, beat him, and quite possibly kill him.

The guards know about this and they also know the enemies of each prisoner. To avoid fights and riots they want to divide the prisoners in the prison's two blocks in such a way that no prisoner has more than one enemy in his block.

Is this always possible?

PS "Enmity" is always mutual - each prisoner is an enemy to his enemies


Put another way, in a undirected graph where no vertex has a degree greater than 3, is the graph "almost" bipartite.
Spoiler:
There are some cases that are pretty easy to clear up.

Connected components can be dealt with separately, trees are doable ie no loops => solvable. If the graph can be separated into two parts that are connected by only a single edge, then solving the two parts solves the whole.

Also, if you just max out the enmity you end up with a tetrahedron, which can clearly be separated.


Suspect that the answer is "yes you can" but no proof just yet.

eta

Spoiler:
you can do it for the dodecahedron and cube too. looking pretty good.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Sun Sep 07, 2014 11:05 pm UTC

What do you mean by this?

jestingrabbit wrote:
Spoiler:
Also, if you just max out the enmity you end up with a tetrahedron.


Spoiler:
If by "maxed out enmity" you mean that every prisoner has three enemies, then that's not true. Every even number of prisoners greater than or equal to four can have maxed out enmity. Not just tetrahedrons
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Prisoners and their enemies

Postby jestingrabbit » Mon Sep 08, 2014 1:13 am UTC

wraith wrote:What do you mean by this?

jestingrabbit wrote:
Spoiler:
Also, if you just max out the enmity you end up with a tetrahedron.


Spoiler:
If by "maxed out enmity" you mean that every prisoner has three enemies, then that's not true. Every even number of prisoners greater than or equal to four can have maxed out enmity. Not just tetrahedrons


Yeah, there are a lot of configurations with each vertex having maximum order. I thought that the tetrahedron was a good example to mention/ruleout.

I'm thinking about ruling out some other sub configurations. For instance, a solution for the second graph in the diagram can be extended to the first in an obvious way.

reduction.png


A more complicated reduction also works for graphs that have a loop of size 3.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Prisoners and their enemies

Postby Cauchy » Mon Sep 08, 2014 2:50 am UTC

The Petersen graph is not a counterexample, so the result is very likely true. (Curiously, the block assignment for the Petersen graph does not have equal numbers in each block.) However, in general you can't just pick any pair of enemy prisoners, throw them into the same block, and expand from there: there's a counterexample of size six to that idea.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: Prisoners and their enemies

Postby notzeb » Mon Sep 08, 2014 8:08 am UTC

Any maximal cut solves the problem...
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Mon Sep 08, 2014 9:14 am UTC

notzeb wrote:Any maximal cut solves the problem...


Well what about the Petersen graph, then? :)

Here is a max cut on a Petersen graph. Notice the prisoner with two enemies in his block.
Attachments
maxcuptpetersen.png
maxcuptpetersen.png (11.37 KiB) Viewed 7010 times
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Mon Sep 08, 2014 9:21 am UTC

Actually, never mind. This wasn't a maximum cut.

It really seems that a maximum cut does solve it, but I'm still not sure that ANY maximum cut does.
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Mon Sep 08, 2014 10:02 am UTC

Actually I agree with it completely now. Any maximum cut solves it.

Funny. I hadn't thought of that :)

My solution doesn't use graphs at all.
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Prisoners and their enemies

Postby Cauchy » Mon Sep 08, 2014 10:10 am UTC

wraith wrote:Actually, never mind. This wasn't a maximum cut.

It really seems that a maximum cut does solve it, but I'm still not sure that ANY maximum cut does.


Take a maximum cut, and assume for sake of contradiction that it fails the condition given in the problem. Then, there exists some vertex such that at most one of its incident edges crosses the cut. Flip which side of the partition it's on, and now at least two of its incident edges cross the cut, without changing the crossing status of any other edge. So our cut wasn't actually a maximum cut, contradiction.

I'm not terribly versed in graph theory, so things like "maximum cuts" don't spring to my mind immediately, but in retrospect it's an obvious solution. We want to partition the vertices, and we want a lot of edges to cross the partition, so an obvious first guess is the partition that makes the most edges cross.

With a little more work, this also turns into a proof that every such graph is four-colorable, and a similar argument yields that a graph with max degree at most 5 is six-colorable, and a graph with max degree at most 7 is eight-colorable (and similarly for several other numbers as well). Is the statement "a graph with max degree at most n is (n+1)-colorable" true in general, and is an argument similar to this a proof for it?
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Prisoners and their enemies

Postby Lopsidation » Mon Sep 08, 2014 3:10 pm UTC

Yes, that is true, Cauchy.

Spoiler:
Go ahead and color the vertices one by one. How could you possibly get stuck?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Prisoners and their enemies

Postby jestingrabbit » Mon Sep 08, 2014 9:50 pm UTC

wraith wrote:Actually I agree with it completely now. Any maximum cut solves it.

Funny. I hadn't thought of that :)

My solution doesn't use graphs at all.


What does your solution look like?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Prisoners and their enemies

Postby Cauchy » Tue Sep 09, 2014 11:22 am UTC

Lopsidation wrote:Yes, that is true, Cauchy.

Spoiler:
Go ahead and color the vertices one by one. How could you possibly get stuck?


Wow, I am *really* rusty, because that's incredibly straightforward.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Tue Sep 09, 2014 11:44 am UTC

jestingrabbit wrote:
wraith wrote:Actually I agree with it completely now. Any maximum cut solves it.

Funny. I hadn't thought of that :)

My solution doesn't use graphs at all.


What does your solution look like?


Spoiler:
Put all prisoners in the two blocks at some random configuration. Take one prisoner with 2 or more enemies in his block and put him in the other block. Do this until there are no more prisoners with two or more enemies in their block.

This works because if you imagine all enmities, after this step two or three are removed from one block and zero or one are added to the other, ultimately reducing their total number until it's no longer possible.

If you have a prisoner with two or more enemies in his block, the number of enmities WILL be reducible, which proves that this is a solution to the problem.
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Prisoners and their enemies

Postby jestingrabbit » Wed Sep 10, 2014 5:06 am UTC

wraith wrote:
jestingrabbit wrote:
wraith wrote:Actually I agree with it completely now. Any maximum cut solves it.

Funny. I hadn't thought of that :)

My solution doesn't use graphs at all.


What does your solution look like?


Spoiler:
Put all prisoners in the two blocks at some random configuration. Take one prisoner with 2 or more enemies in his block and put him in the other block. Do this until there are no more prisoners with two or more enemies in their block.

This works because if you imagine all enmities, after this step two or three are removed from one block and zero or one are added to the other, ultimately reducing their total number until it's no longer possible.

If you have a prisoner with two or more enemies in his block, the number of enmities WILL be reducible, which proves that this is a solution to the problem.


Your method has the benefit of being complete after #prisoners time (I think), whereas finding a max cut is probably not doable in poly time (it is doable iff P=NP).
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Wed Sep 10, 2014 7:56 am UTC

jestingrabbit wrote:Your method has the benefit of being complete after #prisoners time (I think), whereas finding a max cut is probably not doable in poly time (it is doable iff P=NP).


Well, for max enmity (every prisoner has three enemies), my method produces a max cut, since only a max cut is a solution in this case (it's not necessarily so if some prisoners have less than three enemies, though).

Is this suddenly a polynomial algorithm for finding max cuts for graphs, where all vertices have a degree of 3?
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Prisoners and their enemies

Postby Nitrodon » Wed Sep 10, 2014 4:22 pm UTC

This is not the case. If the enmity graph is a cube, there are two cuts (up to isomorphism) that satisfy the condition, but only one max cut.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Prisoners and their enemies

Postby Cauchy » Wed Sep 10, 2014 8:13 pm UTC

The algorithm doesn't necessarily produce a maximum cut. Instead, it produces a sort of maximal cut, maximal in the sense that it cuts more edges than the cuts produced by flipping any one vertex to the other side. It's a local max, but not necessarily a global max.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Prisoners and their enemies

Postby jestingrabbit » Thu Sep 11, 2014 3:18 am UTC

That said, there might be a polynomial time algorithm for graphs where every vertex has degree less than 3 that finds the max cut, but this isn't it.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
wraith
Posts: 101
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

Re: Prisoners and their enemies

Postby wraith » Thu Sep 11, 2014 11:46 am UTC

Cauchy wrote:The algorithm doesn't necessarily produce a maximum cut. Instead, it produces a sort of maximal cut, maximal in the sense that it cuts more edges than the cuts produced by flipping any one vertex to the other side. It's a local max, but not necessarily a global max.


Indeed. My mistake :)
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames


Return to “Logic Puzzles”

Who is online

Users browsing this forum: Google Feedfetcher and 15 guests