Friends (Hard)
A group of people numbered are going to your house for a party. To not let anyone feels left out, you want to befriend the one with the least number of friends. To achieve that, you will ask each of them the question "How many friends do you have?" and note down their response. Before working out the details, you want to make sure that no one give false information. That is, there is at least one possible network of friendships that matches the responses.
Below is a list of responses taken from a group of 30 people. Coincidentally, the number of friends are in decreasing order . Output the first (leftmost) person whom answer must be false. That is, it is possible to generate a network based from the responses of those before him, but not after him. If it is possible to generate a network of friendship, put your answer as 0.
29 29 28 25 23 23 22 20 19 17 17 16 14 14 14 14 13 8 7 7 6 6 6 5 5 5 4 4 1 1
Clarifications :
-
Friendship is mutual. If is 's friend, then is 's friend as well.
-
You are not counted as their friends at the moment.
-
The first person is indexed as 1.
You are encouraged to solve the Medium version of this problem first.
The answer is 29.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The first person claims to befriend everyone else, and we have to take it as the truth at the moment since we don't have anymore information yet. But if we look at the last 2 responses by the 29th and the 30th individuals, both of whom told us that each of them only befriended one other person, and this mutual friend must be our first person who we believe to be everyone's friend. If this is really the case, then the first liar is the second person whose number of friends might only be 27 at most. If that is not the case, then it must be that the loners' mutual friend is actually the second person, or that the loners' friend is actually two different person, of Person 1 AND Person 2.
Anyway, assuming that the lonelier people are, the more honest they'd be, the first two response can never be 29+29, the reality should be 29+27 or 28+28 or 27+29.
Answer = 29