mersenneforum.org April 2020
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

Nov 2003

22·5·373 Posts

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

2020-04-02, 02:43   #13
LaurV
Romulan Interpreter

Jun 2011
Thailand

3×47×67 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2020-04-02, 03:06   #14
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV 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

2020-04-02, 03:09   #15
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by uau Sure the complete graph has maximal probability.
We agree. But I seek a formal proof.

2020-04-02, 03:31   #16
LaurV
Romulan Interpreter

Jun 2011
Thailand

3×47×67 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2020-04-03, 08:38   #17
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by LaurV 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.

 2020-04-03, 10:39 #18 LaurV Romulan Interpreter     Jun 2011 Thailand 3×47×67 Posts 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
2020-04-03, 13:29   #19
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV 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.

2020-04-03, 16:59   #20
virgo

Apr 2020

5 Posts

Quote:
 Originally Posted by uau 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,

2020-04-05, 11:10   #21
LaurV
Romulan Interpreter

Jun 2011
Thailand

3·47·67 Posts

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

Last fiddled with by LaurV on 2020-04-05 at 11:15

2020-04-07, 10:31   #22
tgan

Jul 2015

2·13 Posts
what am i doing wrong?

Quote:
 Originally Posted by virgo 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Soap Box 685 2021-03-03 23:29 gd_barnes Conjectures 'R Us 14 2020-12-30 15:58 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 03:23.

Sat May 15 03:23:27 UTC 2021 up 36 days, 22:04, 0 users, load averages: 2.67, 2.28, 2.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.