Competition problem — Combinatorics

Combinatorics Difficulty 4.7 AIME Find the answer United States

Problem:

Paul fills in a $7 \times 7$ 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?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Each of the $\binom{49}{2}$ pairs of numbers has a probability of $\frac{14 \cdot \binom{7}{2}}{\binom{49}{2}} = 1/4$ of being in the same row or column in one of the arrangements, so the expected number that are in the same row or column in both arrangements is
$\binom{49}{2} \cdot (1/4)^2 = \frac{147}{2}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.