20200407, 11:58  #23 
Jun 2003
2·5^{2}·97 Posts 
I haven't figured out how to calculate the probability, but here is a quick simulation to get an estimate:
Code:
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. 
20200408, 03:55  #24 
Jan 2020
1C_{16} Posts 
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. Last fiddled with by 0scar on 20200408 at 03:56 
20200408, 04:01  #25 
Romulan Interpreter
Jun 2011
Thailand
10001111010000_{2} Posts 
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) Last fiddled with by LaurV on 20200408 at 04:06 
20200408, 04:55  #26  
Romulan Interpreter
Jun 2011
Thailand
2^{4}·3·191 Posts 
Quote:
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 hometowork 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 nonsymmetric 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) Last fiddled with by LaurV on 20200408 at 05:06 

20200408, 17:19  #27 
Oct 2017
101 Posts 
Wasn‘t sure if it is spoiling
Last fiddled with by Dieter on 20200408 at 17:44 Reason: Spoiling. 
20200410, 08:06  #28 
Jan 2020
2^{2}×7 Posts 
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 doublecheck 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. 
20200410, 12:14  #29  
Nov 2003
2^{2}×5×373 Posts 
Quote:
.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 nnode graphs are subgraphs. (although I suspect it will take a clever algorithm) 

20200411, 20:59  #30 
"Kebbaj Reda"
May 2018
Casablanca, Morocco
2·31 Posts 
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? 
20200412, 02:43  #31 
Jun 2003
2·5^{2}·97 Posts 
You've take a "probability of infection" and misinterpreted it as a "rate of infection"

20200412, 16:21  #32  
"Kebbaj Reda"
May 2018
Casablanca, Morocco
111110_{2} Posts 
Quote:


20200412, 17:09  #33 
Jan 2020
2^{2}×7 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
U.S. Electile Dementia paralytica 2020  ewmayer  Soap Box  667  20210112 13:27 
2020 project goals  gd_barnes  Conjectures 'R Us  14  20201230 15:58 
March 2020  what  Puzzles  1  20200424 05:46 
February 2020  what  Puzzles  20  20200304 07:55 
January 2020  what  Puzzles  21  20200202 14:11 