April 2020
 

[url]http://www.research.ibm.com/haifa/ponderthis/challenges/April2020.html[/url]

is there someone get 29.16521896% after day 10?
i'm still getting 24.25371788% ._.

[QUOTE=virgo;541518]is there someone get 29.16521896% after day 10?[/QUOTE]
Yes, my calculations match the provided answer for the example graph.

[QUOTE=Xyzzy;541469][url]http://www.research.ibm.com/haifa/ponderthis/challenges/April2020.html[/url][/QUOTE]

HUH?

This problem seems very under-posed! Some questions:

(1) What are the initial conditions? If all are healthy at t=0, then they remain healthy.
(if one is adjacent to 2 rather than 3 people the chance that at t+1 a neighbor will get
sick is lower).
(1a) How MANY are sick at t= 0??? Just one? Do we get to select which one
is sick at t = 0?
(1b) Can a sick person infect more than one adjacent person?

(2) If someone is sick at time t do the people immediately adjacent become sick with equal probability? (assuming the healthy ones have no other sick neighbors)


(3) Is it possible that once infected, someone will heal? If so, how long does it take?
[I assume not, but it needs to be stated]

(4) If sick at t, how is the probability determined that someone adjacent becomes sick
at t+1? Is it constant throughout the 10 days? Is it a necessity that someone adjacent does become sick? i.e. if at time 0 someone is sick and does not infect a neighbor
must another adjacent neighbor become sick?

(4) If someone is sick at time t do the people adjacent become sick with equal probability?

(5) Are the probabilities independent? If someone is healthy and two adjacent people are sick at t,
does one add the probabilities (p1+p2) that the person becomes sick at t+1 or is the probability
1- ( (1-p1)(1-p2))?

I assume the latter. I can see an argument for either if it is possible to get infected by two people at the same time....

Or am I just plain missing the obvious?

[QUOTE=R.D. Silverman;541545]HUH?

This problem seems very under-posed! Some questions:

(1) What are the initial conditions? If all are healthy at t=0, then they remain healthy.
(if one is adjacent to 2 rather than 3 people the chance that at t+1 a neighbor will get
sick is lower).
(1a) How MANY are sick at t= 0??? Just one? Do we get to select which one
is sick at t = 0?
(1b) Can a sick person infect more than one adjacent person?

(2) If someone is sick at time t do the people immediately adjacent become sick with equal probability? (assuming the healthy ones have no other sick neighbors)


(3) Is it possible that once infected, someone will heal? If so, how long does it take?
[I assume not, but it needs to be stated]

(4) If sick at t, how is the probability determined that someone adjacent becomes sick
at t+1? Is it constant throughout the 10 days? Is it a necessity that someone adjacent does become sick? i.e. if at time 0 someone is sick and does not infect a neighbor
must another adjacent neighbor become sick?

(4) If someone is sick at time t do the people adjacent become sick with equal probability?

(5) Are the probabilities independent? If someone is healthy and two adjacent people are sick at t,
does one add the probabilities (p1+p2) that the person becomes sick at t+1 or is the probability
1- ( (1-p1)(1-p2))?

I assume the latter. I can see an argument for either if it is possible to get infected by two people at the same time....

Or am I just plain missing the obvious?[/QUOTE]

Also:

Is it possible to infect more than one person in a time period??

[QUOTE=R.D. Silverman;541545]This problem seems very under-posed! Some questions:[/QUOTE]
I think the initial conditions are the only particularly unclear part. I assumed that the first person (corresponding to the first row of the adjacency matrix) is always the only person infected at start.

For the rest, I think the following is the most obvious natural way to calculate how the set of infected people changes from one day to the next, and does match the probability given for the example:

Given a set of infected people S, find all edges in the graph that connect to an infected person. Color each such edge red with 10% probability. The next set of infected people is people who are either already in S or have a red edge.

If I want to calculate probability of all infected at day t, should I just product all edges infection probability?
If there are only 3 edges and infection probabilities are like (a:0.1, b:0.1, c:0.1)
all edges infected probability @ day t = (0.1)^3 ? or should I also concern all edges infected probability @ day 0 to t-1 ?
its rly confusing

[QUOTE=uau;541557]I think the initial conditions are the only particularly unclear part. I assumed that the first person (corresponding to the first row of the adjacency matrix) is always the only person infected at start.
[/QUOTE]

But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.

An interesting question: Given a graph X. Delete an edge. Prove or disprove that
the resulting graph always has a lower probability.

This seems intuitively true. The resulting graph has two people with no direct contact,
thus lowering the probability for at least those two.

This immediately suggests that the maximal probability graph should be complete.
(every node connected to every other). Now all one need do is check the complete graphs
to size 8.

[QUOTE=R.D. Silverman;541566]But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.

An interesting question: Given a graph X. Delete an edge. Prove or disprove that
the resulting graph always has a lower probability.

This seems intuitively true. The resulting graph has two people with no direct contact,
thus lowering the probability for at least those two.

This immediately suggests that the maximal probability graph should be complete.
(every node connected to every other). Now all one need do is check the complete graphs
to size 8.[/QUOTE]

I think the correct approach to a proof is to model the problem as a stochastic
process/martingale. I wish I could remember the material..... Its been 45 years
since I last looked at/took a course....Can you say "ossification of the intellect"?

[QUOTE=R.D. Silverman;541568]I think the correct approach to a proof is to model the problem as a stochastic
process/martingale. I wish I could remember the material..... Its been 45 years
since I last looked at/took a course....Can you say "ossification of the intellect"?[/QUOTE]

BTW, there is a reason why .70 was selected. (1-1/e) should be familiar to participants
herein.

Another interesting question. Among all graphs, which is maximal? I think I know the answer.

[QUOTE=R.D. Silverman;541566]But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.[/QUOTE]
Well if you assume an unlabeled graph, you could label it arbitrarily. But the adjacency matrix necessarily implies an ordering of the graph nodes. So I interpreted it as: "find an adjacency matrix such that the probability will be close to 70% when doing 10 steps from the state where the node corresponding to the first row is the only infected node".

[QUOTE]This immediately suggests that the maximal probability graph should be complete. (every node connected to every other). Now all one need do is check the complete graphs to size 8.[/QUOTE]I don't quite get the point here? Sure the complete graph has maximal probability. But we're not trying to find maximal probability, we're trying to get close to 70%. So if we find that a size 5 complete graph has probability >70%, now what?