Author |
Topic: Contagion (Read 1598 times) |
|
Grisha_Perelman
Newbie
Gender: 
Posts: 17
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Contagion
« Reply #1 on: Feb 25th, 2007, 1:21pm » |
 Quote  Modify
|
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  1000/21 =48 people
Considering I seem to need so many fewer people, I'm having some doubts here..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Contagion
« Reply #2 on: Feb 25th, 2007, 1:29pm » |
Quote Modify
|
hmm, reconsidering, a 90-pointed 'star' seems more appropriate. And just one more person, and 90 wouldn't suffice any more.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Contagion
« Reply #3 on: Feb 25th, 2007, 1:50pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Contagion
« Reply #4 on: Feb 25th, 2007, 2:02pm » |
Quote Modify
|
on Feb 25th, 2007, 1:50pm, 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]
|
| « Last Edit: Feb 25th, 2007, 2:07pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Contagion
« Reply #5 on: Feb 25th, 2007, 2:25pm » |
Quote Modify
|
on Feb 25th, 2007, 2:02pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Contagion
« Reply #6 on: Feb 25th, 2007, 2:40pm » |
Quote Modify
|
on Feb 25th, 2007, 2:25pm, 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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Contagion
« Reply #7 on: Feb 26th, 2007, 10:16am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Contagion
« Reply #8 on: Feb 26th, 2007, 2:52pm » |
Quote Modify
|
on Feb 26th, 2007, 10:16am, rmsgrey wrote:
Very clear, IMHO. That's the proof I had.
|
|
IP Logged |
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Contagion
« Reply #9 on: Feb 27th, 2007, 5:01pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: Contagion
« Reply #10 on: Mar 1st, 2007, 9:49am » |
Quote Modify
|
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.......... 
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Contagion
« Reply #11 on: Mar 1st, 2007, 10:39am » |
Quote Modify
|
on Mar 1st, 2007, 9:49am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Contagion
« Reply #12 on: Mar 2nd, 2007, 7:34am » |
Quote Modify
|
on Feb 26th, 2007, 2:52pm, 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...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Contagion
« Reply #13 on: Mar 5th, 2007, 5:55pm » |
Quote Modify
|
on Feb 27th, 2007, 5:01pm, 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  (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, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print