Ten people in a room

There are ten people in a room:

Person $1$ knows $9$ people. Person $2$ knows $8$ people. etc. Person $9$ knows $1$ person.

How many people does person $10$ know?

What is the answer and what is the principle behind this question?

You can think of this as a problem in graph theory. You have a graph $G$ on ten vertices (the ten people in the room ${ 1, 2, 3, ... 10 }$) where two people are connected by an edge if and only if they know each other. The degree or valence of a vertex $v \in G$, denoted $d_v$, is the number of edges connected to it (the number of people someone knows). You are given that $d_1 = 9, d_2 = 8, ... d_9 = 1$ and you want to know $d_{10}$ (so the problem gives you information here: it tells you that $d_{10}$ is uniquely determined by these conditions).

Here's one way to solve it, in steps.

• Person $1$ must know everyone else; that is, he must be connected to all of the other vertices (including person $10$). In particular, he must be the only person that person $9$ knows.
• Person $2$ must know everyone else except one person, and since person $9$ only knows person $1$, person $2$ must know everyone else except person $9$ (including person $10$). In particular, he must be the only other person that person $8$ knows.
• Person $3$ must know everyone else except two people, and since persons $8$ and $9$ have all their friends accounted for, person $3$ must know everyone else except persons $8$ and $9$ (including person $10$). In particular, he must be the only other person that person $7$ knows.
• ... and so forth. By induction we conclude that person $10$ knows persons $1, 2, 3, 4, 5$ but not persons $6, 7, 8, 9$. So $d_{10} = 5$.