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

        riddles >> medium >> Handshakes
        
(Message started by: codpro880 on Jan 1st, 2009, 12:59pm)
Title: Handshakes
Post by codpro880 on Jan 1st, 2009, 12:59pm
You're in a room with 100 people, and one of them is sick. It's a party so everybody wants to meet everyone else. Assume that the people in this room shake hands once per minute (simultaneously), they have to shake a new hand every minute, once they have shaken someone's hand they can't shake it again because they want to meet new people, and if they shake a sick persons hand they become sick (immediately).

What's the minimum number of minutes required to make everyone sick?

What's the maximum length of time they can hold out before all of them become sick?

*Note* I created this riddle (sorry about the crappy wording). The minimum number of minutes is pretty easy to figure out, but I can't figure out the max. Please explain your solution thoroughly. I didn't know which forum to put it in either, easy or medium.
Title: Re: Handshakes
Post by towr on Jan 1st, 2009, 1:25pm
[hide]7 rounds of handshakes should be enough to get everyone sick; by doubling the number of sickies each round.

Not sure of the maximum number, I can get up to 50, at least (put them in two lines, and cycle them through one spot each round). But it should be possible to prolong it further.[/hide]
Title: Re: Handshakes
Post by howard roark on Jan 1st, 2009, 6:15pm
[hide]63? for the maximum[/hide]
Title: Re: Handshakes
Post by codpro880 on Jan 2nd, 2009, 4:06pm
Explain your solution roark!
Title: Re: Handshakes
Post by howard roark on Jan 2nd, 2009, 7:27pm
Divide people into two groups of 36 and 64.

People in the group of 64 contains the sick guy. First these 64 guys should finish shaking hands with each other. This takes 63 minutes.

Later these(people in group of 64) will shake hands with those in the group of 36. This makes everyone sick.


If the above method works, I think it should take 64 and not 63...I am not sure if what I told is correct!!!

Because in the above method people who are in the group of 36 will have to wait for sometime till the people in group of 64 are done with shaking hands among each other.
Title: Re: Handshakes
Post by Grimbal on Jan 3rd, 2009, 12:55am
This doesn't comply with the condition that everyone must shake a new hand every minute.

I assume the shaking must follow a schedule such that after 99 minutes everybody has shaken hands with everybody else.

So far, I have not been able to come up with a solution where someone remains uncontaminated past round 50.

If just 2 persons per round are allowed to shake no hands, you can create a schedule of 100 minutes where the last person gets contaminated in the very last minute.  You just need to form a "flat loop", 2 rows of people facing each other.  After each handshake, everybody shifts 1/2 a place left.  Sometimes there are single persons at each end.  These don't shake hands.  If the sick person starts as a single person at one end, then the last contamination happens in the last round.
Title: Re: Handshakes
Post by tohuvabohu on Jan 3rd, 2009, 7:11am
Imagine an infinite number of people, and try to minimize the number of infected people at any stage. If Number 1 is infected, you could start
1-2
1-3 2-4
1-4 2-3
1-5 2-6 3-7 4-8
1-6 2-7 3-8 4-5
1-7 2-8 3-5 4-6
1-8 2-5 3-6 4-7
(next round 9 through 16 are all infected at once)
It might seem that at times the number of infected can be less than two infectees per round. But that can only work if the total present is at least double; that is, in order for 1 through 4 to spend 4 rounds shaking hands with 5 through 8, there must be 8 non infected doing the same thing. With 10, 12 or 14 people, the non infected would run out of hands to shake before this algorithm was completed. I don't think there's any way to grow the infection any slower, so n/2 will always be the maximum.
Title: Re: Handshakes
Post by Hippo on Jan 3rd, 2009, 10:43am

on 01/03/09 at 07:11:00, tohuvabohu wrote:
Imagine an infinite number of people, and try to minimize the number of infected people at any stage. If Number 1 is infected, you could start
1-2
1-3 2-4
1-4 2-3
1-5 2-6 3-7 4-8
1-6 2-7 3-8 4-5
1-7 2-8 3-5 4-6
1-8 2-5 3-6 4-7
(next round 9 through 16 are all infected at once)
It might seem that at times the number of infected can be less than two infectees per round. But that can only work if the total present is at least double; that is, in order for 1 through 4 to spend 4 rounds shaking hands with 5 through 8, there must be 8 non infected doing the same thing. With 10, 12 or 14 people, the non infected would run out of hands to shake before this algorithm was completed. I don't think there's any way to grow the infection any slower, so n/2 will always be the maximum.


1-2
1-3 2-4
1-5 2-3 4-6
1-4 2-5 3-6

I got only 6 infected on 4th shake ... there is a small gap in the argumentation.

... Yes it seems there is no problem to make 50 infected and 50 non infected before shake nr. 50.

If numbers 99,100 shakes with 3,4 on first shake, it can be managed to shake together on last shake > 50.
Similarly 97,98,99,100 shakes with 5,6,7,8 on shakes 2 and 3 this saves onother 2 shakes ...
Title: Re: Handshakes
Post by tohuvabohu on Jan 3rd, 2009, 12:48pm
I was in error.  The pattern you presented didn't break the barrier, but the next handshake would have. Here's a full schedule for 10 guests, with two still uninfected after 5 rounds.
1-2: 3-8 4-9 5-10 6-7
1-3 2-4: 5-8 6-9 7-10
1-5 2-3 4-6: 7-8 9-10
1-4 2-5 3-6: 7-9 8-10
1-6 2-7 3-10 4-5: 8-9
Title: Re: Handshakes
Post by tohuvabohu on Jan 3rd, 2009, 10:15pm
I think I might have it this time. I predict a possible solution with all infected in round 74.
For the first 24 rounds, the number of infected will be 2*round.
Then 25 rounds where the number of infected stays constant at 50.
Then 25 more rounds increasing by 2
Here's an example with 16 guests infected in 11 rounds
1-2
1-3 2-4
1-4 2-5 3-6
1-5 2-6 3-7 4-8
1-6 2-7 3-8 4-5
1-7 2-8 3-4 5-6
1-8 2-3 4-6 5-7
1-A 2-9 3-5 4-7 6-8
1-C 2-B 3-1 4-9 5-8 6-7
1-E 2-D 3-C 4-B 5-1 6-9 7-8
1-0 2-F 3-E 4-D 5-C 6-B 7-A 8-9: All infected.
The unlisted uninfected handshakes are all inversely symmetrical with the infected, starting with 0-F in round 10 and working backwards.
I see no reason why this general method shouldn't work with any even number divisible by 4, infecting all at 3/4 N-1. I'm guessing this is pretty close to optimal, assuming the optimal will have the same symmetrical nature.
Title: Re: Handshakes
Post by TenaliRaman on Jan 3rd, 2009, 11:11pm
Just to clarify,
Are we relaxing the condition of everyone must shake new hands every minute to find an upper bound on the max rounds?

-- AI
Title: Re: Handshakes
Post by Hippo on Jan 4th, 2009, 2:07am

on 01/03/09 at 23:11:01, TenaliRaman wrote:
Just to clarify,
Are we relaxing the condition of everyone must shake new hands every minute to find an upper bound on the max rounds?

-- AI


No. The remaining handshakes are from symmetry as written in the post.


on 01/03/09 at 22:15:59, tohuvabohu wrote:
I think I might have it this time. I predict a possible solution with all infected in round 74.
For the first 24 rounds, the number of infected will be 2*round.
Then 25 rounds where the number of infected stays constant at 50.
Then 25 more rounds increasing by 2
Here's an example with 16 guests infected in 11 rounds
1-2
1-3 2-4
1-4 2-5 3-6
1-5 2-6 3-7 4-8
1-6 2-7 3-8 4-5
1-7 2-8 3-4 5-6
1-8 2-3 4-6 5-7
1-A 2-9 3-5 4-7 6-8
1-C 2-B 3-1 4-9 5-8 6-7
1-E 2-D 3-C 4-B 5-1 6-9 7-8
1-0 2-F 3-E 4-D 5-C 6-B 7-A 8-9: All infected.
The unlisted uninfected handshakes are all inversely symmetrical with the infected, starting with 0-F in round 10 and working backwards.
I see no reason why this general method shouldn't work with any even number divisible by 4, infecting all at 3/4 N-1. I'm guessing this is pretty close to optimal, assuming the optimal will have the same symmetrical nature.


1-2 | 9-A 8-B 7-C 6-D 5-E 4-F 3-0
1-3 2-4 | A-B 9-C 8-D 7-E 6-F 5-0
1-4 2-5 3-6 | 9-B A-D C-E 8-F 7-0
1-5 2-6 3-7 4-8 | A-C B-D E-F 9-0
1-6 2-7 3-8 4-5 | B-C D-E 9-F A-0
1-7 2-8 3-4 5-6 | C-D 9-E A-F B-0
1-8 2-3 4-6 5-7 | 9-D A-E B-F C-0
1-A 2-9 3-5 4-7 6-8 | B-E C-F D-0
1-C 2-B 3-A 4-9 5-8 6-7 | D-F E-0
1-E 2-D 3-C 4-B 5-A 6-9 7-8 | F-0
1-0 2-F 3-E 4-D 5-C 6-B 7-A 8-9 |

BTW: I would choose numbering from 0 to F instead of 1 to F, 0 ;)
And 74 looks well ;).
Title: Re: Handshakes
Post by TenaliRaman on Jan 4th, 2009, 1:17pm

on 01/04/09 at 02:07:26, Hippo wrote:
No. The remaining handshakes are from symmetry as written in the post.

Right, I missed that.

-- AI


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board