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