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?
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.
Oh well that was complex
Isn't that more than 7 pairs of people though?
"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 : ∅
Log in to reply
The question specifies positive integers: H wouldn't be able to shake zero hands.
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.
Log in to reply
@Denis Baudouin – I speak french as well, and had the same reflexion as yours! I learned something today :p
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.
How do you know Alice didn't shake everyone's hands? Or that she was not the one that shook none?
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.)
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:
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 ?
If someone's answer were " 0 " that means the number " 7 " will disappear and the condition positive would disappear as well, and if 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
and assume that handshakes 1 , 2 , 3 , 4 , 5 , 6 , 7 distributed respectfully
meaning f1 made 1 hand shake and f2 made 2 handshakes, so on and so forth
If Alice has 7 hand shakes as f7 that would result in the disappearance of the number " 1 " as an answer (which means a contradiction to the 7 distinct numbers condition)
because Alice a n d f7 each would have been shook hands with the remaining 6 friends, meaning the other 6 friends each would have been shook hands "twice"
The same applies for 6 and 5 will result in the disappearance of the numbers " 2 " and " 3 "
So the only number remains is 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
And then came Alice and shook hands with f4 , f5 , f6 , f7 raising them up +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 .
Problem Loading...
Note Loading...
Set Loading...