Question

Two unit squares are selected at random without replacement from an $n \times n$ grid of unit squares. Find the least positive integer $n$ such that the probability that the two selected squares are horizontally or vertically adjacent is less than $\frac{1}{2015}.$

Answer

Answer: 90

Concepts:basic probability counting pairs inequality

Difficulty rating: 2270

Solution:

Each of the $n$ rows contains $n - 1$ horizontally adjacent pairs, so there are $n(n-1)$ horizontal pairs and likewise $n(n-1)$ vertical pairs. Out of $\binom{n^2}{2} = \frac{n^2(n^2-1)}{2}$ equally likely pairs, the probability of adjacency is $\frac{2n(n-1) \cdot 2}{n^2(n^2 - 1)} = \frac{4}{n(n+1)}.$

We need $n(n+1) \gt 4 \cdot 2015 = 8060.$ Since $89 \cdot 90 = 8010$ and $90 \cdot 91 = 8190,$ the least such $n$ is $90.$

2015 AIME II Problem 5

Answer: 90

Difficulty rating: 2270

Solution:

Problem 5 in Other Years