2

I am stuck on this question.

Could somebody give some advice on how to tackle/solve this question? I believe that with „always one“ the question means at least one. (otherwise it will not work)

Your help would be very appreciated.

Michal

For a big group of people we know that:
If we select any four persons from the group, that there is always one of the four persons that will be friends with the other three persons.

Therefore, for any four persons selected from the group, will there always be one person that is friends will all people from the whole group?

MJD
  • 65,394
  • 39
  • 298
  • 580
MHuber
  • 21
  • I don't see how it works, regardless of the interpretation of “always one”. What if it's a giant group of strangers and none of them knows any of the others? – MJD Feb 26 '15 at 19:22
  • @MJD There can't be none that know any others. Just select four members of the big group at random, then one of those four is friends with the other three. – J126 Feb 26 '15 at 19:24
  • 1
    Oh, that's a given condition. I thought it was what we were trying to prove. – MJD Feb 26 '15 at 19:26
  • And see also another answer here. – Brian M. Scott Feb 26 '15 at 21:55

2 Answers2

2

Assume the conclusion is false, then we find four people $A,B,C,D$ in the group for which all four of them have someone in the group who is not their friend. In particular we will find that $A$ and $B$ both have someone who is not their friend, denoted by $\bar{A}$ and $\bar{B}$ respectively. Consider the configuration $A,\bar{A},B,\bar{B}$. Now clearly here we don't find a person who is friends with the other $3$, contradicting the assumption.

Edit: If $\bar{A}$ and $\bar{B}$ are the same person, consider $A,C,\bar{A},\bar{C}$. (Where $\bar{C}$ is the "antifriend" of $C$). If also $\bar{C}=\bar{A}$ then $A,B,C,\bar{A}$ will do.

Uncountable
  • 3,520
  • This is under the assumption that if $A$ is not friends with $B$, then $B$ is not friends with $A$. Do you need that assumption? – J126 Feb 26 '15 at 19:46
  • I feel like it is reasonable to assume that friendship is symmetric. – Uncountable Feb 26 '15 at 19:49
  • I feel it is reasonable as well. I'm just wondering if we need it. – J126 Feb 26 '15 at 19:49
  • @Joe Johnson Yes we do need it. Consider $A,B,C,D,E,F,G,H$, where each of $A,B,C,D$ is friends with everyone else (assymetrical towards $E,F,G,H$), and each of $E,F,G,H$ are only friends with each other. Now if a group of four people contains at least one of $A,B,C,D$ then this person will be friends with the other three. If it does not then it contains all $E,F,G,H$, so for instance $E$ will be friends with the other three. Now consider the group $E,F,G,H$ again. None of them is friends with everyone else. – Uncountable Feb 26 '15 at 19:55
  • What if $\bar{A}$ and $\bar{B}$ are the same person? – J126 Feb 26 '15 at 20:10
  • @Joe Johnson Actually, that is a good point. I will edit the answer. – Uncountable Feb 26 '15 at 20:14
2

Here is a proof using induction. For four people it is certainly true. Now suppose you have a group of $n$ people and the claim is true for all groups of size less than $n$. Select person $A$ at random and remove them from the group. This group will have someone who is friends with everyone. Set them aside with $A$ and call them $B$. Do this two more times to get $C$ and $D$. One of $A$, $B$, $C$, or $D$ will be friends with the three others. If it's $A$ then $B$ is friends with $A$ and everyone else by assumption. So, $B$ is friends with the group of $n$ people. If it is $B$, $C$, or $D$ then they will be friends with the whole group of $n$ people.

J126
  • 17,451