Ponder This Challenge - January 2018 - Fake news spread

Alice heard a rumor. She meets Bob after ab days, where ab is uniformly distributed over the integers from 1 to AB. She meets Charlie after ac days (again, uniformly distributed over [1,AC]), and Dave after ad days. Bob meets Charlie after bc days, and Dave after bd days. Charlie meets Dave after cd days.
In every such meeting, if one of the attendees knows the rumor - he/she tells it to the other one.
Find AB, AC, AD, BC, BD, and CD such that the average time of the rumor to get to Dave is exactly 425.36/69.

Solution

• Click here to view the solution

  The solution we designed was [AB,AC,AD,BC,BD,CD] = [23,1,20,19,15,14] ("WATSON").
  There are many similar answers - Bert Dobbelaere gave us a different answer [1,1,16,1,15,8625], and Ozgur Sumer's solution (thanks!) is:

  *I arrived at this solution by a brute-force algorithm with a lot of branch pruning using mathematical insights. The mathematical insights are as follows 3450 | AB*AC*BC*AC*CD*AD. This is because the expectation calculation will have the AB*...*AD term as denominator with an integer numerator, and to get an integer numerator, the denominator must be divisible by 69 * 50 = 3450. AD > 12 ==> otherwise the expectation <= 425.36/69 due to AD.
  Without loss of generality, we can assume AB >= max(AC, BD, CD). This is because the problem is identical if A is swapped with D, or B is swapped with D.
  AB >= 6, otherwise the path AB + BD < 10 brings the expectation <= 426.36/69. Note that AB >= BD is based on the previous assumption.
  min(AB, AC, AD) <= 20, otherwise the expectation goes above the target. Just to get to anywhere from A is too costly in this case.
  Once you fix five edges, the expectation value is monotone on the remaining edge.
  While writing a program, we need to calculate the expectation accurately with 6 for loops, and this may be costly. So we have a Monte Carlo approximation along with an accurate computation.

  When we try we will write conditions to reflect the insights I put above. Here the last insight is actually implying that the final loop can be a binary search.*

Solvers

• Alper Halbutogullari (30/12/17 09:07 AM IDT)
• Mathias Schenker (31/12/17 02:26 PM IDT)
• Shirish Chinchalkar (01/01/18 11:43 PM IDT)
• Hugo Pfoertner (02/01/18 04:55 PM IDT)
• Lorenz Reichel (03/01/18 07:55 AM IDT)
• Muralidhar Seshadri (03/01/18 06:22 PM IDT)
• Bert Dobbelaere (03/01/18 09:28 PM IDT)
• Tom Sirgedas (04/01/18 12:38 AM IDT)
• Kang Jin Cho (04/01/18 12:20 PM IDT)
• Dieter Beckerle (05/01/18 12:51 AM IDT)
• David Greer (05/01/18 08:53 PM IDT)
• Paolo Farinelli (06/01/18 12:24 AM IDT)
• JJ Rabeyrin (07/01/18 02:26 AM IDT)
• Joaquim Neves Carrapa (07/01/18 09:31 AM IDT)
• Francis Golding (08/01/18 11:37 PM IDT)
• Tyler Mullen (09/01/18 09:37 PM IDT)
• Dmitry Serbin (12/01/18 02:42 PM IDT)
• Balakrishnan Varadarajan (16/01/18 06:52 AM IDT)
• Guillaume Escamocher (17/01/18 01:18 PM IDT)
• Ozgur Sumer (19/01/18 03:16 AM IDT)
• Guangzhong Sun (19/01/18 05:38 PM IDT)
• Steven Langerwerf (26/01/18 02:14 PM IDT)
• David F.H. Dunkley (28/01/18 03:19 AM IDT)
• Nyles Heise (28/01/18 04:34 AM IDT)
• Erik Wünstel (28/01/18 11:23 PM IDT)
• Li Li (31/01/18 10:19 AM IDT)
• Mykola Zubach (31/01/18 03:17 PM IDT)
• Oscar Volpatti (31/01/18 03:29 PM IDT)
• Andreas Stiller (31/01/18 06:30 PM IDT)