The Gateway to Computer Science Excellence
+2 votes

Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his seven friends how many people they shook hands with during the party, and was surprised when they responded with seven distinct positive integers. Given that his friends were truthful, how many hands did Naveen shake?

  1. $4$
  2. $5$
  3. $6$
  4. $7$
in Graph Theory by
edited by | 171 views

2 Answers

+4 votes
Best answer
We can consider this as a graph problem.

Let there be 8 vertices in the graph each representing a person and let the edges represent the handshakes between them.

In the question, it is mentioned that no two people can shake hands more than once and a person can not shake hand with himself/herself, that means our graph is a simple, undirected graph having no multiple edges between the two vertices or self-loops.  

Upon asking her friends, Naveen gets "1, 2, 3, 4, 5, 6, 7" as the number of handshakes her seven friends did. which means 1,2,3,4,5,6,7 is the degree sequence of the 7 nodes in a graph and our problem is to find the degree sequence of the 8th vertex., i.e number of handshakes done by Naveen.

So our problem reduces to finding which of the given options on including in our degree sequence represents the simple graph which you can check using Havel-Hakimi theorem.

Ans is option A.

P.s:- No need to check for option B, D (Why? Think!)
selected by
0 votes
For example, all of naveen's friends with letter B, C, D, E, F, G, H. Since, we know that every naveen's friends responded naveen question with
$7$ distinct positive integers, we can guess that
B shook hands $7$ times
C shook hands $6$ times
D shook hands $5$ times
E shook hands $4$ times
F shook hands $3$ times
G shook hands $2$ times
H shook hands $1$ time
B shook hands  with all of Naveen's friends, including Naveen.
B $\rightarrow$ A, C, D, E, F, G, H
C shook hands  with all of Naveen's friends, including Naveen except H.
C $\rightarrow$ A, B,D, E, F, G
D shook hands  with all of Naveen's friends, including Naveen and except G and H.
D $\rightarrow$ A, B, D, E, F
E shook hands  with all of Naveen's friends, including Naveen and except F, G, H.
E $\rightarrow$ A, B, C, D
F only shook hands with B, C and D.
So, A shook hands with B, C, D, E ($4$ times)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,436 answers
95,247 users