Let $P(n)$ be the number of permutations $\left(a_{1}, \ldots, a_{n}\right)$ of the numbers $(1,2, \ldots, n)$ for which $k a_{k}$ is a perfect square for all $1 \leq k \leq n$. Find with proof the smallest $n$ such that $P(n)$ is a multiple of 2010.
The answer is $n=4489$. We begin by giving a complete description of $P(n)$:  Claim - We have  $$ P(n)=\prod_{c \text { squarefree }}\left\lfloor\sqrt{\frac{n}{c}}\right\rfloor! $$   $$ S_{c}=\left\{c \cdot 1^{2}, c \cdot 2^{2}, c \cdot 3^{2}, \ldots\right\} \cap\{1,2, \ldots, n\} $$  and each integer from 1 through $n$ will be in exactly one $S_{c}$. Note also that  $$ \left|S_{c}\right|=\left\lfloor\sqrt{\frac{n}{c}}\right\rfloor . $$  Then, the permutations in the problem are exactly those which send elements of $S_{c}$ to elements of $S_{c}$. In other words,  $$ P(n)=\prod_{c \text { squarefree }}\left|S_{c}\right|!=\prod_{c \text { squarefree }}\left\lfloor\sqrt{\frac{n}{c}}\right\rfloor! $$  We want the smallest $n$ such that 2010 divides $P(n)$.  - Note that $P\left(67^{2}\right)$ contains 67 ! as a term, which is divisible by 2010 , so $67^{2}$ is a candidate. - On the other hand, if $n<67^{2}$, then no term in the product for $P(n)$ is divisible by the prime 67 .  So $n=67^{2}=4489$ is indeed the minimum.