Probability advantage on order dependency puzzle

61 Views Asked by At

I stumbled across this problem on the NSA website, and I am having trouble grappling with the solution. I would expect that the probabilities for each would be equal, as each square would have an equal probability of containing an egg, and the two paths share a graph isomorphism with equal weights from one point to the next. What am I missing here, or was there a mistake on their website? And if they are wrong, what was their mistake?

(sidenote)

I made a quick and dirty python script to test the result empirically and it seems about 50/50. Here is the script if you are interested.

    from numpy import random

def testVerticalPoints(): 
    locationOne = random.randint(1, 12)
    locationTwo = random.randint(1, 12)
    while (locationTwo == locationOne):
        locationTwo = random.randint(1, 12)

    points = 0
    for elem1 in range(1, 5): 
        for elem2 in range(3): 
            current = elem1 + elem2 * 4
            if (current == locationOne or current == locationTwo):
                points += 1
                return points
            else:
                points += 1

def testHorizPoints():  
    locationOne = random.randint(1, 12)
    locationTwo = random.randint(1, 12)
    while (locationTwo == locationOne):
        locationTwo = random.randint(1, 12)

    points = 0
    for elem in range(1, 13):
        if (locationOne == elem or locationTwo == elem): 
            points += 1
            return points
        else: 
            points += 1

score = 0

for i in range(1000000): 
    vert = testVerticalPoints()
    horiz = testHorizPoints()
    if (vert < horiz):
        score += 1
    elif (vert > horiz): 
        score -= 1
    if (i % 100 == 0):
        print(i)
print(score)

TIA.

2

There are 2 best solutions below

3
On BEST ANSWER

I had the same intuition as you do that the probabilities should be equal by symmetry. This is not the case, however. You can perhaps see this most easily if you consider the case of three boxes with one egg, with Alice visiting the boxes in the order $1,2,3$ and Bob visiting them in the order $2,3,1$.

0
On

The system isn't symmetrical because you are using two different measures for the distances to the same cartons.

$$\begin{array}{|l|l|} \hline A(1, 1)_= & B(2, 4)_< & C(3, 7)_< & D(4, 10)_< \\ \hline E(5, 2)_> & F(6, 5)_> & G(7, 8)_< & H(8, 11)_< \\ \hline I(9, 3)_> & J(10, 6)_> & K(11, 9)_> & L(12, 12)_= \\ \hline\end{array}$$

Your program appears to move the eggs each time the distances are measured. You need to pick two eggs, and for the same eggs determine the smallest value for Alice and Bob.

Eg: Alice(J, G) would return 7 while Bob(J, G) would return 6, making Bob the winner of that pair.