April 2020

[axn]

I haven't figured out how to calculate the probability, but here is a quick simulation to get an estimate:

is_infected()=(random()/2.^31 < 0.1)
edges=[ [1,2], [1,3], [1,4], [2,5], [3,4], [3,5] ];
infection_status=[0,0,0,0,0];
update_status()=my(ns=infection_status); for(e=1, #edges, ed=edges[e]; v1=ed[1]; v2=ed[2]; if(infection_status[v1] && is_infected(), ns[v2]=1); if(infection_status[v2] && is_infected(), ns[v1]=1)); infection_status=ns;
one_run()=infection_status=[1,0,0,0,0]; for(dd=1,10, update_status()); infection_status == [1,1,1,1,1]

tot=0; for(cnt=1,10000, tot += one_run()); tot/10000.

That comes out to appr. 29%

[0scar]

Using the same strategy outlined by uau, I computed the sequence p(1) - p(10) for the given example:

p(1) = 0 (E has distance 2 from A)
p(2) ~= 0.00101080000
p(3) ~= 0.00651474676
p(4) ~= 0.02005269168
p(5) ~= 0.04369891337
p(6) ~= 0.07786862357
p(7) ~= 0.12165906807
p(8) ~= 0.17332760091
p(9) ~= 0.23072945497

and finally p(10) ~= 0.29165218960.

For a complete graph K8:
p(10) ~= 0.886924821322
p(19) ~= 0.999513267682

I built a state transition matrix under the following assumptions:
1) if a node is infected, on next day the disease can pass to each of its healthy neighbours, and such events are independent.
2) a healthy node gets infected if the disease passes to it from at least one of its infected neighbours, and such events are independent too.

About the search space, the estimate 2e8 by LaurV and R.D.Silverman seems huge to me.
There are only 11117 unlabeled connected graphs with 8 nodes (https://oeis.org/A001349), and we can choose the node infected at time 0 in at most 8 distinct ways (less, if the graph has some symmetries).
So, there are less than 1e5 distinct configurations to check, and thousands of equivalent ways to represent the same configuration as an adjacency matrix (no need to check them all).
The hardest part is to efficiently generate the graphs, but complete lists are available online for small n.
By comparison, my dummy enumerating strategy checked about 6e5 cases.

[LaurV]

See my post #13 (the edit for virgo) - you forget the back-spread.
edit: whoops, didn't read all the thread (second page), this reply was not for the last post, but for tgan's post (last on the former page)

[LaurV]

Originally Posted by 0scar

About the search space, the estimate 2e8 by LaurV and R.D.Silverman seems huge to me.
There are only 11117 unlabeled connected graphs with 8 nodes (https://oeis.org/A001349), and we can choose the node infected at time 0 in at most 8 distinct ways (less, if the graph has some symmetries).
So, there are less than 1e5 distinct configurations to check, and thousands of equivalent ways to represent the same configuration as an adjacency matrix (no need to check them all).
The hardest part is to efficiently generate the graphs, but complete lists are available online for small n.
By comparison, my dummy enumerating strategy checked about 6e5 cases.

Well, if you look for the exact number**, then here it is: 72489. But generating all those is tedious, a lot of symmetry tricks to check... I would still prefer to go through all of them, which is straight forward, and compute the probability for each. My goal with 2^28 was not to give and exact number, but to show that the puzzle is easy, comparing with former puzzles where the search space was like 10^50 and you had no chance to solve it by brute force, unless you really could came with an intelligent idea.

Anyhow, 72489 cases to check just makes the puzzle simpler and less interesting

On the way, however, we learned new terminology for graphs (which we didn't know it in English). During the weekend, swmbo had different plans (like cleaning windows, etc) so we didn't really made any progress towards the definitive solution.

-------
**(you won't believe I computed that for 3, 4, and 5, in my head, during about 40 minutes driving home-to-work in the morning, after reading your post; 3 and 4 was kinda easy, but 5 confused me few times, however I could come to the right 21 graphs knowing already the number, from your link, and then 58 non-symmetric nodes; then first thing I did in the office, before even pouring the coffee, was to check the OEIS for "1, 1, 3, 11, 58", haha)

[Dieter]

Wasn‘t sure if it is spoiling

[0scar]

Originally Posted by Dieter

Wasn‘t sure if it is spoiling

If so, I apologise.

Of course, the text of April 2020 problem is ambiguous.
My first goal was to confirm that uau's interpretation of the problem is coherent with the given example.
I restated his explanation from post #6, remarking the somehow implicit assumption that events along distinct edges are independent.
By the way, I hope that someone will double-check my computations.

Previous posts also contain the following hints about how to solve the problem:
R.D.Silverman suggested to model the infection process as a stochastic process / martingale (allowing an exact computation);
axn showed how to estimate the required probability by simulating such process.
Earning an asterisk requires an accuracy to more than four decimal places, implying lengthy simulations.
Whichever approach you prefer, LaurV proposed to repeat it for each of the 2^28 possible adjacency matrices.

But the problem just asks to find a pair connected_graph+starting_node (a "rooted graph"), which can admit up to 7!= 5040 equivalent adjacency matrices.
Not surprisingly, for small order n someone already enumerated all such graphs, sent the result to OEIS, possibly shares the complete lists, and probably wrote a paper about it.
Even without knowing the exact number 72489, we could use the lower bound 2^28/7! ~= 53261 to guess the correct order of magnitude and come to the same conclusion.
Suppose that we actually check 2^28 adjacency matrices, because enumerating them is simpler, and that it takes one week (exaggerating?).
Less than 3 minuts are spent on checking each graph once, sooner or later; the remaining time is spent on checking them over and over again.
Very wasteful.

In my opinion, the most interesting part of the problem is to find some some simple test which allows to quickly discard many subsets of matrices as "duplicates".
I was able to reduce the candidate matrices from 2^28 to 640000, so that the fictional running time is reduced from one week to 24 minutes + preprocessing.
Still wasteful, but good enough for a puzzle.

[R.D. Silverman]

Originally Posted by 0scar

If so, I apologise.

Of course, the text of April 2020 problem is ambiguous.
My first goal was to confirm that uau's interpretation of the problem is coherent with the given example.
I restated his explanation from post #6, remarking the somehow implicit assumption that events along distinct edges are independent.
By the way, I hope that someone will double-check my computations.

Previous posts also contain the following hints about how to solve the problem:
R.D.Silverman suggested to model the infection process as a stochastic process / martingale (allowing an exact computation);
axn showed how to estimate the required probability by simulating such process.
Earning an asterisk requires an accuracy to more than four decimal places, implying lengthy simulations.
Whichever approach you prefer, LaurV proposed to repeat it for each of the 2^28 possible adjacency matrices.

But the problem just asks to find a pair connected_graph+starting_node (a "rooted graph"), which can admit up to 7!= 5040 equivalent adjacency matrices.
Not surprisingly, for small order n someone already enumerated all such graphs, sent the result to OEIS, possibly shares the complete lists, and probably wrote a paper about it.
Even without knowing the exact number 72489, we could use the lower bound 2^28/7! ~= 53261 to guess the correct order of magnitude and come to the same conclusion.
Suppose that we actually check 2^28 adjacency matrices, because enumerating them is simpler, and that it takes one week (exaggerating?).
Less than 3 minuts are spent on checking each graph once, sooner or later; the remaining time is spent on checking them over and over again.
Very wasteful.

In my opinion, the most interesting part of the problem is to find some some simple test which allows to quickly discard many subsets of matrices as "duplicates".
I was able to reduce the candidate matrices from 2^28 to 640000, so that the fictional running time is reduced from one week to 24 minutes + preprocessing.
Still wasteful, but good enough for a puzzle.

One can cut down the search further. If the complete graph on n nodes does not exceed
.70 then one can skip searching the n node graphs. Generating the n+1 node graphs
can/should be made easier because all of the n-node graphs are sub-graphs. (although I
suspect it will take a clever algorithm)

[Kebbaj]

Taking the following assumptions for the example given:

- The infection leaves from city A to other city with 10% of chance.

- The population of A and of all the cities is 10,000. (Which is not sure that all the cities have the same population, it is not precised)

I get with the example of the Excel file attached, that after 10 days all cities are 100% contaminated.
Where does the 29% come from? Something that I am not well understood?

[axn]

You've take a "probability of infection" and misinterpreted it as a "rate of infection"

[Kebbaj]

Originally Posted by axn

You've take a "probability of infection" and misinterpreted it as a "rate of infection"

https://en.wikipedia.org/wiki/Apparent_infection_rate ?

[0scar]

A simple counterexample.
There is a small (but strictly positive) chance that the infection never leaves town A in ten days.
Or in ten months.
Or in ten thousand years.