The Straggler Shakes Hands - posted March 22, 1999

Last week, our town celebrated St. Patrick's day by having a parade. One of the floats held the Mayor and all the council members. At the end of the parade, everyone shook hands with everyone else.

A straggler suddenly arrived and shook hands with only those people he knew. Altogether, there were one hundred forty-one handshakes. How many people did the straggler know? How many people were on the float?

If you use any variables, be sure to represent them. Show all work and explain your reasoning.

Comments

We had lots of participation with this problem, and I was pleased to see it.

There were several places to learn about the classic handshake problem and how to solve it. One place to visit would have been Handshake Problem from the Dr. Math archives.

Highlighted solutions:

The straggler knew 5 people.  There were 17 people on the float.

The first step is to find the number of combinations of �E'  that is

near 141.



The number of combinations is determined by:    nCr

Factorial n / [Factorial (n-r) x Factorial r]



...where    n = number of people

        r = number to combine = 2 people hand-shaking



The closest combinations are:

With n = 16:    120 combinations

With n = 17:    136 combinations    [ 17! / (15! * 2!) ]

With n = 18:    153 combinations



Obviously 18 people produces too many handshakes in total (>141).

But 16 people does not produce enough handshakes.  The straggler would

have to shake 21 hands to reach 141.



So there are 17 people and the straggler shakes the hand of 5 of them.

    [136 + 5 = 141]

A float contained 17 people who shook hands with each other once. Then a

strggler arrived and shook hands with the 5 people he knew.

The number of handshakes that takes place in a group in which everyone shakes

everyone elses hand (where n represents the number of people) is equal to (n -

1) + (n - 2) + (n - 3) ... + 1 + 0. This can be simplified to (n^2 - n) -

((n^2 - n) / 2), which equals (n^2 - n)/2. Now we can solve for n, to

determine the number of people on the float, since we know that this number is

less then 141, which tells us that n <= 17. Since if n were equal to 16 or

less, the straggler would end up shaking hands with more people then are on

the float, we know that n = 17. We can now evaluate ((17^2 - 17)/2) an find

out that the number of handshakes taken before the straggler arrived was 136.

This means the Straggler took 5 handshakes.

The Straggler know 5 people.  There are 17 people on the float.

The formula to find how many handshakes are there if everyone shook

hands with everyone else is: (x-1)x/2.  x is the number of people.



I have an equation like this:

       (x-1)x/2 + a = 141



(x-1)x/2 is the number of handshakes when everyone shook hands with

everyone else on the float.  A is the number of handshakes the

straggler shook which is also the number of people the straggler

know.  The total number of handshake altogether is 141.



Instead of solving the equation that I now have I did it

differently.  I looked at the equation and I saw that if I took out a

then (x-1)x/2 would be less than 141 so it would be like this.



                                       (x-1)x/2 < 141

I solved this inequality.              (x-1)x  < 282

Now I need to find two number where the first number is one less than

the second number that when I multiply them it would be less than 282.

I chose x to be 17.  so it's 16 multiply 17 which is equal to 272.

272 is less than 282.   I tried x as 18 to see if it also work, so it

would be 18 multiply 17 equal 306.  Nope, it's not less than 282. now

I know that x have to be 17 or less.



   Now I go back to my equation at the begining which is

(x-1)x/2 + a = 141.   I put 17 in the x place and now I only have one

variable.  I solve it:

                                         (17-1)17/2 + a = 141

The number of handshake before the      136 + a = 141

straggler came is 136......makes            a = 141-136

sense, this tells me that it might        a  = 5

be the answer because that number

should be less than 141.



This is the answer:

X=number of people     a=number of people straggler know

X= 17                  a= 5



I know that x has to be less than 17 so now I tried x as 16 to see if

it works also, and solve it like how I just did.  If x equal 16 than

a would have to equal 21 so the total handshake would be 141.  But

then it can't be because we already say that there's 16 people on the

float so the straggler couldn't have shake hand with 21 because

that's more than 16 and there's only 16 people on the float.  So the

answer can't be 16 or less either so the only answer is there's 17

people on the float.

The straggler knew 5 people, and there were 17 people on the float

(not including the straggler).

Okay, here's what I did.  I took a number of people, and then

determined how many handshakes these people exchanged.  I did this

from the numbers 1 to 6.  Using this information, I determined the

pattern that if there are "n" people, they exchange



n(n-1)

------

   2



handshakes.  Since there were 141 handshakes, I set 141 equal to the

pattern I discovered.



141 = n^2 - n

      -------

         2



282 = n^2 - n



From there, I completed the square by adding 1/4 to each side



1129/4 = (n - 1/2)^2



1129^(1/2)

----------  = n - 1/2

    2



n = 1 + 1129^(1/2)

    --------------

          2



n = approx  17.300



Since there can't be 17.300 people on the float, I rounded it down to

17 and plugged it into the formula.  If there were 17 people on the

float, 136 handshakes would be exchanged.  Since the straggler

arrived, he exchanged handshakes with the 5 people he knew, and

altogether, 141 handshakes were exchanged.

The straggler knows 5 people. There were 17 people on the float.

I found it easier to answer the questions in reverse order. The first

problem is how to relate the number of handshakes (h) to the number of

people (n). So I sketched a few easy examples using letters:



n=2 AB  h=1



n=3 AB BC   h=3

    AC



n=4  AB BC CD  h=6

     AC BD

     AD



I had to be careful not to "duplicate" handshakes, eg AB and BA are

the same handshake so only one can be counted. I noticed that when

counting up you could do it, eg for n=4



1+2+3=6,



i.e. the sum of the first three counting numbers. This is just the sum

of a simple arithmetic progression with initial term a=1 and common

difference d=1, with 'n' terms. After searching the web I found the

formula for the sum Sn of the first n terms of an arithmetic

progression:



Sn=[(2a+d(n-1))n]/2



In this case the formula is



Sn=[(2+(n-2))(n-1)]/2



I had to subtract 1 from 'n' because in this case n=1 yields h=0,

whereas in the arithemtic progression  S1=1.



Just to check this was correct I tried n=5 in the formula giving

S5=10, then I sketched the problem as above and counted.



AB  BC CD DE

AC  BD CE

AD  BE

AE



Counting gives h=10 so this is OK so far.



Now after this long preliminary I can consider the problem in hand.

Setting the number of people the straggler knows to be X then we have

the equation:



[(2+(n-2))(n-1)]/2 + X = 141



Ignoring the straggler complication for the moment, I tried to come up

with a value for n which would give h pretty close to 141. I reasoned

a council probably wouldn't have more than 20 or less than 10 members,

so tried these both giving h=190 and h=45 respectively, so clearly the

answer is somewhere between the two. I started at the top and worked

down till I got h close to and less than 141. I then worked out what X

would be in each case.



I got n=17 giving h=136, X=5, and n=16 giving 120, X=21.



At first it appears there are two or more solutions, I could have

obtained solutions right down to n=2 giving X=140, but there is an

additional constraint on X in that it cannot exceed h. (It must also

be noted that n, X and h must be integers.) This is algebra for saying

that the straggler can't know any more people on the float than there

are people on the float, which is a bit of a mouthful but is just

common sense. The only solution which satisfies this additional

constraint is:



n=17 and X=5.

There were 17 people on the floats and the straggler knew 5 people.

I let:

   n = the number of people on the floats (except the straggler)

   N = the number of people the straggler knew.



I count the number of handshakes between the n people on the float.

The 1st people makes (n-1) handshakes to the others; then the second

people makes (n-2) handshakes to the remaining; then the third makes

(n-3) handshakes to the remaining, etc. ; and finally, the (n-1)th

people makes only 1 handshake to the last people. The number of

handshakes between these n people is therefore

   (n-1)+(n-2)+(n-3)+ ... + 3 + 2 + 1

By looking at the sum of the first and last numbers, of the second

and second last numbers (that's exactly what Gauss did when he was a

primary school student) etc., I found that the number of handshakes

between n people on the floats is

   (n-1)+(n-2)+(n-3)+ ... + 3 + 2 + 1 = n(n-1)/2



Since this number of handshakes and the number of handshakes the

straggler made add up to 141, we have

       n(n-1)/2 + N = 141.



To solve this equation, I first note that N must be greater or equal

than zero, so

   141 = n(n-1)/2 + N >= n(n-1)/2   or   n(n-1) <= 2*141=282

By trial, I found that

                  n <= 17                                 (1)

On the other hand, the straggler cannot know more than n people, so

N<=n and we obtain

   141 = n(n-1)/2 + N <= n(n-1)/2 + n   or   n(n+1) >= 282

Again, by trial , I found

                  n >= 17                                 (2)

From (1) and (2), I conclude that n = 17. Substitute into the

equation I get

   17(17-1)/2 + N = 141  or  136 + N =141. Hence N=5.



Therefore, there were 17 people on the floats and the straggler knew

5 of them.

There were 17 people on the float and the straggler knew five of them.

When a group of (n) people shakes hands, each person shakes (n-1)

hands since they shake all but their own.  However, the total number

of handshakes does not equal [n(n-1)] because this would be counting

person A shaking person B's hand as a separate event from person B

shaking person A's hand.  This would be counted as two handshakes

when in reality it is only one.  I found it helpful to think of a

group of people in which one person shakes everyone else's hand, and

then a second person does the same, then a third, and so on....  In

order to compensate for the loss in number of shakes from [n(n-1)],

after the first person is done shaking his (n-1) hands, he should

leave since he has already shaken everybody's hand.  This means that

the second person to shake actually shakes only (n-2) hands, since he

has already shaken one.  The total number of handshakes within the

group is then equal to:



Total=1+2+3+...+(n-1)



The total is also the number that is closest to 141 without going

over that satisfies this equation.  Only one (n)-value can possibly

satisfy this, and that is 17.  This creates a total number of

handshakes on the float of 136.  The number of people the straggler

knows is then just the 141-136=5.

There were 17 persons in the float and the straggler knew 5 of them.

Let's note:

 n - the number of the people in the float

 k - the number of people the straggler knew



Let's count first the number of handshakes before the straggler

came.Every person shakes hands with the rest of n-1 persons.So we have

a total number of n*(n-1) handshakes. Taking into consideration the

fact that we counted twice each handshake (when person i shakes hands

with person j and again when person j shakes hands with i),we have to

divide this number by 2. So the number of handshakes before the

straggler came is:

  n*(n-1)/2         (1)



The straggler shakes hands with k persons,where k verifies:

   0<=k<=n          (2)

We have:

   n*(n-1)/2 + k = 141     (3)



From (2) and (3) we get:



   n*(n-1)/2<=141<=n*(n-1)/2 + n

   n*(n-1)/2<=141<=n*(n+1)/2      (4)



Solving the inequations (4) in N (the natural numbers set),we have the

only possible solution:



   n=17                           (5)



Getting back in (3),we obtain:

  k = 141 - 17*16/2 = 141 - 136 = 5



  k = 5                           (6)



It means there were 17 persons in the float and the straggler knew 5

of them.

There were 17 people on the froat and the straggler shook 5 of them.

First make a list to find the relationship between the # of people

and # of handshakds.

  # of people    1   2   3   4   5 ... n

# of handshakes  0   1   3   6   10    ?



# of handshakes= 0   1   1   1   1     ? will be (n-1)+(n-2)+(n-3)....

                         +   +   +     and there's gonna be the # of

                         2   2   2     (n-1) factores.

                             +   +     So there's an equation,

                             3   3     n(n-1)/2. This has to be equal

                                 +     or less than 141 because there

                                 4     were 141 handshakes.



        n(n-1)/2<,=141        The domain for n is -16.3<n<17.3, but

           n^2-n<,=282        since n is # of people, it has to be

       n^2-n-282<,=0          positive and a whole number. So n could

(n-17.3)(n+16.3)<,=0          be any whole number between 0~17.



But since the # of people that the straggler shook hands can't be

more than the # of people who were there, there's an equation,

  141-n(n-1)/2<n

   282-n^2+n-n<0

          -n^2<-282

           n^2>282

             n>+,-16.79



Now the n has to be more than 16.79, so the only number that obeys

the all n domain is 17.

  17(17-1)/2=136    141-136=5

There were 17 council members on the float.  The straggler knew 5

people.

There is a simple rule to solve this problem:

                    y * (y-1) / 2 = z

y equals the number of people on the float and z equals the total

amount of handshakes.  This works because a triangle is half of a

square, this is why you divide the number in the problem by two:

Person 1            1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Person 2            1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Person 3            1 2 3 4 5 6 7 8 9 10 11 12 13 14

Person 4            1 2 3 4 5 6 7 8 9 10 11 12 13

Person 5            1 2 3 4 5 6 7 8 9 10 11 12

Person 6            1 2 3 4 5 6 7 8 9 10 11

Person 7            1 2 3 4 5 6 7 8 9 10

Person 8            1 2 3 4 5 6 7 8 9

Person 9            1 2 3 4 5 6 7 8

Person 10           1 2 3 4 5 6 7

Person 11           1 2 3 4 5 6

Person 12           1 2 3 4 5

Person 13           1 2 3 4

Person 14           1 2 3

Person 15           1 2

Person 16           1

Person 17



As shown in the diagram above, there would be 17 people on the float.

If you totaled the amount of handshakes shown in the diagram, it would

total 136 handshakes.  If 141 handshakes occured, that proves that the

straggler shook hands with 5 people.

There were 17 people in the float without counting the straggler.

The straggler knew 5 people.

To find the number of people in the float before the straggler came I

made this chart:



    # of people              # of handshakes

        2                            1

        3                            3

        4                            6

        5                            10

        6                            15

        7                            21

        8                            28

        9                            36

        10                           45

        11                           55

        12                           66

        13                           78

        14                           91

        15                           105

        16                           120

        17                           136

        18                           153

        19                           171



The number of handshakes is 141. Then the closest number is 136 (17

people). If the number of people was 16, then there would be 120

handshakes. Then there would be missing 21 handshakes, but the

straggler cannot know more people than there really are in the float,

so the number must be 17 people. Then the straggler knows 5

people!!!

There were 17 people on the float, and the straggler knew 5.

Let there be n people on the float.

Think of the people as dots.

When two people shake hands, think of it as a line drawn between

the two dots.

The total number of handshakes before the straggler came is the

number of possible 2-dot lines made in this group of n dots. In other

words, it' s the number of ways you can chose a pair of dots from n

dots: C(n,2).

The straggler shook hands with 0 to n people, so

   C(n,2)  < the toal number of handshakes < C(n,2) + n

Try a few numbers

   C(10,2) = 45 too low

   C(20,2) = 190 too high

   C(15,2) = 105 too low

   C(17,2) = 136 looks good

Check: 136 < 141 < 136 +17  ?

            136 < 141 < 153         yes!

Therefore, there were 17 people on the float, and the straggler knew

141-136 = 5 people.

96 students received credit this week.

Madeel Abdullah, age 15 - Marple Newtown Senior High School, Newtown Square, PA
Steve Adams, age 14 - Palm Harbor University High School, Palm Harbor, FL
Ashley Andreone, age 15 - Shaler Area High School, Pittsburgh, PA
Martin Angert, age 14 - Holland Junior High School, Holland, PA
C. Anghel, age 16 - Mackenzie High School, Deep River, Canada
C. J. B., age 16 - none, San Francisco, CA
Anna Bankowski, age 14 - Maria Carrillo High School, Santa Rosa, CA
Wayne Beisch, age 15 - Watertown Senior High School, Watertown, SD
Adam Bezilla, age 16 - Shaler Area High School, Pittsburgh, PA
Angela Bookwalter, age 15 - Shaler Area High School, Pittsburgh, PA
Christopher Bourguignon, age 14 - Cosackie-Athens High School, Coxsackie, NY
Jonathan Bowen, age 14 - Freehold Township High School, Freehold, NJ
Teddy Buffington, age 10 - Heritage Heights, Amherst, NY
Jill Burkhart, age 16 - Shaler Area High School, Pittsburgh, PA
Laura Cancienne, age 15 - Fontainebleau High School, Mandeville, LA
Dolie Chacko, age 15 - Marple Newtown Senior High School, Newtown Square, PA
Eric Chen, age 13 - Brookhurst Junior High School, Anaheim, CA
Jason Chiu, age 13 - Laramie High School, Laramie, WY
Katie Clark, age 16 - Shaler Area High School, Pittsburgh, PA
Josh Clayton, age 15 - Rockford High School, Rockford, MI
Kristopher Clearwater-Ross, age 15 - Cosackie-Athens High School, Coxsackie, NY
Monica-Ramona Costache, age 14 - Mihai Viteazul High School, Bucharest, Romania
Luis Ernesto Criales Escobar, age 12 - British International College, Barranquilla, Colombia
Jenni Crom, age 15 - Watertown Senior High School, Watertown, SD
Beth Cutler, age 14 - Roosevelt High School, Minneapolis, MN
Jason Desiderio, age 10 - Heritage Heights, Amherst, NY
Devin Duncan, age 15 - Dayspring Academy, Whitefish, MT
Jerrod Early, age 16 - Shaler Area High School, Pittsburgh, PA
Jared Elizares, age 14 - Amador Valley High School, Pleasanton, CA
Jenn Elliott, age 16 - Marple Newtown Senior High School, Newtown Square, PA
Betsy Feldman, age 15 - Marple Newtown Senior High School, Newtown Square, PA
Emily Fike, age 16 - Shaler Area High School, Pittsburgh, PA
Kelsey Fourdyce, age 15 - Edwardsville High School, Edwardsville, IL
Ariel Franks, age 11 - Forsyth School, St. Louis, MO
Mariko Furukawa, age 16 - Shaler Area High School, Pittsburgh, PA
John Gabel, age 15 - Watertown Senior High School, Watertown, SD
Lisa Gardner, age 8 - Boyette Springs Elementary School, Riverview, FL
Kristen Geubtner, age 15 - Shaler Area High School, Pittsburgh, PA
Emily Guh, age 11 - Wissahickon Middle School, Ambler, PA
Frankie Guiliano, age 13 - Sawgrass Springs Middle, Coral Springs, FL
Bob Haas, age 16 - Shaler Area High School, Pittsburgh, PA
Christine Hu, age 11 - Kennedy Junior High, Cupertino, CA
Sarah Imboden, age 16 - Maria Carrillo High School, Santa Rosa, CA
Tim Kelley, age 25+ - none, Austin, TX
Dave Kennedy, age 25+ - none, Lethbridge, Canada
Dan Kert, age 16 - Pacific Grove High School, Pacific Grove, CA
Lauren Leo, age 16 - Shaler Area High School, Pittsburgh, PA
Karlene Lihota, age 16 - Marple Newtown Senior High School, Newtown Square, PA
Russ Lutz, age 16 - Shaler Area High School, Pittsburgh, PA
Michael Mastroianni, age 11 - Heritage Heights, Amherst, NY
Dan McCoy, age 15 - Marple Newtown Senior High School, Newtown Square, PA
Ryan McHugh, age 15 - Shaler Area High School, Pittsburgh, PA
Wes McKinney, age 14 - St. Edward School, Ashland, OH
Martin McNicoll, age 19 - Strathclyde University, Glasgow, Scotland, UK
Erin Meyer, average age 15 - Shaler Area High School, Pittsburgh, PA
Jai Mirchandani, age 15 - Geelong Grammar School, Corio, Australia
Jeffrey Mo, age 9 - University Elementary School, Calgary, Alberta, Canada
Michael Moyer, age 17 - The Way Home School, Carlisle, PA
Preeti Nalavade, age 12 - Wissahickon Middle School, Ambler, PA
Ryan Newman, age 16 - Shaler Area High School, Pittsburgh, PA
Tien Nguyen, age 14 - Johnson Middle School, Westminster, CA
Nicole Czake, average age 16 - Shaler Area High School, Pittsburgh, PA
Scott Niekum, age 16 - Shaler Area High School, Pittsburgh, PA
Megan Olson, age 15 - Watertown Senior High School, Watertown, SD
Evie Pitts, age 13 - Manhattan Beach Middle School (MBMS), Manhattan Beach, CA
Lewis Rentz, age 13 - Wacoochee Junior High School, Salem, AL
Danielle Resick, age 15 - Watertown Senior High School, Watertown, SD
Farhad Roueintan, age 17 - Carson Graham Secondary School, North Vancouver, Canada
Emily Schindler, age 15 - Shaler Area High School, Pittsburgh, PA
John Schirrippa, age 16 - East Hampton High school, East Hampton, NY
Hanna Schmerbeck, age 15 - Gesamtschule Hattingen, Hattingen, Germany
Kim Schneider, age 16 - Shaler Area High School, Pittsburgh, PA
Kelly Scott, age 16 - Shaler Area High School, Pittsburgh, PA
Michael Selick, age 14 - Cresskill Jr/Sr High School, Cresskill, NJ
Nicole Sharpe, age 10 - Wilderness School, Walkerville, SA 5081, Australia
Nathanael Shea, age 16 - St. Louis Priory School, St. Louis, MO
Aaron Sichmeller, age 15 - Watertown Senior High School, Watertown, SD
Ainie Soetanto, age 14 - Marple Newtown Senior High School, Newtown Square, PA
Jessica Soine, age 15 - Watertown Senior High School, Watertown, SD
Ana Sovic, age 16 - XV. Gimnazija, Zagreb, Croatia
Jamie Stark, age 16 - Shaler Area High School, Pittsburgh, PA
Jennica Stetler, age 14 - Champlain Valley Union High School, Hinesburg, VT
Nathan Strauss, age 11 - Forsyth School, St. Louis, MO
Melissa Tengowski, age 15 - Shaler Area High School, Pittsburgh, PA
Bob Tobin, age 16 - Shaler Area High School, Pittsburgh, PA
Paul Tolomeo, age 16 - Shaler Area High School, Pittsburgh, PA
Tim Tordoff, age 15 - Watertown Senior High School, Watertown, SD
Peter Tran, age 10 - Summer Hill Public School, Sydney, Australia
Alex Tuchel-Veyhl, age 11 - Forsyth School, St. Louis, MO
Internet User, age 25+ - homeschooled, Roselle Park, NJ
Asher Walkover, age 16 - Rambam Mesivta, Lawrence, NY
Michael White, age 16 - Shaler Area High School, Pittsburgh, PA
Brian Wineberg, age 16 - Shaler Area High School, Pittsburgh, PA
Doug Wolfe, age 16 - Shaler Area High School, Pittsburgh, PA
Renee Worst, age 16 - Shaler Area High School, Pittsburgh, PA
Shuo Zhang, age 15 - Marple Newtown Senior High School, Newtown Square, PA

View most of the solutions submitted by the students above