6
$\begingroup$

I need help with the following question which I cannot seem to solve:

17 students are sitting in a circle. Each person shakes hands with everyone but his/her neighbours. How many handshakes have been exchanged?

My approach: no. of ways $ = 1 + 2 + 3 + ... + 14 = 7(15) = 105 $.

Apparently my answer is wrong (correct ans is 119). But I can't seem to understand why. Could someone please explain?

$\endgroup$
  • $\begingroup$ The reason why this is wrong is as follows: the first person has 14 people to shake hands with. The second person as well has 14 people to shake hands with, since he wouldn't shake hands with his neighbour anyway! So, the sum is 14+(14+13+...+1), which does add up to 119. $\endgroup$ – Sanchises Feb 16 '15 at 19:49
15
$\begingroup$

Each of 17 people shakes hands with 14 people (all except themselves and their 2 neighbors), so there are

$$\frac{17\times 14}{2} = 119$$

handshakes (dividing by 2 to account for symmetry, as you would otherwise count "$A$ shaking hands with $B$" and "$B$ shaking hands with $A$" as distinct events).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Does it mean that we don't care about how they sit, say in a circle or in a row? $\endgroup$ – Nighty Feb 16 '15 at 15:04
  • 2
    $\begingroup$ @LeeKM: The difference is that in a circle, everyone has two neighbors, while in a row, the first and last person have only one each. $\endgroup$ – user139000 Feb 16 '15 at 15:05
  • $\begingroup$ Thanks! Now I know that I misunderstood the quuestion. I thought that the handshakes were to be made with distinct persons. $\endgroup$ – Donald Feb 16 '15 at 21:44
5
$\begingroup$

Here's another way to think about it.

If everyone shook hands with everyone you'd have $\frac {17*16}2 = 136$ handshakes (divide by 2 because the above is double counting A shaking hands with B and so forth).

However, there are $\frac {17*2}2 = 17$ handshakes that aren't happening because neighbors aren't shaking hands (2 neighbors for each of the 17 people, again divided by 2 to remove duplicates).

So $136-17 = 119$

Pew's response is a little more direct, but finding the number by calculating the total possibilities minus the "not allowed" interactions is sometimes a little more intuitive for some people.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

You can think of this in graph theory as the following:


$G$ has $17$ vertices with degree $14$, since there are no loops(people self handshaking), and no vertices are adjacent to the vertices beside them. So total degree is $17\times 14$.

We know that degree is equal to $2\times\text{number of edges}$ and hence there are $\frac{17\times 14}{2}=119$ edges in total, where edges represent handshakes.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

As is typical for problems with big numbers, you should always resort to a smaller number if you can't solve the full problem.

Here, 17 people at the table is a bit hard to imagine immediately.

Let's start with 3 people at the table.

How many handshakes now?

There are zero.

What about 4 people:

A B

C D

A can't shake with B or C, B can't with A or D, D can't with B or C, C can't with A or D--only A & D and B & C can shake.

So 2 shakes:

A B
 X
C D

5 people is when it gets interesting, and when you should be able to see the pattern:

      B

  A       C

    D   E

Everyone has two people they can't shake with, leaving two shakes per person--but we overcount by just multiplying 5 & 3, so we divide by two.

This is easiest to see by trying to draw the graph mentioned by @Commitingtoachalleng -- draw a line between any people who can shake hands:

        B
       / \
  A-----------C   (also C-D & A-E--a 5-point star)
     /     \
    D       E

So we hypothesize the answer is $\frac{n(n-3)}{2}$. Note that this formula holds for $n=3$ and $n=4$ as well, as we'd hope!

One final way to see this is to look again at the graphs--

you might notice that they're always complete graphs (every vertex connected to every other vertex) with the outer edges removed.

Since there are $\frac{n(n-1)}{2}$ edges in a complete graph on $n$ vertices (which you can confirm yourself by a similar process), and $n$ outer edges,

there must be $\frac{n(n-1)}{2} - n = \frac{n^2-n-2n}{2} = \frac{n(n-3)}{2}$ handshakes.

However you cut it, there are $\frac {17 \cdot 14} 2 = 119$ total handshakes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We should also point out that the second option (working backwards from complete graphs) is the graph analogue of @Duncan's solution $\endgroup$ – MichaelChirico Feb 17 '15 at 6:42
-1
$\begingroup$

I will explain for 6, same logic applies for all the numbers.

first, if 6 persons shakes will all in the party, then number of shakes will be:

A B C D E F

A can shake with only rest of 5 persons(B,C,D,E,F) i.e, right side ppl. = 5

B can shake with only his right sides(C,D,E,F) ppl(not with A bcos,A already shook with B just now. so no repeat) = 4

C can shake with only his right sides(D,E,F) ppl(not with A&B bcos,A&B already shook with C just now. so no repeat) = 3

D can shake with only his right sides(E,F) ppl(not with left side ppl bcos, they already shook with D just now. so no repeat) = 2

E can shake with only his right sides(F) ppl(not with left side ppl bcos, they already shook with E just now. so no repeat) = 1

as all of the persons shook hand with F, He dont shake with any one now.

So total possible shakes for 6 persons are = 5+4+3+2+1 => 15

now in questions it is given that, No one shakes hand with neighbors.

Imagine ppls sitting around table

        A   B
      F       C
        E   D   

Please treat above image as 6 Ppl around circle : So now,

Invalid Shakes:

A cannot shake with B,F . I am representing it as below : A -no- B & F => 2 invalid shakes.
B -no- C only. Bcos B -no- A is covered as part of first case.
=> 1 invalid shake
C -no- D only. => 1 invalid shake
D -no- E only. => 1 invalid shake
E -no- F only. => 1 invalid shake
F dont shake with A is already covered as part of first invalid shakes.

so total invalid shakes are 2+1+1+1+1 = 6

so for 6 ppl: out of total 15 , 6 are invalid. So 15-6 = 9

on the same line :

for 17 ppl: out of total (16+15+...+1)=136 , 17 are invalid. So 136-17 = 119

shortcut : For N ppl, Total shakes are (N-1)(first term + last term)/2 Arithmetic progression sum. out of which Invalids are N.
So valid shakes => (Total - N)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What is the point of posting such a complex answer to a question with a simple and accepted answer posted almost four years ago? $\endgroup$ – José Carlos Santos Oct 31 '18 at 17:23

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.