HMMT November

Solution:
Answer: $1006$

Since any proper divisor of $n$ must be less than or equal to $n / 2$, none of the numbers greater than $1006$ can divide any other number less than or equal to $2012$. Since there are at most $1006$ values of $n$ for which $\pi(n) \leq 1006$, this means that there can be at most $1006$ values of $n$ for which $\pi(n)$ divides $\pi(n+1)$.

On the other hand, there exists a permutation for which $\pi(n)$ divides $\pi(n+1)$ for exactly $1006$ values of $n$, namely the permutation:
$$\left(1,2,2^{2}, 2^{3}, \ldots, 2^{10}, 3,2 \cdot 3,2^{2} \cdot 3,2^{3} \cdot 3, \ldots, 2^{9} \cdot 3,5, \ldots\right)$$
Formally, for each odd number $\ell \leq 2012$, we construct the sequence $\ell, 2 \ell, 4 \ell, \ldots, 2^{k} \ell$, where $k$ is the largest integer such that $2^{k} \ell \leq 2012$. We then concatenate all of these sequences to form a permutation of the numbers $1$ through $2012$ (note that no number occurs in more than one sequence). It follows that if $\pi(n) \leq 1006$, then $\pi(n+1)$ will equal $2 \pi(n)$, and therefore $\pi(n)$ will divide $\pi(n+1)$ for all $1006$ values of $n$ satisfying $1 \leq \pi(n) \leq 1006$.