Random Walk on a Telephone Pad: Divisibility by 2
Consider a standard telephone number pad arranged as:
``` 1 2 3 4 5 6 7 8 9 ```
You press a random digit (uniformly from 1-9), write it down, then move to a uniformly random orthogonally adjacent digit (up, down, left, or right -- no diagonals), write that down, then move again to a random adjacent digit and write it down. The three digits form a 3-digit number (e.g., if you press 5, then 6, then 9, the number is 569).
What is the probability that this 3-digit number is divisible by 2?
Hints
- Divisibility by 2 depends only on the last digit. Focus on whether $d_3$ is even.
- Check the adjacency structure of the 3x3 grid. What do you notice about the parity of each digit and its neighbors?
- The grid is bipartite: odd digits only neighbor even digits and vice versa. So parity alternates at each step, and $d_3$ has the same parity as $d_1$. Count the even starting digits: $\{2, 4, 6, 8\}$, giving probability $4/9$.
Worked Solution
How to Think About It: A number is divisible by 2 iff its last digit is even. So we need $P(d_3 \text{ is even})$, where $d_3$ is the third digit in the random walk. The pad has a beautiful structure: lay out the digits and check their adjacencies. Odd digits $\{1, 3, 5, 7, 9\}$ only connect to even digits $\{2, 4, 6, 8\}$, and vice versa. The graph is bipartite! This means the parity of the digit alternates with every step.
Quick Estimate: Since the grid is bipartite (odd connects only to even and vice versa), the parity of $d_3$ equals the parity of $d_1$. There are 5 odd digits and 4 even digits among $\{1, \dots, 9\}$, so $P(d_1 \text{ even}) = 4/9$ and $P(d_1 \text{ odd}) = 5/9$. Since odd $\to$ even $\to$ odd and even $\to$ odd $\to$ even, we get $P(d_3 \text{ even}) = P(d_1 \text{ even}) = 4/9$.
Approach: Exploit the bipartite structure of the adjacency graph on the telephone pad.
Formal Solution:
First, write out the adjacency list for orthogonal neighbors:
| Digit | Neighbors | Parity | Neighbor parity | |-------|-----------|--------|-----------------| | 1 | 2, 4 | odd | all even | | 2 | 1, 3, 5 | even | all odd | | 3 | 2, 6 | odd | all even | | 4 | 1, 5, 7 | even | all odd | | 5 | 2, 4, 6, 8 | odd | all even | | 6 | 3, 5, 9 | even | all odd | | 7 | 4, 8 | odd | all even | | 8 | 5, 7, 9 | even | all odd | | 9 | 6, 8 | odd | all even |
The adjacency graph is bipartite: every odd digit has only even neighbors, and every even digit has only odd neighbors. This means the parity alternates deterministically at each step:
- $d_1$ odd $\Rightarrow$ $d_2$ even $\Rightarrow$ $d_3$ odd
- $d_1$ even $\Rightarrow$ $d_2$ odd $\Rightarrow$ $d_3$ even
So $d_3$ is even if and only if $d_1$ is even. Since $d_1$ is chosen uniformly from $\{1, 2, \dots, 9\}$:
$$P(d_3 \text{ even}) = P(d_1 \text{ even}) = P(d_1 \in \{2, 4, 6, 8\}) = \frac{4}{9}$$
Answer: The probability that the 3-digit number is divisible by 2 is $\boxed{\dfrac{4}{9}} \approx 0.444$.
Intuition
The beautiful insight here is that the 3x3 telephone grid is a bipartite graph when you look at parity. Think of it like a checkerboard: color odd positions white and even positions black, and every orthogonal move flips the color. This means that after an even number of steps, you return to the same parity as your start, and after an odd number of steps, you flip. Since we take 2 steps (from $d_1$ to $d_3$), the parity of $d_3$ matches $d_1$.
This bipartite structure shows up in many grid-walk problems and Markov chain questions. Recognizing graph bipartiteness can instantly collapse a complicated enumeration into a simple counting argument. In interviews, checking the structure of the state space before diving into computation is almost always the right move.