Problem: (Putnam) Let $a_1, a_2, \ldots, a_{3 k+1}$ be an arrangement of the numbers $1,2, \ldots, 3 k+1$. Let $ s_i=a_1+a_2+\cdots+a_i $ for $1 \leq i \leq 3 k+1$. How many arrangements have the property that none of the $s_i$ are divisible by 3? Solution: We ask the highly logical question: when is it the case that $3 \mid s_{i}$ for an arrangement $a_1, a_2, \ldots, a_{3 k+1}$? If $3 \mid a_{1}$, this is certainly a case where $3 \mid s_{i}$ for some $i$ ($i = 1$). Otherwise, if $3 \nmid s_{i}$ for all $i \in \{ 1,2,\dots,k \}$ then we can also have a violation if $s_{k} + a_{k+1} \equiv 0 \pmod 3$ as $s_{k+1} = s_{k} + a_{k+1}$. So, we learn that if none of the $s_{i}$ are divisible by $3$ then $a_{1} \not\equiv 0 \pmod 3$, and as long as $s_{i}$ is not divisible by $3$, we conclude that $s_{i+1} = s_{i} + a_{i+1}$ is not divisible by $3$ only when $s_{i} + a_{i+1} \not\equiv 0 \pmod 3$. Let $\alpha$ denote the sequence of length $3k+1$ where $\alpha_{i}$ is the remainder $a_{i}$ taken modulo $3$. At this point, notice that there are $k+1$ $1s in $\alpha$ and $k$ $0$s and $2$s in $\alpha$. Notice that at any point, if $\alpha_{i} = 0$ then it doesn't impact what $\alpha_{i+1}$ should be. So, we consider the placement of the $1$s and the $2$s. Suppose the first nonzero entry in $\alpha$ is $2$. Then, the next nonzero entry in $\alpha$ must also be $2$. Then, the next must be $1$, and the next must be $2$, and the next must be $1$, and the pattern repeats. But there would be a time when we run out of $2$s leading to two consecutive $1$s which is a violation (this would yield some $s_{j}$ divisible by $3$). So, $\alpha_{1} = 1$ and then the nonzero entries in $\alpha$ after this must be $1$ and then $2$ repeating. So, we conclude that an arrangement $a_1, a_2, \ldots, a_{3 k+1}$ is only valid when $\alpha = 1[0]1[0]2[0]1[0] \dots 1[0]2[0]$ where each $[0]$ denotes a potentially non-empty block of $0$s. There are $2k+1$ blocks of $0$s and $k$ $0$s so there are hence $\binom{3k}{2k}$ valid $\alpha$s. For each $\alpha$, we may permute the $k+1$ numbers among $\{ a_1, a_2, \ldots, a_{3 k+1} \}$ that are $1 \pmod 3$, permute the $k$ numbers that are $2 \pmod 3$, and the $k$ numbers that are $0 \pmod 3$. Hence, the total answer is $ \binom{3k}{2k}(k+1)!k!k! = \frac{(3k)!(k+1)!k!}{(2k)!}. $