Grid: Direction Change
Nick travels from \((0,0)\) to \((8,8)\) by moving one unit right (R) or up (U) at each step. What is the probability that he changes his direction an odd number of times during the entire journey?
Answer
There are \(\binom{16}{8}\) total ways to arrange 8 \(R\)s and 8 \(U\)s in a 16-move path. Let \(X\) be the number of direction changes. A key fact is that \(X\) is odd precisely when the first and last moves differ.
\(\text{Case 1:}\) First move \(R\), last move \(U\). We then have 14 moves in between, with 7 \(R\)s and 7 \(U\)s. There are \(\binom{14}{7}\) such sequences.
\(\text{Case 2:}\) First move \(U\), last move \(R\). By the same reasoning, there are again \(\binom{14}{7}\) sequences.
Hence the number of paths with an odd number of direction changes is
Therefore, the probability is
Notes and comments
Comment 1: A quick intuitive way to see this is to think of listing all permutations of 8 \(R\)s and 8 \(U\)s. Without loss of generality, suppose the first move is \(U\). Then to have a different last move, that last move must be an \(R\). Among the remaining 15 slots, we must place 7 \(R\)s and 7 \(U\)s so that the last slot is \(R\). This effectively gives an 8‐in‐15 chance (because 8 of the 16 total \(R\)s go into that last slot across all arrangements), leading to \(\tfrac{8}{15}\).