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.

I found no one I graded so far had given a correct proof. The embarassing side is I also do not know how to find a simple proof. So I decided to ask. The question is:

Eight students in a class are asked how many of the other seven student they know. One student knows all the other students. But only two students know the same number of students. Show that these two students know each other.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

I don't know if this is simple enough, but here goes.

Everyone knows between zero and seven. Since someone knows seven, no one knows zero. Since only two know the same number, the degrees of the vertices in the acquaintanceship graph must be 1, 2, 3, 4, 5, 6, 7, with one repeat.

Since there's a 7 and a 6, there can't be two 1s. So there's a single 1.

Since there's a single 1 and a 2, there can't be two 6s. So there's a single 6.

Since there's a 7, a 6, and a 5, there can't be two 2s. So there's a single 2.

Since there's a single 1 and a single 2 and a 3, there can't be two 5s. So there's a single 5.

Since there's a 7, a 6, a 5, and a 4, there can't be two 3s. Now we've ruled out everything but two 4s.

The 7 knows everyone. The 6 knows all but the 1. The 5 knows all but the 1 and the 2. Each 4 knows all but the 1, 2, and 3. So, the 4s know each other.

share|improve this answer
3  
Does it simplify the argument if you use the handshaking lemma? By the handshaking lemma you get there is an even number of people that know an odd number of people. Therefore you cannot have 1, 3, 5 or 7 as your repeats. Then you are just lef to discard 2 and 6. –  fidbc Feb 28 '13 at 5:39
2  
@fidbc: You don’t even have to discard $6$: if there are two $6$’s, neither can know the $1$, so they must know each other. –  Brian M. Scott Feb 28 '13 at 7:16
    
@Gerry: I appreciate your effort. Much embarrassed. –  Bombyx mori Feb 28 '13 at 12:18
    
Nothing to be embarrassed about. Kudos to @fidbc and Brian for their simplifications. –  Gerry Myerson Feb 28 '13 at 12:21

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.