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

        riddles >> medium >> Contagion
        
(Message started by: Grisha_Perelman on Feb 25th, 2007, 12:56pm)
Title: Contagion
Post by Grisha_Perelman on Feb 25th, 2007, 12:56pm
There are 1000 people in a village and some of them are friends (if a person A is a friend of B, then B is a friend of A). If a person is sick she will infect all her friends on the next day. It is known that no matter which subset of people gets sick first, after some time all village is infected.

Prove that it is possible to choose 90 people in such a way that if we infect them on the same day then in 10 days evryone in the village will be sick.
Title: Re: Contagion
Post by towr on Feb 25th, 2007, 1:21pm
[hide]We have a connected graph; taking the least-interconnected connected graph would be a single line. So in 10 days each person can infect ten people in both directions along the line, so including himself 21. Therefore, we need only http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.gif1000/21http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif=48 people[/hide]

Considering I seem to need so many fewer people, I'm having some doubts here..
Title: Re: Contagion
Post by towr on Feb 25th, 2007, 1:29pm
hmm, reconsidering, [hide]a 90-pointed 'star' seems more appropriate. And just one more person, and 90 wouldn't suffice any more. [/hide]
Title: Re: Contagion
Post by Grisha_Perelman on Feb 25th, 2007, 1:50pm
to towr:

In terms of graphs the problem is:

Prove that in any connected graph with 1000 vertices it is possible to choose 90 vertices in such a way that any vertex is at the distance no more than 10 from some of those 90 vertices.

You, if I understand correctly, gave two examples for which it is possible . But the problem asks for a proof that it is always possible to do.
Title: Re: Contagion
Post by towr on Feb 25th, 2007, 2:02pm

on 02/25/07 at 13:50:05, Grisha_Perelman wrote:
You, if I understand correctly, gave two examples for which it is possible . But the problem asks for a proof that it is always possible to do.
Yes, but the point is that I try to show it can be done for the hardest graph imaginable.
If it can be done in the worst case, it can be done in every case (because they're per definition at least as easy).

My first attempt was a bust because I quite clearly was mistaken in my assumption that it was the worst case.

Of course it remains to be proven that I have indeed found the worst case. Perhaps some transformation process that monotonicly progresses through simpler graphs is feasable..

[e]Also note, cycles only make it easier, and without cycles, we're between the two graphs I gave, one the extreme simple, one the extreme 'hard'.[/e]
Title: Re: Contagion
Post by Grisha_Perelman on Feb 25th, 2007, 2:25pm

on 02/25/07 at 14:02:59, towr wrote:
If it can be done in the worst case, it can be done in every case. Of course it remains to be proven that I have indeed found the worst case.

Oh, I see! I haven't thought about such approach! But proving that something is the worst case might be quite challenging here.



Title: Re: Contagion
Post by towr on Feb 25th, 2007, 2:40pm

on 02/25/07 at 14:25:18, Grisha_Perelman wrote:
Oh, I see! I haven't thought about such approach! But proving that something is the worst case might be quite challenging here.
I'm pretty confident I could morph my 'worst-case' to any other connected graph (keeping it covered each step of the way). If I can formalize such an approach in an algorithm it would also work as proof.
But I think I'll sleep on it first, as it's getting late here..
Title: Re: Contagion
Post by rmsgrey on Feb 26th, 2007, 10:16am
How a direct proof?:

Start by reducing the graph to a tree by deleting arbitrary edges from any cycles (removing edges never makes total infection faster).

From this tree, pick a longest path, and call the end-points A and B. If the distance between A and B is 20 or less, then the entire graph is within 10 of the midpoint, M, of that path (if not, the point C 11 away is either further from A than B is or further from B than A is since at least one of AC and BC has to pass through M and MC>MA and MC>MB by definition, so AB is not the longest path)


Otherwise, pick the point I 10 away from A along that path.
Label every node within 10 of I as infected.
Recursively remove every infected leaf.
The remaining graph will still be a tree, and if you can infect it with 89 initial infected, then those 89 plus I will infect the entire original graph.
This new tree is at least 11 nodes smaller than the original as the 11 nodes of the path AI must have been removed - if they hadn't, then I must still have at least one path between uninfected nodes passing through it. Both ends of that path must be at least 11 away from I, so one or other end of the path must be further from B than A was, contradicting the definition of AB as a longest path.

If you repeat this process - choosing an initial infected node 10 away from one end of the longest path on the new tree and recursively removing infected leaves - for a total of 89 iterations, then you will have removed at least 979 nodes, and have at most 21 remaining, with one initial infection to place. The longest possible path on any 21 node graph has length 20, so the last infection must be able to infect all the remaining nodes.

In general, with t days and n initial infected, a connected population, p=(n+1)(t+1)-1 can always be infected in the time.
Title: Re: Contagion
Post by Grisha_Perelman on Feb 26th, 2007, 2:52pm

on 02/26/07 at 10:16:44, rmsgrey wrote:
How a direct proof?:


Very clear, IMHO. That's the proof I had.
Title: Re: Contagion
Post by Grisha_Perelman on Feb 27th, 2007, 5:01pm
In fact, now I think that the better way to pose this puzzle is:

There are 1000 people in a village and some of them are friends (if a person A is a friend of B, then B is a friend of A). If a person is sick she will infect all her friends on the next day. It is known that no matter which subset of people gets sick first, after some time all village is infected.

What is the minimal number of people to be infected on the same day so that in 10 days everyone in the village will be sick.
Title: Re: Contagion
Post by tiber13 on Mar 1st, 2007, 9:49am
if you think out side of the box, if one of the people was an arse and was a friend to nobody then he would never get sick.......... ???
Title: Re: Contagion
Post by towr on Mar 1st, 2007, 10:39am

on 03/01/07 at 09:49:53, tiber13 wrote:
if you think out side of the box, if one of the people was an arse and was a friend to nobody then he would never get sick.......... ???
True, but it's given, in the problem statement, that eventually all people get sick if anyone gets sick at all. And with that the case that there might be some loner is excluded.
Title: Re: Contagion
Post by rmsgrey on Mar 2nd, 2007, 7:34am

on 02/26/07 at 14:52:56, Grisha_Perelman wrote:
Very clear, IMHO. That's the proof I had.

Thanks.

Credit where credit's due, I started by trying to patch towr's proof, and, having convinced myself that he's right about the worst case, stumbled into the final proof as a series of corrections to failed patches...
Title: Re: Contagion
Post by Eigenray on Mar 5th, 2007, 5:55pm

on 02/27/07 at 17:01:47, Grisha_Perelman wrote:
What is the minimal number of people to be infected on the same day so that in 10 days everyone in the village will be sick.

For a complete answer we must show the converse, that if p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif (n+1)(t+1), then it may not be possible to find n people such that everyone will be infected within t days.  For this, [hide]arrange the people in n+1 rows with at least t+1 people in each row, and connect along each row, and down the first column.  Then we must infect at least one person from each row, so we need at least n+1 people.[/hide]


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