wu :: forums - Print Page


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

        riddles >> easy >> Infection!
        
(Message started by: zbudde on Jan 24^th, 2013, 9:04am)

Title: Infection!
Post by zbudde on Jan 24^th, 2013, 9:04am

Not really sure what level this belongs in, but I thought this is a pretty fun problem (that I haven't figured out yet).

There are 36 students in a class, each with a cup of water. One of the students has an "infected" cup. It has an invisible chemical in it so no one knows who has it. Each round everyone has to mix their cup with two separate people. There isn't a particular order to the mixing (a student who has mixed his once in that round can mix with someone who hasn't yet). After 3 rounds what is the probability that you will get infected assuming you do not start off with the infected cup?

Have fun fellow nerds!

Title: Re: Infection!
Post by Grimbal on Jan 24^th, 2013, 9:21am

Is the mixing random?

If yes, what is the process by which the choice of who mixes with who is made?

If not, I would propose to 2 people to mix the cups only between the 3 of us at each round.
This way, after one round you are either all infected or definitely safe. The question is only whether one of the 2 was infected.
That gives a probability of 2/35 to end up infected if you were not from the start.

Title: Re: Infection!
Post by towr on Jan 24^th, 2013, 11:25am

We did an experiment like that in high school for sex ed. using milky water and starch as infectant, and finally iodine to reveal which cups were 'infected'.

Anyway..
If in each round we make groups of three, that don't share members that were in a group before, then after round 1, there's 3 infected, after round 2 there's 9. And then round 3 gets trickier..
At most 18 extra get infected, but it may be as low as none. So there's at least a definite 25% chance you're not infected, but there's another potential 50% to be divided. :-/
And at that point I'd probably rather do a Monte Carlo simulation than work it out by hand. :P

Title: Re: Infection!
Post by zbudde on Jan 24^th, 2013, 2:53pm

I forgot to mention this, but you can not mix with the same person more than once. So you can't stick with the same 3 people all 3 rounds. The tricky part, for me at least, is the fact that not everyone does their first mix and second mix at the same time. So in the first round the infect person is guaranteed to infect 2 people, but potentially 3 if the first person he mixed with has not mixed with anyone else yet, because that person will infect the second person they mix with to get infected. Does this make sense or did I explain it poorly?

Title: Re: Infection!
Post by towr on Jan 24^th, 2013, 10:37pm

So basically every round you start with one person that picks another, then that person pick another etc, until you get a loop. Then if anyone hasn't had a turn yet you pick a random one and go on?
(Actually, there are multiple ways to go here, cause you can grow the chains on both ends. And you could start multiple chains at the same time.)

So then there's even a very small chance everyone gets infected in the first round.

Title: Re: Infection!
Post by rmsgrey on Jan 25^th, 2013, 4:27am

What's the smallest group that can stay closed under the rules? It's at least 7 (and, presumably, not more than 36), so, if you can arrange with groups of 7 (and one of 8 ) you can keep the infection rate down to at most 22.2%

The other question is what happens if 34 people complete their 2 mixings without involving the remaining pair? They can manage one of their mixings with each other, but they'll have to either repeat, or give someone a third mixing...

Title: Re: Infection!
Post by Nursejim on Sep 30^th, 2013, 12:46pm

on 01/24/13 at 22:37:30, towr wrote:

I believe it would be impossible for everyone to be infected 1st round. am I wrong?

Title: Re: Infection!
Post by towr on Sep 30^th, 2013, 12:50pm

Not in that scheme. You just chain from the first infected person up to the last in one round.
So how the infection can spread depends very much on how the round proceeds. If every connection between people is simultaneous, then the infection can't spread to everyone in one round, but if you process everyone/every link one after the other, then it can happen.