2012 AMC 10A Problem 25

Setting up. Think of $(x, y, z)$ as a random point in a cube with side $n$. The probability is the volume of the "good" part divided by the whole volume $n^3$.

1. Sort first. The six orders ($x$ smallest, $y$ smallest, and so on) are equally likely and give the same shape of good region. So look only at the order $x < y < z$. That piece of the cube has volume $\frac{n^3}{6}$.
2. The condition, once sorted. With $x < y < z$, "no two within $1$" means $y$ is at least $1$ more than $x$, and $z$ is at least $1$ more than $y$. Then $z$ is automatically at least $2$ more than $x$.
3. Remove the gaps. Try a concrete case with $n = 10$: the good triple $x = 2$, $y = 5$, $z = 9$. Slide $y$ down by $1$ and $z$ down by $2$ to get $2, 4, 7$. These are still in order, and all lie between $0$ and $8$.
In general, set $X = x$, $Y = y - 1$, $Z = z - 2$. The conditions $y \ge x + 1$ and $z \ge y + 1$ become just $X \le Y \le Z$. And since $z \le n$, we get $Z \le n - 2$. So the good sorted triples match up exactly with sorted triples in $[0, n - 2]$.
4. Volume. Sliding does not change volume. Sorted triples in $[0, n-2]$ fill $\frac{(n-2)^3}{6}$ of volume. So
$$\text{probability} = \frac{(n-2)^3 / 6}{n^3 / 6} = \left(\frac{n-2}{n}\right)^3.$$
5. Find the smallest $n$. The fraction grows as $n$ grows, so test the choices from the smallest:
- $n = 9$: $\left(\frac79\right)^3 = \frac{343}{729}$, and $343$ is less than half of $729$. Too small.
- $n = 10$: $\left(\frac{8}{10}\right)^3 = \frac{512}{1000}$, which is more than $\frac12$.

The answer is $\boxed{\textbf{(D)}\ 10}$.

"No two within $1$" is the smooth version of choosing numbers with gaps. Sort them, slide each one back by the gaps in front of it, and the condition disappears. Sorting costs a factor of $6$ on both top and bottom, which cancels, and sliding does not change volume. The same trick works for any number of values and any gap size.

Check the method with two numbers, where you can draw the picture. For $x, y$ in $[0, n]$, the sliding trick predicts $\left(\frac{n-1}{n}\right)^2$. In the $n$ by $n$ square, the bad points form a strip along the diagonal where $x$ and $y$ are less than $1$ apart. The good points form two right triangles with legs $n - 1$, with total area $(n-1)^2$. So the probability really is $\frac{(n-1)^2}{n^2}$, as the trick predicts.