Non-Adjacent Selection from 1 to 10
You pick 3 numbers uniformly at random from the set $\{1, 2, \ldots, 10\}$ (all $\binom{10}{3}$ subsets equally likely). The catch: the selection is only valid if no two chosen numbers are adjacent -- meaning no two differ by exactly 1.
What is the probability that a random 3-element subset satisfies this non-adjacency condition?
Hints
- Think about the denominator first: how many total 3-element subsets of $\{1, \ldots, 10\}$ are there? Then ask: what structured technique handles constraints on gaps between chosen elements?
- The non-adjacency constraint says the chosen numbers in sorted order must satisfy $a_{i+1} \geq a_i + 2$. Try a substitution $b_i = a_i - (i-1)$ to absorb the gaps and reduce to an unconstrained count.
- After the substitution, the valid selections correspond exactly to unconstrained 3-element subsets of $\{1, \ldots, 8\}$, giving $\binom{8}{3} = 56$ favorable outcomes out of $\binom{10}{3} = 120$ total.
Worked Solution
How to Think About It: This is a counting problem dressed up as probability. The denominator is easy: $\binom{10}{3} = 120$ equally likely subsets. The work is in the numerator -- how many 3-element subsets of $\{1, \ldots, 10\}$ have no two elements differing by 1? The key is recognizing that a non-adjacency constraint on an ordered set is equivalent to a simpler unconstrained counting problem via a classic substitution. Before going formal, sanity check the scale: there are 120 total subsets. Non-adjacency is a meaningful restriction -- you can't pick, say, $\{1, 2, 3\}$ or $\{5, 6, 9\}$ -- so the answer should be noticeably less than 1. A rough guess might be around half, so expect something in the $\frac{1}{2}$ to $\frac{2}{3}$ range.
Quick Estimate: Count directly for small cases to build intuition. For $\{1, \ldots, 5\}$, choose 2 non-adjacent: valid pairs are $\{1,3\}, \{1,4\}, \{1,5\}, \{2,4\}, \{2,5\}, \{3,5\}$ -- that is 6 out of $\binom{5}{2} = 10$, giving $3/5$. The bijection argument (explained below) predicts $\binom{4}{2}/\binom{5}{2} = 6/10$. Checks out. Scaling to our problem, the bijection gives $\binom{8}{3}/\binom{10}{3} = 56/120 = 7/15 \approx 0.467$. Slightly less than half -- makes sense given the restriction bites harder with more elements.
Approach: Use a variable substitution (stars and bars bijection) to reduce the constrained counting problem to an unconstrained one.
Formal Solution:
Let the three chosen numbers in increasing order be $a_1 < a_2 < a_3$. The non-adjacency constraint requires $a_2 \geq a_1 + 2$ and $a_3 \geq a_2 + 2$.
Define new variables: $$b_1 = a_1, \quad b_2 = a_2 - 1, \quad b_3 = a_3 - 2.$$
Then $b_1 < b_2 < b_3$, and since $a_3 \leq 10$, we get $b_3 \leq 8$. So $(b_1, b_2, b_3)$ is an unconstrained 3-element subset of $\{1, 2, \ldots, 8\}$. The map is a bijection, so: $$\text{Number of valid subsets} = \binom{8}{3} = 56.$$
The total number of 3-element subsets is $\binom{10}{3} = 120$.
$$P(\text{no two adjacent}) = \frac{56}{120} = \frac{7}{15}.$$
Answer: $\displaystyle\frac{7}{15} \approx 0.467$.
Intuition
The variable substitution trick here is a workhorse of combinatorics: whenever you have a constraint that elements must be spaced at least $k$ apart, you can shift later variables to eat up the required gaps and reduce to an unconstrained problem on a smaller set. Specifically, choosing $r$ elements from $\{1, \ldots, n\}$ with no two adjacent is equivalent to choosing $r$ elements from $\{1, \ldots, n - r + 1\}$ freely, giving $\binom{n-r+1}{r}$ valid subsets. This formula comes up all the time in probability and combinatorics -- from occupancy problems to barrier-crossing arguments.
In a quant interview, the broader lesson is that hard-looking counting problems often collapse once you find the right bijection or encoding. The instinct to ask 'can I reparametrize the constraint away?' is the same instinct you use in derivatives (change of numeraire) and probability (change of measure). Spotting the bijection quickly, rather than grinding through inclusion-exclusion case-by-case, is what distinguishes a clean, confident answer from a messy one.