21
$\begingroup$

The question that I saw is as follows:

In the Parliament of Sikinia, each member has at most three enemies. Prove that the house can be separated into two houses, so that each member has at most one enemy in his own house.

I built a graph where each person corresponds to a vertex and there is an edge between them if the two are enemies. Then I tried to color the vertices of the graph using two colors and remove edges that were between vertices of different colors. The goal is to arrive at a graph with max degree 1. I tried a couple of examples. It seems to workout fine, but I don't know how to prove it.

$\endgroup$
  • $\begingroup$ I think this problem is from Engel's book on problem solving, can the OP please confirm? $\endgroup$ – shardulc Dec 17 '16 at 23:33
  • $\begingroup$ I just checked it - it's actually in chapter 1, example 4, AND it comes with a solution (which is nearly identical to mine). So OP probably didn't get it from the book. $\endgroup$ – cats Dec 18 '16 at 1:11
18
$\begingroup$

Split the house however you like. Let $E_i$ be the number of enemies person $i$ has in their group, and let $E = \sum E_i.$ For any person having more than $1$ enemy in their group, i.e. at least $2$, move them to the other group, where they will have at most $1$ enemy. This decreases $E.$ Since $E$ is always non-negative, this process must end eventually, at which point the desired configuration is reached.

$\endgroup$
  • $\begingroup$ just be careful to note that moving a person might add an enemy for someone else but the net result is always a loss $\endgroup$ – cats Dec 17 '16 at 19:48
  • 14
    $\begingroup$ A clever solution. Just to clarify, I assume this depends on the "is an enemy of" relation being symmetric and irreflexive (i.e. if I'm your enemy, then you are mine, and I cannot be my own enemy), right? It seems to me that those assumption are needed to show that $E$ must always decrease. $\endgroup$ – Ilmari Karonen Dec 17 '16 at 20:17
  • 1
    $\begingroup$ @IlmariKaronen Without that assumption, can this be solved? $\endgroup$ – Yakk Dec 18 '16 at 0:36
  • $\begingroup$ Good point. Otherwise it's possible $E$ increases, even. $\endgroup$ – cats Dec 18 '16 at 0:49
  • 2
    $\begingroup$ @Yakk: Good question. The irreflexivity is definitely necessary: without it, there's a simple counterexample with three people, all of whom are enemies with everyone including themselves. I haven't managed to come up with a counterexample involving asymmetric (but still irreflexive) enmities yet; it's possible that the symmetry assumption isn't actually needed for the problem to be solvable, or I might just be missing something obvious. $\endgroup$ – Ilmari Karonen Dec 18 '16 at 1:57
10
$\begingroup$

The question is ambiguous in two ways: we are not told whether being an enemy is a symmetric or asymmetric relation, nor whether the parliament has a finite or infinite number of members. I will show that the assertion is false for asymmetric relations, even in the finite case; in fact, I give an (asymmetric) example of $15$ people, each having only $2$ enemies, who can't be divided into two groups in which each member has at most one enemy. On the other hand, if the relation is symmetric, the assertion is true even in the infinite case.

An asymmetric counterexample. There are $15$ people, call them $x_i,y_i,y'_i,z_i,z'_i\ (i=0,1,2).$ The enemies of $x_i$ are $y_i,y'_i;$ the enemies of $y_i,y'_i$ are $z_i,z'_i;$ the enemies of $z_i,z'_i$ are $x_i,x_{i+1}$ (addition modulo $3$). Let each of the $15$ people be colored red or blue. Then at least two among $x_0,x_1,x_2$ have the same color; without loss of generality, suppose that $x_0,x_1$ are red. If either $z_0$ or $z'_0$ is red, then we have a red person with two red enemies; so we may assume that $z_0,z'_0$ are blue. If either $y_0$ or $y'_0$ is blue, then we have a blue person with two blue enemies; so we may assume that $y_0,y'_0$ are red. But then $x_0$ is a red person with two red enemies.

The finite symmetric case. (Already proved in the answer by @cats, repeated here for convenience.) If $G=(V,E)$ is a finite undirected graph with maximum degree at most $3,$ then the vertex set $V$ can be partitioned into two sets $V_1,V_2$ so that, for $i=1,2,$ each vertex in $V_i$ has at most one neighbor (i.e. "enemy") in $V_i.$ This can be done by choosing a partition which maximizes the number of edges with one endpoint in $_1$ and the other in $V_2.$ (This argument does not work if $V$ is infinite.)

The infinite symmetric case. If $G=(V,E)$ is any (not necessarily finite) undirected graph with maximum degree at most $3,$ then the vertex set $V$ can be partitioned into two sets $V_1,V_2$ so that, for $i=1,2,$ each vertex in $V_i$ has at most one neighbor in $V_i.$ This follows from the finite case by the usual sort of compactness argument, i.e., using the fact that the Tychonoff product of any family of finite spaces is compact.

$\endgroup$
8
$\begingroup$

I will give a counter-example for the case where the enemy relationship is not assumed to be symmetric (but is assumed to be irreflexive). Imagine four kingdoms called North, South, East, and West. Each kingdom has many citizens and a king and a pretender to the throne (actually, the pretender to the throne might be the only citizen, awkward). The enemies of each citizen are the three foreign kings. The enemies of each king are the two next counterclockwise kings (North's enemy is West and South) as well as his pretender to the throne (each king has an enemy within his own kingdom).

Now let's first consider how to divide the kings. Clearly they can't go all in the same group. Also, if it is a 3-1 split, then two of the three may be happy because they hate the singleton, but the third of the three will hate the other two in the three, so a 3-1 split will not work. Now let's consider a 2-2 split, where the kingdoms pair off into two alliances. This may work for the kings, but we will need to make one observation: for either alliance, one of the king hates the other king (and possibly they both hate each other). For example, North is either paired with West or South, who North hates, or with East who hates North.

Now lets consider the placement of everyone else. Everyone besides the kings (including the pretenders) hate the three other kings. So each citizen has to be in his own kings alliance (because there are two enemy kings in the other alliance).

But now finally we get to a contradiction. In each alliance, there is a king who is allied with a king he hates. But then this king also hates the pretender in his own kingdom. Thus he has two people he hates.

User cardboard_box found a simplification. In addition to the other citizens besides the pretenders being unnecessary, it can actually be the case that all the pretenders are one and the same, and they don't need to hate anybody. But since he is taking the role of all the pretenders, all the kings hate him. But now which alliance can he go in? As before, both alliances have a king who hates the other king in the alliance, and all kings hate the pretender, so he cannot go in either alliance, a contradiction. Thus only five people are necessary to provide a counterexample.

$\endgroup$
  • 1
    $\begingroup$ Great illustration of the asymmetric case $\endgroup$ – Joffan Dec 18 '16 at 6:52
  • 1
    $\begingroup$ I ran a brute-force search for the smallest counterexample in the irreflexive but not symmetric case. The result is similar to your graph - it has 5 people - 4 kings, with each king hating the next two kings in clockwise order, and one villain whom all the kings hate (who doesn't hate anyone). If one group has 3 kings, one king will hate the other two, so the groups must each have 2 kings. Each group will have at least one king who hates the other king (since each pair of kings has one hating the other). This leaves nowhere to put the villain. $\endgroup$ – cardboard_box Dec 20 '16 at 23:39
  • $\begingroup$ @cardboard_box Thanks, I will incorporate this into my answer. $\endgroup$ – Brian Moths Dec 20 '16 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.