# 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?

-
The word you want is "principle." –  Qiaochu Yuan Dec 2 '10 at 23:49
Can we assume that if $a$ knows $b$, then $b$ knows $a$? Else the answer can be any number between $0$ and $9$. –  user17762 Dec 3 '10 at 0:52

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).
• 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$.