Author |
Topic: Handshakes (Read 1419 times) |
|
codpro880
Junior Member
Teachers strike, students hurt. English...
Gender: 
Posts: 89
|
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.
|
|
 IP Logged |
You miss 100% of the shots you never take.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Handshakes
« Reply #1 on: Jan 1st, 2009, 1:25pm » |
 Quote  Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Handshakes
« Reply #2 on: Jan 1st, 2009, 6:15pm » |
Quote Modify
|
63? for the maximum
|
| « Last Edit: Jan 1st, 2009, 6:15pm by howard roark » |
IP Logged |
|
|
|
codpro880
Junior Member
Teachers strike, students hurt. English...
Gender:
Posts: 89
|
|
Re: Handshakes
« Reply #3 on: Jan 2nd, 2009, 4:06pm » |
Quote Modify
|
Explain your solution roark!
|
|
IP Logged |
You miss 100% of the shots you never take.
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Handshakes
« Reply #4 on: Jan 2nd, 2009, 7:27pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Handshakes
« Reply #5 on: Jan 3rd, 2009, 12:55am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Handshakes
« Reply #6 on: Jan 3rd, 2009, 7:11am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Handshakes
« Reply #7 on: Jan 3rd, 2009, 10:43am » |
Quote Modify
|
on Jan 3rd, 2009, 7:11am, 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 ...
|
| « Last Edit: Jan 3rd, 2009, 2:56pm by Hippo » |
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Handshakes
« Reply #8 on: Jan 3rd, 2009, 12:48pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Handshakes
« Reply #9 on: Jan 3rd, 2009, 10:15pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Handshakes
« Reply #10 on: Jan 3rd, 2009, 11:11pm » |
Quote Modify
|
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
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Handshakes
« Reply #11 on: Jan 4th, 2009, 2:07am » |
Quote Modify
|
on Jan 3rd, 2009, 11:11pm, 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 Jan 3rd, 2009, 10:15pm, 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 .
|
| « Last Edit: Jan 4th, 2009, 2:33am by Hippo » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Handshakes
« Reply #12 on: Jan 4th, 2009, 1:17pm » |
Quote Modify
|
on Jan 4th, 2009, 2:07am, Hippo wrote:| No. The remaining handshakes are from symmetry as written in the post. |
|
Right, I missed that.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print