Learn / Library / Brainteasers

Counting acquaintances

BrainteasersMedium

At a conference $15$ people meet. Acquaintance is mutual. Each person writes down how many of the other $14$ people they know. What is the largest possible number of people who wrote an odd number?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Add up all the numbers written down and think about what each acquaintance contributes.

Solution

Each acquaintance between $2$ people is counted by both of them, so the sum of the written numbers is the number of acquaintances multiplied by $2$ , an even number.
So the number of people with an odd count is even, and cannot be $15$ ; it is at most $14$ .
The value $14$ is possible: split $14$ people into $7$ couples who know only each other, and let the last person know nobody.
Then $14$ people wrote $1$ , and the answer is $14$ .

Answer: $14$

Next question Back to the library