2015 AIME II Problems/Problem 5
Problem
Two unit squares are selected at random without replacement from an grid of unit squares. Find the least positive integer
such that the probability that the two selected unit squares are horizontally or vertically adjacent is less than
.
Solution
Call the given grid "Grid A". Consider Grid B, where the vertices of Grid B fall in the centers of the squares of Grid A; thus, Grid B has dimensions . There is a one-to-one correspondence between the edges of Grid B and the number of adjacent pairs of unit squares in Grid A. The number of edges in Grid b is
, and the number of ways to pick two squares out of grid A is
. So, the probability that the two chosen squares are adjacent is
. We wish to find
such that
, and the first such
is
.