How many handshakes?

Alice invited seven of her 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, Alice asked each of her 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 her friends were truthful, how many hands did Alice shake?

0 3 5 6 7 1 4 2

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Ferren Alwie
Jul 18, 2015

Oh well that was complex

Shivam Mittal - 5 years, 11 months ago

Isn't that more than 7 pairs of people though?

Saksham Bansal - 5 years, 8 months ago

"3" should be a correct answer too:

If we represent Alice and her friends with these letters : A (for Alice), B, C, D, E, F, G, H

(A : B,C = A shook and with B and C)

B : A,C,D,E,F,G

C : A,B,D,E,F

D : A,B,C,E

E : B,C,D

F : B,C

G : B

H : ∅

denis baudouin - 3 years, 6 months ago

Log in to reply

The question specifies positive integers: H wouldn't be able to shake zero hands.

Tyler Friedman - 3 years, 5 months ago

Log in to reply

Thanks for your answer. It seems that in french (my native language), zero is considered both positive and negative, but not in english.

denis baudouin - 3 years, 5 months ago

Log in to reply

@Denis Baudouin I speak french as well, and had the same reflexion as yours! I learned something today :p

dontneed toknow - 3 years, 2 months ago

Since one friend shook everyone's hand, that person is effectively not contributing any information and can be removed, while decreasing everyone else's count by 1 (including Alice's). That leaves counts 0 through 5, plus Alice. Now one person shook no one's hand, and can be removed, leaving 1 through 5, plus Alice. That person with "5" shook everyone's hand, and can be removed, etc. Do this once more to get two people, Alice and one other person, and the other person only shook 1 hand (Alice's). That means Alice shook one hand. Undo the three steps earlier (where we subtracted 1 from Alice each step), adding 3 to Alice, and you get 4 for Alice.

This is basically using the Havel-Hakimi algorithm, and is how I did it too.

Ben Reiniger - 4 years, 5 months ago

How do you know Alice didn't shake everyone's hands? Or that she was not the one that shook none?

Dave Hilger - 3 years, 1 month ago

Log in to reply

Her friends shook unique positive integers, so 1--7; Alice is not included in that list. At first, perhaps she did shake everyone's hand, but one of her friends did too, and Lawrence removes that friend (and not Alice). (We find eventually exactly whose hands Alice shook, but you can see already here that she did not shake everyone's hand: if she had, then both she and her 7-shaking friend shook everyone's hand, so that everyone shakes at least two hands. Similarly she can't have shaken no hands, because she has a friend who shook everyone's including hers.)

Ben Reiniger - 2 years, 10 months ago
Jonathan Aldana
Jul 22, 2015

Friends represented by letters: A, B, C, D, E, F, G and H. In parentheses are the friends that have shaked hands with that specific friend. Then the total shakes for that specific friend is shown:

  • A (BCDEFGH) = 7 shakes.
  • B(ACDEFG)=6 shakes.
  • C(ABDEF)=5 shakes
  • D(ABCE)=4 shakes.
  • E(ABCD)=4 shakes.
  • F(ABC)=3 shakes.
  • G(AB)=2 shakes.
  • H(A)=1 shake.

The only number of shakes repeated is 4, so the answer is 4. All the other ones are discarted, as they are unique.

can't even begin to figure this out. Where do i start learning HOW to solve these kind of problems ?

Simon Cochrane - 4 years, 4 months ago
Ahmed Obaiedallah
Oct 27, 2015

If someone's answer were " 0 \textbf{0} " that means the number " 7 \textbf{7} " will disappear and the condition positive \textbf{positive} would disappear as well, and if Alice \textbf{Alice} was to answer "0" that means there are at least 2 of her 7 friends will have the same number of handshakes

Now we know for sure the friends hold the numbers from 1 to 7 for handshakes and Alice holds a repeated number to one of them

So, let's name her friends f1 , f2 , f3 , f4 , f5 , f6 , f7 \color{#D61F06}{\textbf{f1}}, \color{#3D99F6}{\textbf{f2}}, \color{maroon}{\textbf{f3}}, \color{magenta}{\textbf{f4}}, \color{lime}{\textbf{f5}}, \color{#20A900}{\textbf{f6}}, \color{#EC7300}{\textbf{f7}}

and assume that handshakes 1 , 2 , 3 , 4 , 5 , 6 , 7 \color{#D61F06}{\textbf{1}}, \color{#3D99F6}{\textbf{2}}, \color{maroon}{\textbf{3}}, \color{magenta}{\textbf{4}}, \color{lime}{\textbf{5}}, \color{#20A900}{\textbf{6}}, \color{#EC7300}{\textbf{7}} distributed respectfully

meaning f1 \color{#D61F06}{\textbf{f1}} made 1 \color{#D61F06}{\textbf{1}} hand shake and f2 \color{#3D99F6}{\textbf{f2}} made 2 \color{#3D99F6}{\textbf{2}} handshakes, so on and so forth

If Alice \textbf{Alice} has 7 hand shakes as f7 \color{#EC7300}{\textbf{f7}} that would result in the disappearance of the number " 1 \textbf{1} " as an answer (which means a contradiction to the 7 distinct numbers condition)

because Alice a n d f7 \textbf{Alice}\space and\space \color{#EC7300}{\textbf{f7}} each would have been shook hands with the remaining 6 \textbf{6} friends, meaning the other 6 \textbf{6} friends each would have been shook hands "twice"

The same applies for 6 \textbf{6} and 5 \textbf{5} will result in the disappearance of the numbers " 2 \textbf{2} " and " 3 \textbf{3} "

So the only number remains is 4 \Large\color{#3D99F6}{\boxed{4}}

It's like if the 7 friends shook hands together with respect to the condition

And the result was

f1=1 , f2=2 , f3=3 , f4=3 , f5=4 , f6=5 , f7=6 \color{#D61F06}{\textbf{f1=1}}, \color{#3D99F6}{\textbf{f2=2}}, \color{maroon}{\textbf{f3=3}}, \color{magenta}{\textbf{f4=3}}, \color{lime}{\textbf{f5=4}}, \color{#20A900}{\textbf{f6=5}}, \color{#EC7300}{\textbf{f7=6}}

And then came Alice \textbf{Alice} and shook hands with f4 , f5 , f6 , f7 \color{magenta}{\textbf{f4}}, \color{lime}{\textbf{f5}}, \color{#20A900}{\textbf{f6}}, \color{#EC7300}{\textbf{f7}} raising them up +1 \textbf{+1} handshake

Since handshakes involve two persons, the total number of handshakes by everyone involved will be an even number - zero is even, and every handshake increases the count by one for two persons. The sum of 1 + 2 + 3 + 4 + 5 + 6 + 7 is 28, so we know that Alice must have shaken an even number of hands. (We already knew that she didn't shake them all (7), since all of her other friends shook hands with all distinct, positive , numbers - including seven, since she has seven friends here - which means that someone only shook one person's hand...and it wasn't hers; sounds kind-of rude for a "friend," but at least that person came to the party.)

So, Alice shook either two, four or six hands. It couldn't have been six, for similar reasons to why it couldn't have been seven: since two other people shook seven and six hands, there can only be one person who shook one hand, and one person who shook only two hands. Hey, by that argument, that means that she couldn't have only shaken two hands, either.

Thus, Alice must have also shaken four hands .

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...