Friends (Easy)
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 10 people. Answer
True
if it's possible to find a network of friendships that matches,
False
otherwise.
2 4 3 2 5 3 2 1 1 2
Clarifications :
-
Friendship is mutual. If is 's friend, then is 's friend as well.
-
You are not counted as their friends at the moment.
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
One critical observation is that if the responses are valid, the sum of number of friends must be even. This is because each friendship will be counted twice.
The sum of number of friends is odd, thus is not possible to build a network of friendship.