Problem: Let $P(n)$ be the number of permutations $(a_1, \dots, a_n)$
of the numbers $(1, 2, \dots, n)$ for which $ka_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$.

Solution: The answer is $n= 4489$.

We begin by giving a complete description of $P(n)$:
\begin{claim*}
  We have
  \[ P(n) = \prod_{c \text{ squarefree}} \left\lfloor \sqrt{\frac nc} \right\rfloor! \]
\end{claim*}
\begin{proof}
Every positive integer can be uniquely expressed in the form $c \cdot m^2$
where $c$ is a squarefree integer and $m$ is a perfect square.
So we may, for each squarefree positive integer $c$, define the set
\[ S_c = \left\{ c \cdot 1^2, c \cdot 2^2, c \cdot 3^2, \dots \right\}
  \cap \{1, 2, \dots, n\} \]
and each integer from $1$ through $n$ will be in exactly one $S_c$.
Note also that
\[ \left\lvert S_c \right\rvert = \left\lfloor
  \sqrt{\frac nc} \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}} |S_c|!
  = \prod_{c \text{ squarefree}} \left\lfloor \sqrt{\frac nc} \right\rfloor!
  \qedhere \]
\end{proof}

We want the smallest $n$ such that $2010$ divides $P(n)$.
\begin{itemize}
  \ii Note that $P(67^2)$ contains $67!$ as a term,
  which is divisible by $2010$, so $67^2$ is a candidate.
  \ii On the other hand, if $n < 67^2$,
  then no term in the product for $P(n)$ is divisible by the prime $67$.
\end{itemize}
So $n = 67^2 = 4489$ is indeed the minimum.