9
$\begingroup$

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?

  • 0
    The word you want is "principle."2010-12-02
  • 3
    Can we assume that if $a$ knows $b$, then $b$ knows $a$? Else the answer can be any number between $0$ and $9$.2010-12-03

1 Answers 1

7

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$.
  • 1
    It does not seem to me that mathematical induction is being used in the argument above. There is an interesting infinite class of graphs related to this example with degrees: 3, 2, 2, 1; 5, 4, 3, 3, 2, 1; 7, 6, 5, 4, 4, 3, 2, 1; the example above, etc. The number of edges in these graphs is respectively, 4, 9, 16, 25, etc.2010-12-03