11
$\begingroup$

Four married couples attend a party. Each person shakes hands with every other person, except their own spouse, exactly once. How many handshakes?

My book gave the answer as $24$. I do not understand why.


I thought of it like this:

You have four pairs of couples, so you can think of it as

M1W2, M2W2, M3W3, M4W4,

where M is a man and W is a woman. M1 has to shake 6 other hands, excluding his wife. You have to do this 4 times for the other men, so you have $4\times 6$ handshakes, but in my answer, you are double counting.

How do I approach this problem?

$\endgroup$
  • 3
    $\begingroup$ In your answer, you both overcounted and undercounted, and incidentally these happened to cancel out and give you the correct answer without having to do anything further. You did $4 \times (\text{Handshakes done by the men})$, which overcounted the man-man handshakes, but left out the woman-woman handshakes. $\endgroup$ – M. Vinay Mar 17 at 4:49
  • 2
    $\begingroup$ And that's easily fixed by counting all such handshakes in the same way, not just those done by men, so you get $48$. And now, as you said, you have indeed double-counted. But if you know it's exactly double counting, you can get the answer by halving it! $\endgroup$ – M. Vinay Mar 17 at 4:56
  • 4
    $\begingroup$ @Issel No, Person #2 being the spouse of Person #1, also has to shake hands with $6$ people, and so on, so it's $6 + 6 + 4 + 4 + 2 + 2 + 0 + 0 = 24$. $\endgroup$ – M. Vinay Mar 17 at 5:42
  • 2
    $\begingroup$ Possible duplicate of Handshakes in a party $\endgroup$ – Xander Henderson Mar 17 at 20:45
  • 2
    $\begingroup$ @user21820 Hm, if it gets reopened, I'll post an answer. I don't think I see why it got closed. Sure it's an elementary problem, but it clearly shows effort and at least a part of the question is why the specific method used seems to be wrong but gives the correct answer. $\endgroup$ – M. Vinay Mar 19 at 5:29
51
$\begingroup$

$8$ people. Each experiences handshakes with $6$ people. There are $6\times 8=48$ experiences of handshakes. Each handshake is experienced by two people so there $48$ experiences means $48\div 2=24$ handshakes.

$\endgroup$
31
$\begingroup$

Suppose the spouses were allowed to shake each other's hands. That would give you $\binom{8}{2} = 28$ handshakes. Since there are four couples, four of these handshakes are illegal. We can remove those to get the $24$ legal handshakes.

$\endgroup$
  • $\begingroup$ This uses Inclusion-Exclusion Principle. $\endgroup$ – smci Mar 17 at 11:48
  • $\begingroup$ Inclusion-Exclusion helps to find the cardinality of a union of non-disjoint sets. I'm merely using the fact that a set together with its complement (which are disjoint) comprise the entire universe. $\endgroup$ – Austin Mohr Mar 18 at 2:30
  • $\begingroup$ and that's just a case of Inclusion-Exclusion Principle. (By the way, the set we're enumerating here isn't the 'entire universe', since it's not the total number of handshakes, or handshakes with all people in the world, or even n-way handshakes with all people.) $\endgroup$ – smci Mar 19 at 0:27
11
$\begingroup$

You may proceed as follows using combinations:

  • Number of all possible handshakes among 8 people: $\color{blue}{\binom{8}{2}}$
  • Number of pairs who do not shake hands: $\color{blue}{4}$

It follows: $$\mbox{number of hand shakes without pairs} = \color{blue}{\binom{8}{2}} - \color{blue}{4} = \frac{8\cdot 7}{2} - 4 = 24$$

$\endgroup$
6
$\begingroup$

Let's look at it not from individuals, but from couples. There are four couples, i.e. $3!=6$ meetings of couples. Per meeting of couples, there are four handshakes. This makes it $6\times4=24$ handshakes.


Thanks @CJ Dennis for pointing out an error in the reasoning: It should, of course, be the sum, not the product, so the correct number of meetings of couples is $\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$.

$\endgroup$
2
$\begingroup$

Each line is a handshake between the required two people. There are 24 lines:

enter image description here

$\endgroup$
1
$\begingroup$

$k$ couples entails $2k$ people. If we imagine each couple going in sequential order, couple 1 will each have to shake $2k-2$ couple's hands for each individual, or $4k-4$ handshakes for couple 1 total. Since there is 1 fewer couple every time a new couple shakes hands, there will be $4k-4i$ handshakes by the $i$-th couple. So the total number of handshakes is given by:

$$\sum_{i=1}^k (4k-4i) = \sum_{i=1}^k4k - \sum_{i=1}^k4i = 4k^2 - 4\frac{k(k+1)}{2} = 4(k^2 - \frac{k^2+k}{2}) = 4(k^2 - (\frac{k^2}{2} + \frac{k}{2})) = 4(\frac{k^2}{2}-\frac{k}{2}) = 2(k^2-k)$$

for $k$ couples. Plugging in $k$ = 4 verifies a solution of 24 for this case.

$\endgroup$
  • 1
    $\begingroup$ Well… Each of the $2k$ people shakes hands with $2k - 1 - 1 = 2k - 2$ others (everyone except the spouse). So that's $2k(2k- 2) = 4k(k - 1)$, but since every handshake must've been counted twice, divide that by $2$ to get $2k(k - 1)$ handshakes in total. $\endgroup$ – M. Vinay Mar 17 at 5:36
1
$\begingroup$

A simple approach:

There are 8 person in total.

Each one will shake hands with 6 others.

Total shakehands from individual perspective: 6*8 gives 48

Actual shakehands: 48/2 = 24

$\endgroup$
  • 5
    $\begingroup$ How is different from fleablood's answer? $\endgroup$ – Toby Mak Mar 17 at 8:46
  • 1
    $\begingroup$ @TobyMak sorry, I really didn't see it. When I posted there were only four answers including mine. That answer was really not there, completely surprised. I don't know how this happened? $\endgroup$ – Vijendra Parashar Mar 17 at 15:28
  • 1
    $\begingroup$ I see. Since you wrote your answer independently from fleablood, it's only fair to keep your answer. $\endgroup$ – Toby Mak Mar 18 at 8:22
-2
$\begingroup$

If all of them handshakes each other then there are 8!/2! =28 handshakes, but none of them handshake with their own spouse so their are 28-4=24 handshakes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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