2010 USAJMO Problems/Problem 1

Problem

A permutation of the set of positive integers $[n] = {1,2,\ldots,n}$ is a sequence $(a_1,a_2,\ldots,a_n)$ such that each element of $[n]$ appears precisely one time as a term of the sequence. For example, $(3, 5, 1, 2, 4)$ is a permutation of $[5]$ . Let $P(n)$ be the number of permutations of $[n]$ for which $ka_k$ is a perfect square for all $1 \le k \le n$ . Find with proof the smallest $n$ such that $P(n)$ is a multiple of $2010$ .

Solution

The smallest $n = 67^2$ .

Proof

Let $S = \{1, 4, 9, \ldots\}$ be the set of positive perfect squares. We claim that the relation $R = \{(j, k) \in [n]\times[n] \st jk \in S\}$ (Error compiling LaTeX. Unknown error_msg) is an equivalence relation on $[n]$ .

It is reflexive because $k^2 \in S$ for all $k \in [n]$ .
It is symmetric because $jk \in S \implies kj = jk \in S$ .
It is transitive because if $jk \in S$ and $kl \in S$ , then $jk\cdot kl = jlk^2 \in S \implies jl \in S$ , since $S$ is closed under multiplication and a non-square times a square is always a non-square.

We are restricted to permutations for which $ka_k \in S$ , in other words to permutations that send each element of $[n]$ into its equivalence class. Suppose there are $N$ equivalence classes: $C_1, \ldots, C_N$ . Let $n_i$ be the number of elements of $C_i$ , then $P(n) = \prod_{i=1}^{N} n_i!.$

Now $2010 = 2 \cdot 3 \cdot 5 \cdot 67$ . In order that $2010 \mathrel{\vert} P(n)$ , we must have $67 \mathrel{\vert} n_m!$ for the class $C_m$ with the most elements. This means $n_m \ge 67$ , since no smaller factorial will have $67$ as a factor. This condition is sufficient, since $n_m!$ will be divisible by $30$ for $n_m \ge 5$ , and even more so $n_m \ge 67$ .

The smallest element $g_m$ of the equivalence class $C_m$ is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of $C_m$ . Also, each prime $p$ that divides $g_m$ divides all the other elements $k$ of $C_m$ , since $p^2 \mathrel{\vert} g_mk$ and thus $p \mathrel{\vert} k$ . Therefore $g_m \mathrel{\vert} k$ for all $k \in C_m$ . The primes that are not in $g_m$ occur an even number of times in each $k \in C_m$ .

Thus the equivalence class $C_m = \{g_mk^2 \le n\}$ . With $g_m = 1$ , we get the largest possible $n_m$ . This is just the set of squares in $[n]$ , of which we need at least $67$ , so $n \ge 67^2$ . This condition is necessary and sufficient.

Page

Toolbox

Search

2010 USAJMO Problems/Problem 1

Problem

Solution

Proof