The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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$
asked in Graph Theory by Junior (647 points)
edited by | 94 views

2 Answers

+2 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!)
answered by Loyal (7.6k points)
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)
answered by Junior (647 points)

Related questions

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
49,532 questions
54,126 answers
71,046 users