wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Handshakes
        
(Message started by: Altamira_64 on Apr 26^th, 2016, 12:37am)

Title: Handshakes
Post by Altamira_64 on Apr 26^th, 2016, 12:37am

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.

Title: Re: Handshakes
Post by rmsgrey on Apr 26^th, 2016, 8:35am

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) = SUM_b(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

Title: Re: Handshakes
Post by Grimbal on Apr 26^th, 2016, 10:03am

on 04/26/16 at 00:37:44, 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.

Title: Re: Handshakes
Post by Altamira_64 on Apr 26^th, 2016, 10:18am

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.

Title: Re: Handshakes
Post by Grimbal on Apr 26^th, 2016, 10:59am

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?

Title: Re: Handshakes
Post by Altamira_64 on Apr 26^th, 2016, 11:43am

With 10 people we have 10!/2!8! possible pairs.

Title: Re: Handshakes
Post by anglia on Apr 29^th, 2016, 10:53pm

I'll didn't understand your question

Title: Re: Handshakes
Post by Grimbal on May 1^st, 2016, 11:01am

So I propose the answer: [hide] 32*31/2+1 = 497 handshakes. (i.e. people exchanged between 2 and 497 handshakes.) [/hide]