Discrete Expected Value

Probability Level pending

Sixteen dots are arranged in a $4 \times 4$ grid. The distance between any two dots in the grid defined to be the minimum number of horizontal and vertical steps along the grid lines it takes to get from one dot to the other. For example, two adjacent dots are a distance $1$ apart, and two dots at opposite corners of the grid are a distance $6$ apart. The mean distance between two distinct dots in the grid is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

The answer is 11.

1 solution

Piotr Idzik
May 14, 2020

This looks interesting in the context of the problem. Below is my brute-force approach:

"""
solution of:
    https://brilliant.org/problems/discrete-expected-value/
"""
import itertools
import fractions
def get_dist(pos_a, pos_b):
    """
    returns the distance between two given cells on a grid
    """
    assert len(pos_a) == len(pos_b)
    return sum((abs(pos_a[_]-pos_b[_]) for _ in range(len(pos_a))))

def get_mean_dist(grid_width, grid_height):
    """
    returns the mean distance between pairs of distinct cells
    in a grid of the size grid_width*grid_height
    """
    number_of_cells = grid_width*grid_height
    pos_gen = itertools.product(range(grid_width), range(grid_height))
    point_pair_gen = itertools.combinations(pos_gen, 2)
    total_dist = sum((get_dist(pos_a, pos_b) for (pos_a, pos_b) in point_pair_gen))
    return fractions.Fraction(total_dist, number_of_cells*(number_of_cells-1)//2)

RES = get_mean_dist(4, 4)
print(f"Solution: {RES.numerator+RES.denominator}")

I'm coming up with the mean distance as 5/2 units, so that the answer would be 7. I'm not sure why I'm incorrect - any comments would be appreciated. My logic is as follows.

Because of symmetry, there are really only three distinct cases A, B, or C based on the following diagram:

A B B A

B C C B

A B B A

(For example, any point labeled "B" can be made into another point labeled "B" by rotating or inverting the board).

If we pick a point a random, we have a 1/4 chance of picking an "A". The following table shows the number of steps from a point A to another point on the board:

0 1 2 3

1 2 3 4

2 3 4 5

3 4 5 6

The sum of all of these numbers is 48. We have a 1/16 chance of picking a second point at random, so that the expected value of the number of steps given that we've chosen an "A" is 48/16.

By similar logic, we have a 1/2 chance of choosing a "B". A calculation shows that, given that we we have chosen a "B", the mean number of steps is 40/16.

Lastly, we have a 1/4 chance of choosing "C". Similarly, given that we have chosen "C", we have a 32/16 expected number of steps.

Therefore, the expected number of steps should be (1/4) (48/16) + (1/2) (40/16) + (1/4)*(32/16) = 5/2.

Any comments as to the flaw in my reasoning would be appreciated. Thanks in advance

Ron Gallagher - 1 year ago

I think, that the problem is the following. In this puzzle, we were asked about the mean distance between the distinct dots, so in the second part of each step, you schould take $\frac{1}{15}$ instead of $\frac{1}{16}$ . Then the result is $\frac{8}{3}$ , which gives $11$ .

Piotr Idzik - 1 year ago

Good point. Thank you, Piotr.

Ron Gallagher - 1 year ago

Discrete Expected Value

The answer is 11.

1 solution

0 pending reports