Author |
Topic: Oddly dispersing disease (Read 646 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Oddly dispersing disease
« on: Nov 15th, 2004, 2:10pm » |
 Quote  Modify
|
There is a set of N villages each connected to its neighbours by some medium through which disease can spread. (i.e say they form a graph (need not be complete graph) with the medium links as edges).
Now, these set of villages are prone to affliction by a strange disease, called the Oddly Dispersing Disease (or ODD for short). ODD spreads as follows: if on a day, a village V has an odd number of its neighbours afflicted by ODD, the next day V gets afflicted by ODD too, otherwise it becomes disease free (does not matter if V was currently afflicted or not). This goes on in steps, day after day... The villages can do nothing but watch...
The villages were all happily disease free when it so happened one day that some of them got afflicted with ODD. They observed that it took them more than N days to become completely disease free again. (by completely disease free, it means *that all* the villages were disease free)
Show that it is possible that they can get afflicted again in such a way that there is always some village which is afflicted with ODD from that day on. i.e. the villages will never be completely disease free ever again.
[Edit]
To be clear: It need not be the same village that is diseased everyday. Just that the set of villages diseased on day X is non-empty and need not contain the same elements as day Y etc.
Also, to rephrase the problem in Icarus' words (with a modification):
given that there is some initial configuration that results in more than N days to become disease-free, prove that there is also an initial configuration resulting in some village (need not be the same one) being diseased every day.
[/Edit]
[EDIT1]
Late realisation:
If the disease goes away, then it goes away in no more than N steps!
In the original statement, I am asking you to prove A implies B, with A being FALSE!
Anyway, there are two things that can be done.
1) Prove the statement of the original problem (i.e A implies B)
OR
2) Prove: If the disease does not go away in N days, then it never goes away. (i.e prove that A is false, which proves A implies B...)
[/EDIT1]
|
| « Last Edit: Nov 17th, 2004, 1:25pm by Aryabhatta » |
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Oddly dispersing disease
« Reply #1 on: Nov 15th, 2004, 8:59pm » |
Quote Modify
|
 Obviously the villagers are delusional. Having been completely disease-free, it impossible for them to have ever gotten the disease, as each day all of the villages had 0 diseased neighbors. Since 0 is even, they will not have the disease the next day either!
[Okay - I do know what you mean: given that there is some initial configuration that results in more than N days to become disease-free, prove that there is also an initial configuration resulting in one village always being diseased.]
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #2 on: Nov 15th, 2004, 9:53pm » |
Quote Modify
|
on Nov 15th, 2004, 8:59pm, Icarus wrote:Obviously the villagers are delusional. Having been completely disease-free, it impossible for them to have ever gotten the disease, as each day all of the villages had 0 diseased neighbors. Since 0 is even, they will not have the disease the next day either!
|
|
Quote:
[Okay - I do know what you mean: given that there is some initial configuration that results in more than N days to become disease-free, prove that there is also an initial configuration resulting in one village always being diseased.] |
|
Every day it might be a different village that is diseased, need not be the same one every day. I should have phrased that properly.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Oddly dispersing disease
« Reply #3 on: Nov 16th, 2004, 6:11am » |
Quote Modify
|
If there are two villages with a single edge between them, and both start out infected, then there will always be at least one infected (two, actually, but the problem states n >= 1) because there are always an odd number of infected neighbors.
Given a graph in the shape of a ring with a number of villages N where N % 3 == 0, infect every third village. The next day, the infected villages will become disease free because they have zero neighbors with the disease. Their neighbors will become infected because they have one diseased neighbor. This inverts the circle so every third is disease free, the rest are diseased. This gives the base case above, with twin villages infected with a buffer zone between them. These buffer villages have two infected neighbors, so they remain disease free. This status goes on forever.
While this case only holds for a very specific type of graph, it does prove that such a configuration exists. I do not have the math skills to prove it for all cases.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Oddly dispersing disease
« Reply #4 on: Nov 16th, 2004, 3:08pm » |
Quote Modify
|
Remember that the villages have gotten the disease before, and it took more than N days to go away. Two isolated villages will not satisfy this condition - the infection never goes away. For the ring, I have yet to figure out a scenario wherein the infection is not permanent, but still takes more than N days to go away (though this may simply be lack of imagination).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #5 on: Nov 16th, 2004, 3:24pm » |
Quote Modify
|
on Nov 16th, 2004, 3:08pm, Icarus wrote:| Remember that the villages have gotten the disease before, and it took more than N days to go away. Two isolated villages will not satisfy this condition - the infection never goes away. For the ring, I have yet to figure out a scenario wherein the infection is not permanent, but still takes more than N days to go away (though this may simply be lack of imagination). |
|
I am sorry. I just realised...
If the disease goes away, then it goes away in no more than N steps!
I am asking you to prove A implies B, with A being FALSE!
Anyway, there are two things that can be done.
1) Prove the statement of the original problem (i.e A implies B)
OR
2) Prove: If the disease does not go away in N days, then it never goes away. (i.e prove that A is false, which proves A implies B...)
Sorry, I should stop posting half-baked problems...
|
| « Last Edit: Nov 16th, 2004, 3:25pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #6 on: Nov 17th, 2004, 1:23pm » |
Quote Modify
|
Anyone still interested in this?
I found it a little surprising that if the disease goes away, it must go away within N days.
I guess the way the original problem is stated makes the problem seem more interesting... 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Oddly dispersing disease
« Reply #7 on: Nov 17th, 2004, 2:13pm » |
Quote Modify
|
on Nov 17th, 2004, 1:23pm, Aryabhatta wrote:| Anyone still interested in this? |
|
Well, not in the sense that I have any idea of how to approach it, I'm just watching whether anyone else provides some insight.
Quote:| I found it a little surprising that if the disease goes away, it must go away within N days. |
|
For no good reason I would have expected something like that.
Anyway, it's interesting enough, but I'm not any good with graphs.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #8 on: Nov 17th, 2004, 3:38pm » |
Quote Modify
|
on Nov 17th, 2004, 2:13pm, towr wrote:
Anyway, it's interesting enough, but I'm not any good with graphs.
|
|
hint:
You don't need any graph theory to solve this. It if were, it probably would have been in the CS section.
::
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Oddly dispersing disease
« Reply #9 on: Nov 17th, 2004, 6:47pm » |
Quote Modify
|
It's interesting, but right now I have too much going on to be able to think about it in any depth (it has actually been a long time since I have been able to contribute much of substance to this site).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #10 on: Nov 21st, 2004, 1:02pm » |
Quote Modify
|
Here is a hint.
What goes on can be written as multiplication by a matrix over F_2.
..
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Oddly dispersing disease
« Reply #11 on: Nov 21st, 2004, 1:37pm » |
Quote Modify
|
And find the eigenvalues?
|
| « Last Edit: Nov 21st, 2004, 1:38pm by Grimbal » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #12 on: Nov 21st, 2004, 3:54pm » |
Quote Modify
|
on Nov 21st, 2004, 1:37pm, Grimbal wrote:| And find the ........? |
|
The solution I know does not use that concept but..
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Oddly dispersing disease
« Reply #13 on: Nov 27th, 2004, 12:29pm » |
Quote Modify
|
Here is another hint:
Linear Independence.
::
The result in this problem can be used to simplify the proof that the n numbers game (Barukh's extension of the Four Numbers game which Obob posted to this forum) will terminate iff n is a power of 2. The n-numbers game corresponds to a cycle of villages in our problem. In fact, this problem actually came about trying to simplify that proof! I thought it might be interesting (and surprising to some except towr ).
Anyway, here is the solution I had in mind:
We prove the following: If the disease goes away, then it does in no more than N days.
Let n = N.
We can represent a village having a disease by 1 and being disease free by 0. We can represent the state of the villages by an n-vector of 0's and 1's.
Now the process that is going on is equivalent to multiplication of that n-tuple by some matrix T, taking the values over F2.
Thus after k steps, the state of the villages is Tkv where v was the initial state.
So we want to prove that following:
If Tkv = 0 and Tk-1v [ne] 0, for some k, then k [le] n.
To prove this we claim that v, Tv, T2v,...,Tk-1v are all linearly independent. (this would imply k [le] n).
Suppose they are not L.I.
Then [sum]i=0k-1[alpha]iTiv = 0 -- (1)
Let s be the smallest such that [alpha]s [ne] 0.
Multiplying by both sides of (1) by Tk-1-s, we see that Tk-1v = 0, contradiction.
:::
|
| « Last Edit: Nov 27th, 2004, 12:48pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print