HMMT-Feb 2015 guts, Problem 5

Let $\mathcal{H}$ be the unit hypercube of dimension 4 with a vertex at $(x, y, z, w)$ for each choice of $x, y, z, w \in$ $\{0,1\}$. (Note that $\mathcal{H}$ has $2^{4}=16$ vertices.) A bug starts at the vertex $(0,0,0,0)$. In how many ways can the bug move to $(1,1,1,1)$ (the opposite corner of $\mathcal{H}$ ) by taking exactly 4 steps along the edges of $\mathcal{H}$ ?

Solution: You may think of this as sequentially adding 1 to each coordinate of $(0,0,0,0)$. There are 4 ways to choose the first coordinate, 3 ways to choose the second, and 2 ways to choose the third. The product is 24 . $\fbox{24}$.

Answer: 24