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

        riddles >> putnam exam (pure math) >> Oddly dispersing disease
        
(Message started by: Aryabhatta on Nov 15th, 2004, 2:10pm)
Title: Oddly dispersing disease
Post by Aryabhatta on Nov 15th, 2004, 2:10pm
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]
Title: Re: Oddly dispersing disease
Post by Icarus on Nov 15th, 2004, 8:59pm
;)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.]
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 15th, 2004, 9:53pm

on 11/15/04 at 20:59:59, 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.
Title: Re: Oddly dispersing disease
Post by John_Gaughan on Nov 16th, 2004, 6:11am
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.
Title: Re: Oddly dispersing disease
Post by Icarus on Nov 16th, 2004, 3:08pm
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).
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 16th, 2004, 3:24pm

on 11/16/04 at 15:08:09, 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...

:-[ :-[ :-[  :-[ :-[
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 17th, 2004, 1:23pm
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... :-/
Title: Re: Oddly dispersing disease
Post by towr on Nov 17th, 2004, 2:13pm

on 11/17/04 at 13:23:47, 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.
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 17th, 2004, 3:38pm

on 11/17/04 at 14:13:55, towr wrote:
Anyway, it's interesting enough, but I'm not any good with graphs.


hint:
[hide]
You don't need any graph theory to solve this. It if were, it probably would have been in the CS section.
[/hide]
::
Title: Re: Oddly dispersing disease
Post by Icarus on Nov 17th, 2004, 6:47pm
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).
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 21st, 2004, 1:02pm
Here is a hint.
[hide]

What goes on can be written as multiplication by a matrix over F_2.

[/hide]
..
Title: Re: Oddly dispersing disease
Post by Grimbal on Nov 21st, 2004, 1:37pm
[hide]And find the eigenvalues?  ;)[/hide]
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 21st, 2004, 3:54pm

on 11/21/04 at 13:37:36, Grimbal wrote:
[hide]And find the ........?  ;)[/hide]


;D

The solution I know does not use that concept but..
Title: Re: Oddly dispersing disease
Post by Aryabhatta on Nov 27th, 2004, 12:29pm
Here is another hint:
[hide]
Linear Independence.
[/hide]
::

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1099273123) 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:

[hide]
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.
[/hide]
:::


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