Not a Chessboard

Probability Level 5

Calvin fills in a $7\times7$ grid with the numbers $1$ through $49$ in a random arrangement. He then erases his work and does the same thing again, to obtain two different random arrangements of the numbers in the grid. What is the expected number of pairs of numbers that occur in either the same row as each other or the same column as each other in both of the two arrangements?

The answer is 73.5.

1 solution

Alan Yan
Aug 31, 2015

Since expected value is linear, we only need to calculate the expected value of one pair. If we fix the original configuration, we will only look at row pairs and column pairs. In each row or column there are 7 terms. Thus there are $14{7 \choose 2}$ for all of the rows and columns. Let's denote $S$ as the expected value.

For each pair $i = 1, 2, ..., 14{7 \choose 2}$ we define $S_i$ as:

$S_i \stackrel{def}{=} \begin{cases} 1 & \small \text{pair in the same row or column} \\ 0 & \small \text{otherwise} \end{cases}$

Because of the linearity of expected value, we know that

$\mathbb{E}(S) = \mathbb{E}(S_1) + \mathbb{E}(S_2) + ... \mathbb{E}(S_{14{7 \choose 2}})$

It is easy to see that $\mathbb{E}(S_i) = \mathbb{P}(S_i = 1) = \frac{{7 \choose 2}14}{49 \choose 2} = \frac{1}{4}$

Reason for the Probability: There are $14$ ways to choose a row/column for the pair to be on and $7 \choose 2$ ways to choose the place where the pair will occupy. There are a total of $49 \choose 2$ ways to choose the place for the pair. (Notice how even though the terms in the pair are distinguishable, if I count consistently, in this case, consistently indistinguishable, the counting will still be valid )

Now, since expected value is linear, we just have to multiply this probability by the number of pairs which implies that the answer is

$14{7 \choose 2}\cdot \frac{1}{4} = \boxed{\frac{147}{2} = 73.5}$

Sorry, but how is it possible to get more than 49 matches out of 49 trials?

I think the argument goes like this: for any given number to match, we can first pick the first location. Then, there are 13 locations out of 49 for the second number to match. Thus, for each number, there is an added 13/49 expected value, and 13/49*49 = 13.

Anonymous Anonymous - 5 years, 9 months ago

What do you mean? The problem asks for PAIRS not individual numbers as individuals. Thus it is possible to have more than 49.

Another solution is like this.

Each pair of numbers of 49 has a $\frac{14{7 \choose 2}}{49 \choose 2} = \frac{1}{4}$ probability in being in the same row or column in any orientation. This is because you choose a row/column and then choose two squares.

Thus, the probability a pair is on the same row/column in two orientations is $(\frac{1}{4})^2$ . Since there are $49 \choose 2$ pairs, the total expected value is ${49 \choose 2} \cdot (\frac{1}{4})^2 = \boxed{73.5}$

Due to Linearity of Expectation, which states: Given any random variables, $X_1, X_2, ..., X_n$ , we always have

$\mathbb{E}[X_1+X_2+...+X_n] = \mathbb{E}[X_1] + ...+ \mathbb{E}[X_n]$

regardless of dependency,

we can set each variable as a pair of squares, which allows us to kill this problem easily.

Alan Yan - 5 years, 9 months ago

Not a Chessboard

The answer is 73.5.

1 solution

0 pending reports