mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-04-02, 02:29   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by uau View Post
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".

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?
Thank you. I misread the problem as ">= 70.00%".
R.D. Silverman is offline   Reply With Quote
Old 2020-04-02, 02:43   #13
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19·461 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.
Right. So? (how does this change the puzzle? It does not)
The puzzle is well formulated. I also get their number for the example, with a little Excel calculation.

(edit: @virgo: you forgot the possibility of reverse infection, for example, B can also be infected by E, not only by A, assume he is lucky for 7 days, and meantime E gets the disease, by A-D-E or even A-C-D-E route, then B gets it in the eighth day, from E).

OTOH, the problem seems quite easy by brute force, 8 vertices, there are \(C_8^2=28\) possible edges, the matrix in fact is triangular (symmetric on the first diagonal, which is zero always), so there are just 28 bits of entropy, the search space is 2^28, less than a billion possible cases. This should be an extremely easy, few hours, pari "struggle" to calculate all probabilities and sort them in a list.

(I didn't solve it yet, no time, but one idea would be to check if the probability of complete graph \(K_8\) is higher than 70%, first, to be sure there IS a solution. Then, start cutting edges in some fashion).

Last fiddled with by LaurV on 2020-04-02 at 03:05
LaurV is offline   Reply With Quote
Old 2020-04-02, 03:06   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
Right. So? (how does this change the puzzle? It does not)
The puzzle is well formulated. I also get their number for the example, with a little Excel calculation.

OTOH, the problem is quite easy by brute force, 8 vertices, there are \(C_8^2=28\) possible edges, the matrix in fact is triangular (symmetric on the first diagonal, which is zero always), so there are just 28 bits of entropy,).
Actually it is much less, because we are only need consider labelled connected graphs.
There are less than 2000000 such with 8 nodes. See http://oeis.org/A001187
R.D. Silverman is offline   Reply With Quote
Old 2020-04-02, 03:09   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by uau View Post

<snip>

Sure the complete graph has maximal probability.
We agree. But I seek a formal proof.
R.D. Silverman is offline   Reply With Quote
Old 2020-04-02, 03:31   #16
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

210678 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Actually it is much less, because we are only need consider labelled connected graphs.
There are less than 2000000 such with 8 nodes. See http://oeis.org/A001187
You re totally right about connected graphs. However I was talking about "brute force" and I didn't actually think to a way to enumerate connected graphs without generating all of them and check which is connected and which not. That is why I was talking about starting from the complete graph. With a clever way to generate only the connected graphs, the puzzle is even simpler. But not by much. The number is still in 200M, not 2^28, but also not 2M. I guess you typo-ed, or didn't see that the sequence on OEIS is zero-indexed (yes, there are 4 labeled connected graphs with 3 nodes, see here). For comparison, there are 251'548'592 to test, versus 2^28=268'435'456. Non-connected graphs are very few here. Of course, you still may eliminate the symmetries, but checking for such, will be slower than generating all 2^28 graphs.

Last fiddled with by LaurV on 2020-04-02 at 04:09
LaurV is offline   Reply With Quote
Old 2020-04-03, 08:38   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by LaurV View Post
Right. So? (how does this change the puzzle? It does not)
.
Consider the following graph:

A-----B-------C

vs.

B-----A------C

If the infected person is A he/she can infect two people on the first iteration in the second
graph, but not the first.
R.D. Silverman is offline   Reply With Quote
Old 2020-04-03, 10:39   #18
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100010001101112 Posts
Default

This is not what you initially said. I learned from you, to read it as it is, and not to interpret it. The two examples are the same, if I can label arbitrary the A node. Yes, the labeling is arbitrary. I always put A in the middle. Think about it. Arbitrary labeling means that, given a graph, I can label it the way I want. For 3 nodes, you have 4 cases (of connected, labeled graphs), but 2 are symmetric (A--C--B and A--B--C give the same probability), so you have to test 3 of them for probability, assuming you have a fast way to detect the symmetry. If not, you must test all 4. (Now, if you read the continuation of the discussion in the thread, you can see it was just nitpicking (or, better said, picking on you )).

Anyhow, this problem is extremely easy, once you come with the conditioned probability formula (which is actually the hardest part). Then, one way or the other, you have about 2-3 hundred millions cases to test. You can make a nice sorted list, in full, in memory, and pick the closest to 70 for the answer, but also provide the "full solution" to amaze the puzzle makers

Edit: I have some vague idea about how I will spend my weekend tomorrow

Last fiddled with by LaurV on 2020-04-03 at 10:57
LaurV is offline   Reply With Quote
Old 2020-04-03, 13:29   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by LaurV View Post
This is not what you initially said. I learned from you, to read it as it is, and not to interpret it. The two examples are the same, if I can label arbitrary the A node. Yes, the labeling is arbitrary. I always put A in the middle.
The issue is not the labeling. It is assumed that A is the person infected at t=0.
The question is where A is placed on the graph.



Quote:
Anyhow, this problem is extremely easy, once you come with the conditioned probability formula (which is actually the hardest part).
I disagree. I think this is the easy part.
R.D. Silverman is offline   Reply With Quote
Old 2020-04-03, 16:59   #20
virgo
 
Apr 2020

410 Posts
Default

Quote:
Originally Posted by uau View Post
Yes, my calculations match the provided answer for the example graph.
can you give me probabilities after day 1~9?
I think its about how to calculate complementary event, but I still get wrong numbers
thanks,
virgo is offline   Reply With Quote
Old 2020-04-05, 11:10   #21
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19·461 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I disagree. I think this is the easy part.
Maybe for you...


Last fiddled with by LaurV on 2020-04-05 at 11:15
LaurV is offline   Reply With Quote
Old 2020-04-07, 10:31   #22
tgan
 
Jul 2015

2×7 Posts
Default what am i doing wrong?

Quote:
Originally Posted by virgo View Post
can you give me probabilities after day 1~9?
I think its about how to calculate complementary event, but I still get wrong numbers
thanks,
I am also having the same results 24.xxx and not 29.xxx
https://mersenneforum.org/images/smi...tra/picard.png
tgan 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 15:37.

Wed Sep 30 15:37:21 UTC 2020 up 20 days, 12:48, 0 users, load averages: 1.45, 1.61, 1.67

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.