mersenneforum.org April 2020
 Register FAQ Search Today's Posts Mark Forums Read

 2020-04-07, 11:58 #23 axn     Jun 2003 22·52·47 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. That comes out to appr. 29%
 2020-04-08, 03:55 #24 0scar   Jan 2020 C16 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 2020-04-08 at 03:56
 2020-04-08, 04:01 #25 LaurV Romulan Interpreter     Jun 2011 Thailand 19·461 Posts 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) Last fiddled with by LaurV on 2020-04-08 at 04:06
2020-04-08, 04:55   #26
LaurV
Romulan Interpreter

Jun 2011
Thailand

19×461 Posts

Quote:
 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)

Last fiddled with by LaurV on 2020-04-08 at 05:06

 2020-04-08, 17:19 #27 Dieter   Oct 2017 89 Posts Wasn‘t sure if it is spoiling Last fiddled with by Dieter on 2020-04-08 at 17:44 Reason: Spoiling.
2020-04-10, 08:06   #28
0scar

Jan 2020

C16 Posts

Quote:
 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.

2020-04-10, 12:14   #29
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 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)

2020-04-11, 20:59   #30
Kebbaj

"Kebbaj Reda"
May 2018
Casablanca, Morocco

5·11 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?
Attached Files
 April 2020.zip (18.0 KB, 29 views)

 2020-04-12, 02:43 #31 axn     Jun 2003 22×52×47 Posts You've take a "probability of infection" and misinterpreted it as a "rate of infection"
2020-04-12, 16:21   #32
Kebbaj

"Kebbaj Reda"
May 2018
Casablanca, Morocco

5510 Posts

Quote:
 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 ?

 2020-04-12, 17:09 #33 0scar   Jan 2020 22×3 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 4 2020-09-23 08:59 ewmayer Soap Box 308 2020-09-14 23:50 what Puzzles 1 2020-04-24 05:46 what Puzzles 20 2020-03-04 07:55 what Puzzles 21 2020-02-02 14:11

All times are UTC. The time now is 16:28.

Wed Sep 30 16:28:13 UTC 2020 up 20 days, 13:39, 0 users, load averages: 1.63, 1.76, 1.80