mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-04-07, 11:58   #23
axn
 
axn's Avatar
 
Jun 2003

22·52·47 Posts
Default

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%
axn is online now   Reply With Quote
Old 2020-04-08, 03:55   #24
0scar
 
Jan 2020

C16 Posts
Default

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
0scar is offline   Reply With Quote
Old 2020-04-08, 04:01   #25
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19·461 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2020-04-08, 04:55   #26
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19×461 Posts
Default

Quote:
Originally Posted by 0scar View Post
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
LaurV is offline   Reply With Quote
Old 2020-04-08, 17:19   #27
Dieter
 
Oct 2017

89 Posts
Default

Wasn‘t sure if it is spoiling

Last fiddled with by Dieter on 2020-04-08 at 17:44 Reason: Spoiling.
Dieter is offline   Reply With Quote
Old 2020-04-10, 08:06   #28
0scar
 
Jan 2020

C16 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
0scar is offline   Reply With Quote
Old 2020-04-10, 12:14   #29
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by 0scar View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2020-04-11, 20:59   #30
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5·11 Posts
Unhappy

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
File Type: zip April 2020.zip (18.0 KB, 29 views)
Kebbaj is offline   Reply With Quote
Old 2020-04-12, 02:43   #31
axn
 
axn's Avatar
 
Jun 2003

22×52×47 Posts
Default

You've take a "probability of infection" and misinterpreted it as a "rate of infection"
axn is online now   Reply With Quote
Old 2020-04-12, 16:21   #32
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5510 Posts
Default

Quote:
Originally Posted by axn View Post
You've take a "probability of infection" and misinterpreted it as a "rate of infection"
https://en.wikipedia.org/wiki/Apparent_infection_rate ?
Kebbaj is offline   Reply With Quote
Old 2020-04-12, 17:09   #33
0scar
 
Jan 2020

22×3 Posts
Default

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.
0scar is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
2020 project goals gd_barnes Conjectures 'R Us 4 2020-09-23 08:59
U.S. Electile Dysentery 2020 ewmayer Soap Box 308 2020-09-14 23:50
March 2020 what Puzzles 1 2020-04-24 05:46
February 2020 what Puzzles 20 2020-03-04 07:55
January 2020 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.