6. [6] Let $\pi$ be a permutation of the numbers from 1 through 2012 . What is the maximum possible number of integers $n$ with $1 \leq n \leq 2011$ such that $\pi(n)$ divides $\pi(n+1)$ ?
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 $\ell$ (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$.