recategorized by
650 views
3 votes
3 votes

Five married couples attended a party. In the party, each person shook hands with those they did not know. Everyone knows his or her spouse. At the end of the party, Shyamal, one of the attendees, listed the number of hands that other attendees including his spouse shook. He got every number from $0$ to $8$ once in the list. How many persons shook hands with Shyamal at the party?

  1. $2$
  2. $4$
  3. $6$
  4. $8$
  5. Insufficient information
recategorized by

1 Answer

4 votes
4 votes
$\text{There are 10 attendees in total,}\\ \text{Shyamal counts all the hands shaken by everyone other than him.}$

$\text{no. of hands that other attendees including his spouse shook (expcept him) }$

$\quad \quad= \sum_{i=0}^{8}(i) = \frac{8\times 9}{2} = 36.$

$\text{Hand shaking lemma state that,} \\ \text{The sum of total hand shakes(sum of degrees) should be even,} \\  \text{total no. of  handshakes expect him is 36, }$

$\text{Therefore, No of persons who shook hands with Shyamal should be even.} \\ \quad \quad \text{(Let it be n)}$

$\text{There are 5 different possible values of n \{0,2,4,6,8\}, } \\ \text{and 5 different degree sequences as follows:}$

$ n =8, \quad \\ \quad \text{degree sequence: } \\ \quad \quad 8,8,7,6,5,4,3,2,1,0 \\ \quad \quad 0,7,6,5,4,3,2,1,0,0  \quad \quad \rightarrow \text{Not possible, we can’t delete 7 now.}$

$ n =6, \quad \\ \quad \text{degree sequence: } \\ \quad \quad 8,7,6,6,5,4,3,2,1,0 \\ \quad \quad 0,6,5,5,4,3,2,1,0,0 \\ \quad \quad 0,0,4,4,3,2,1,0,0,0 \\ \quad \quad 0,0,0,3,2,1,0,0,0,0 \quad \quad \rightarrow \text{Not possible, we can’t delete 3 now.}$

$ n =4, \quad \\ \quad \text{degree sequence: } \\ \quad \quad 8,7,6,5,4,4,3,2,1,0 \\ \quad \quad 0,6,5,4,3,3,2,1,0,0 \\ \quad \quad 0,0,4,3,2,2,1,0,0,0 \\ \quad \quad 0,0,0,2,1,1,0,0,0,0 \\ \quad \quad 0,0,0,0,0,0,0,0,0,0 \quad \quad \rightarrow \textbf{one possible degree sequence.}$

$ n =2, \quad \\ \quad \text{degree sequence: } \\ \quad \quad 8,7,6,5,4,3,2,2,1,0 \\ \quad \quad 0,6,5,4,3,2,1,1,0,0 \\ \quad \quad 0,0,4,3,2,1,0,0,0,0  \quad \quad \rightarrow \text{Not possible, we can’t delete 4 now.}$

$ n =0, \quad \\ \quad \text{degree sequence: } \\ \quad \quad 8,7,6,5,4,3,2,1,0,0  \quad \quad \rightarrow \text{Not possible, we can’t even delete 8}$

$\text{Only possible value for n is 4.}$

$\textbf{Hence B is Answer.}$
edited by
Answer:

Related questions

1 votes
1 votes
1 answer
2
soujanyareddy13 asked Mar 25, 2021
631 views
Find the following sum.$$\frac{1}{2^{2}-1}+\frac{1}{4^{2}-1}+\frac{1}{6^{2}-1}+\cdots+\frac{1}{40^{2}-1}$$$\frac{20}{41}$$\frac{10}{41}$$\frac{10}{21}$$\frac{20}{21}$$1$
3 votes
3 votes
2 answers
3
soujanyareddy13 asked Mar 25, 2021
696 views
Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ in any sequence ...
1 votes
1 votes
1 answer
4
soujanyareddy13 asked Mar 25, 2021
595 views
What is the area of a rectangle with the largest perimeter that can be inscribed in the unit circle (i.e., all the vertices of the rectangle are on the circle with radius...