Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The word you want is "principle." –  Qiaochu Yuan Dec 2 '10 at 23:49
3  
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

1 Answer 1

up vote 6 down vote accepted

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$.
share|improve this answer
    
Thank-you very much –  Ian Messiter Dec 3 '10 at 0:04
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. –  Joseph Malkevitch Dec 3 '10 at 3:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.