Author |
Topic: Handshakes (Read 1105 times) |
|
Altamira_64
Junior Member
Posts: 116
|
 |
Handshakes
« on: Apr 26th, 2016, 12:37am » |
 Quote  Modify
|
32 people were invited in a party and started exchanging handshakes. Given the confusion, each of them shook hands with each other at least twice. What is the minimum number X that each invitee shook hands with each of the others, given that every two people exchanged a different number of handshakes from every other two people? That is, each invitee exchanged 2 to X handshakes and we are asking for the minimum possible value of X, to satisfy the above requirements.
|
| « Last Edit: Apr 26th, 2016, 1:00am by Altamira_64 » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2874
|
|
Re: Handshakes
« Reply #1 on: Apr 26th, 2016, 8:35am » |
Quote Modify
|
I'm not sure I understand the question. Is the following what was intended?
You have 32 people. For any given (ordered) pair of people, (a,b), let H(a,b) be the number of times a shook hands with b (by symmetry, H(a,b)=H(b,a) ).
Then H(a,b) >=2 except for H(a,a) = 0
and H(a,b) = H(c,d) only when (a,b)=(c,d) or (a,b)=(d,c)
Let H(a) be the total number of handshakes a is involved in: H(a) = SUMb(H(a,b) )
And we're asked to find one of:
i) the minimum possible value of H(a)
ii) the minimum possible value of H(a) when it's independent of a
iii) the minimum possible value of the maximum value of H(a,b) over all a and b
iv) something else
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Handshakes
« Reply #2 on: Apr 26th, 2016, 10:03am » |
Quote Modify
|
on Apr 26th, 2016, 12:37am, Altamira_64 wrote:| ..., given that every two people exchanged a different number of handshakes from every other two people? |
|
I have trouble with this one. Does it mean that (in rmsgrey's notation H(a,b) is different from H(c,d) if {a,b} and {c,d} are disjoint, or in every case where (a,b) and (c,d) are not the same pair?
In other words, can A and B shake hands the same number of times as A and C, since they are not strictly speaking 2 other persons.
|
| « Last Edit: Apr 26th, 2016, 10:06am by Grimbal » |
IP Logged |
|
|
|
Altamira_64
Junior Member
Posts: 116
|
|
Re: Handshakes
« Reply #3 on: Apr 26th, 2016, 10:18am » |
Quote Modify
|
We are not interested in numbers of handshakes of individuals; only of pairs.
Therefore, H(a,b) = H(b,a) but different from H(a,c).
Each distinct pair (a,b) shakes hands at least twice and up to X.
However, this "X" must be different for every couple.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Handshakes
« Reply #4 on: Apr 26th, 2016, 10:59am » |
Quote Modify
|
Can you give an example with 4 or 5 people?
The way I understand the problem, with 5 people, there are 10 possible pairs. They shake hands a different number of times, so the number of handshakes is from 2 to 11 to make 10 different numbers. So X is 11. For 5 people. Correct so far?
|
| « Last Edit: Apr 26th, 2016, 11:07am by Grimbal » |
IP Logged |
|
|
|
Altamira_64
Junior Member
Posts: 116
|
|
Re: Handshakes
« Reply #5 on: Apr 26th, 2016, 11:43am » |
Quote Modify
|
With 10 people we have 10!/2!8! possible pairs.
|
|
IP Logged |
|
|
|
anglia
Junior Member
Gender: 
Posts: 60
|
|
Re: Handshakes
« Reply #6 on: Apr 29th, 2016, 10:53pm » |
Quote Modify
|
I'll didn't understand your question
|
|
IP Logged |
ebooks
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Handshakes
« Reply #7 on: May 1st, 2016, 11:01am » |
Quote Modify
|
So I propose the answer: 32*31/2+1 = 497 handshakes. (i.e. people exchanged between 2 and 497 handshakes.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print