3

Question:
Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies, and there are either 3 mutual enemies or 4 mutual friends.

I'm really lost in this question. After hours of just thinking and having no progress, I looked at the answer key, and still lost. So I will give you the books answer key and point out where I'm lost.

Book's Solution:
By symmetry we need to prove only the first statement. Let $A$ be one of the people. Either $A$ has at least four friends, or $A$ has at least six enemies among the other nine people (since $3 + 5 < 9$). Suppose, in the first case, $B, C,D, E$ are all $A$'s friends. If any two of these are friends with each other, then we have found three mutual friends. Otherwise $\{B, C, D, E\}$ is a set of four mutual enemies of $A$. By Example 11, among $B, C, D, E, F, G$ there are either three mutual friends or three mutual enemies, who form with $A$, a set of four mutual enemies.

One can ignore the last sentence, it's basically saying that in 6 people, there are either 3 mutual friends or 3 mutual enemies, which I completely understand already.

My Problem:
The proof actually make sense, except for the part where they said "Either A has at least 4 friends, or A has at least six enemies among the other nine people (since 3 + 5 < 9)", that 's the part thats bothering me. Where did they get the number $4$? I mean, by pigeon hole principle, $A$ has at lest $\lceil \dfrac{9}{2}\rceil = 5$ enemies or friends (not both of course). If you could help me out, I would appreciate it. I'm almost halfway the Discrete Mathematics text book and this is so far the most bizarre, and I would like to build some neural path and make this problem easier.

JoeyAndres
  • 1,269
  • 1
    If $A$ has fewer than four friends, then there are at least six people left who are not friends of $A$. Then these are enemies of $A$, so $A$ then has at least six enemies. – Daniel Fischer Jul 19 '14 at 08:27
  • 2
    A cannot have less than 4 friends and less than 6 enemies simultaneously because A knows 9 people. If A has at most 3 friends and at most 5 enemies, A would know at most 8 people, but A knows 9. The 9th person must then fall into the friend category (and thus, A has at least 4 friends) or in the enemy category (and thus, A has at least 6 enemies) – Darth Geek Jul 19 '14 at 08:32
  • Why people have to be friend or enemies...such a bleak polar world... Also, did you meant to write AND instead of OR in the problem description? – Gina Jul 19 '14 at 08:33
  • @DanielFischer I do understand that statement, but why $4$? I could've said, Either A has at least $5$ friends or $A$ has at least $4$ enemies, which is equally valid since $5 + 4 \leq 9$, right?? – JoeyAndres Jul 19 '14 at 08:33

3 Answers3

5

$A$ has $9$ people who are each friends or enemies. Let's write this as $$F_A+E_A=9.$$

So if $F_A \le 3$ then this implies $E_A \ge 6$.

But since $F_A$ is an integer, $F_A \not \le 3$ implies $F_A \ge 4$.

So we can conclude from $$F_A \le 3 \text{ or } F_A \not \le 3$$ that $$E_A \ge 6 \text{ or } F_A \ge 4$$

Henry
  • 157,058
  • I missed the part $F_A$ is an integer, thus $F_A \nleq 3 \rightarrow F_A \geq 4$. Can you elaborate on that further? – JoeyAndres Jul 19 '14 at 08:38
  • @Joey Andres: The smallest integer not less than or equal to $3$ is $4$. There is no integer strictly greater than $3$ and strictly less than $4$. – Henry Jul 19 '14 at 08:40
  • I looked at the question again, and your answer too. There is still something bothering me, you said "So if $FA \leq 3 \dots$". How did you even start at that? I mean why not $FA \geq 5, FE \geq 4$, which satisfy the inequality too. – JoeyAndres Jul 19 '14 at 17:14
  • @Joey Andres. I chose $3$ because you did not understand "Either A has at least 4 friends, or A has at least six enemies among the other nine people" and $3$ is the integer below $4$. It is also true that "either A has at least $5$ friends or A has at least $5$ enemies among the other nine people" which is a little stronger that what you say, but that was not your original question. – Henry Jul 19 '14 at 17:24
  • I should've worded my question correctly. What I really wanted is the origins of the number. What do you mean when you said "a little stronger $\dots$"? Do you mean the the proof in the book is less valid when I used the statement "either A has at least 5 friends or A has at least 5 enemies among the other nine people" instead? Sorry for bothering you, 8 hours ago, this idea was complete alien to me. – JoeyAndres Jul 19 '14 at 17:29
  • The proof you quote says "Either A has at least 4 friends, or A has at least six enemies among the other nine people" so you need to see how to show that. The key point you may be missing is that the to either/or numbers add up to $10$ (hence my "stronger") – Henry Jul 19 '14 at 20:17
  • Can't all 10 just be friends or enemies of A? – Diecie Jul 13 '21 at 08:45
  • @Diecie If the other $9$ are all friends of A, then either there is pair who are friends of each other (making $3$ mutual friends including A) or they are all mutual enemies (and $9 \ge 4$). If the other $9$ are all enemies of A, then either $3$ are mutual friends, or $3$ are mutual enemies (making $4$ mutual enemies including A) – Henry Jul 13 '21 at 09:02
  • So I'm right? I meant 9, BTW. – Diecie Jul 14 '21 at 01:49
  • @Diecie - What do you think you are "right" about? – Henry Jul 14 '21 at 07:32
2

Let us assume A has 9 relations with B,C,D,E,F,G,H,I,J (i.e rest of 9 people). They can be either friends or enemies. By pigeon hole principle, A has atleast ⌈9/2⌉=5 enemies or friends (not both of course).

Let us now consider A is friends with 5 people i.e with B,C,D,E,F. Now we know here any 2 are either friends or enemies.(B,C,D,E,F)

Now apply pigeon hole principle again. Consider them as 5 nodes where these are connected by 4 edges which are of value 'f' or 'e' i.e friends or enemies. B---C---D---E---F.So we have ⌈4/2⌉=2.

So we have either 2 are enemies or 2 are friends vice versa. Now let us consider 2 are enemies and 2 are friends.

So B--(f)--C--(f)--D-(e)--E--(e)--F.

(where 'e' is for enemy edge and 'f' is for friend edge).

All the nodes B,C,D,E,F are connected to A as well as 'f' friends. From above we can see A,B,C,D are 4 mutual friends and D,E,F are 3 mutual enemies, which we have to proof.

(Drawing a graph for above might help. Similarly we can take 4 friends for A and prove it).

Abhishek Sharma
  • 21
1

$A$ can't have fewer than four friends and fewer than six enemies, because with only three friends and five enemies, friends + enemies would be $5+3=8$.

TonyK
  • 64,559