3
$\begingroup$

I have the following puzzle and I want to check if the answers that I gave are correct. You can check also my reasoning behind the answers. The puzzle is:

In a perfect world two people are either friends or not friends. In this perfect world the population is exactly 6 people.

  • In this perfect world a group of $n$ people is called completely friends when each person in the group is friends with every other person in the group.

  • In this perfect world a group of $n$ people is called completely not friends when each person in the group is not friends with every other person in the group.

Which of the below statements are always true?

  1. We can always find a group of 3 which is either completely friends or completely not friends.

  2. If we have a group of 4 which are completely friends then the number of friendships is higher than the number of not friendships. (A friendship is when two people are friends. A not friendship is when two people are not friends.)

  3. If we have a group of 3 which are completely not friends, there is no way for each person to be friend with exactly two others.

  4. If we know that each two people have at least one common friend, then this means that we have a group of 4 which are completely friends.

  5. There is no way for each two people to have exactly one common friend (from the other four).

  6. There is no way for each two people to have exactly one common not friend (from the other four).

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ This is basic graph theory, more math exercise than puzzle. #1 is true, #3 is false. I'll explain later, but you will get better answers sooner on Math.SE $\endgroup$
    – Daniel Mathias
    May 20, 2020 at 10:14
  • 1
    $\begingroup$ Thanks, I found en.wikipedia.org/wiki/Theorem_on_friends_and_strangers which shows that for sure #1 is true. However, I have some problems to prove other stataments. $\endgroup$
    – Try a
    May 20, 2020 at 10:37
  • 1
    $\begingroup$ A very nice reference. Counterexample for #3 is row 4, column 8. $\endgroup$
    – Daniel Mathias
    May 20, 2020 at 10:59
  • 1
    $\begingroup$ A counterexample for #4 is the case where 2 out of the 6 (say, 1 and 2) are friends with everybody and there are no other friendships. Every pair that excludes 2 (1) has 2 (1) as a common friend, and 2/1 have every other person as common friends. But since 4/6 have only two friendships, there is no grouping of 4 complete friends. $\endgroup$
    – H Rogers
    May 20, 2020 at 12:08

1 Answer 1

Reset to default
3
$\begingroup$

Answer for 1

TRUE

Reason:

Each person is either friends with atleast 3 people or not friends with atleast 3 people. You can draw graph among people to get better understanding yourself. In the example mentioned by you, 1, 3 and 5 are completely not friends with each other

Answer for 2

FALSE

Reason

Correctly pointed out by you

Answer for 3

FALSE

Reason

Let 1,2,3 be completely non friends. Let 1 be friends with 4 & 5, 2 with 4 & 6 and 3 with 5 & 6. Every one is friends with exactly 2 others. Note, here apart from 1,2,3, the group of 4,5 & 6 is also not completely friends with each other.

Answer for 4

FALSE

Reason

Let 6 be common friend for any remaining pair(not involving 6 obviously). Now, let common friends of 1 & 6 be 2, 2 & 6 be 1, 3 & 6 be 2, 4 & 6 be 5 and 5 & 6 be 4. You will not find any group of four friends which are complete friends.

Answer for 5

TRUE

Reason

https://en.wikipedia.org/wiki/Friendship_graph#Friendship_theorem It states that if a finite graph has the property that every two vertices have exactly one neighbour in common then there must be a vertex adjacent to everybody, and the graph is one of the so-called friendship graphs. In this case it means that we would need to have someone being friend with everybody. But for that we would need odd number of vertices

Answer for 6

TRUE

Reason

This question is exactly the same question than the 5th one. Indeed we defining your graph, instead of putting an edge when two people are friend, put an edge when two people are not friends. Then question 6 asks for the same condition than our previous question 5 : a graph on 6 vertices where any two vertices have exactly one common neighbour, it is impossible as we have seen.

BONUS

Some parts of this quesiton have been more beautifully answered here https://math.stackexchange.com/questions/3683503/graph-logical-task-for-friendships

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Thanks for the answers. I was trying to prove them with graphs, and already managed some of them. However, your explanations are really good. Thanks! $\endgroup$
    – Try a
    May 20, 2020 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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