USAJMO 2010 Problem 1

Revision as of 21:52, 25 January 2017 by Dli00105 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
This article has been proposed for deletion. The reason given is: Unnecessary duplicate of 2010 USAJMO Problems/Problem 1.

Sysops: Before deleting this article, please check the article discussion pages and history.

A permutation of the set of positive integers [n] = $\{1, 2, \dots , n\}$ is a sequence $\{a_1 , a_2 ,\dots , 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$.


Write all positive integers in the form k(n) squared, where n squared is the largest perfect square dividing n, so k is not a perfect square. Obviously, we can let our permutation be $1,2,\dots ,n$; this is acceptable, as $na_n=n^2$ in this sequence.

Lemma 1: We can permute any numbers which, when divided by the largest perfect square that divides them, yield equal quantites, the quanity "k" in this example.

We can obviously permute two numbers which have the same "$k$," the term multiplied by n squared, as if k(w) squared times m is a perfect square and so is k(j) squared times q, then km and kq are perfect squares as are k(j) squared times m and similarly, k(w) squared times q is a perfect square. This proves that we can permute any two, and thus any numbers with the same "$k$".


Lemma 2: We will prove the connverse of Lemma 1: Let one number, $f$ have a k-value of $\alpha$ and another, $g$, have a k-value of $\beta$. $\alpha f$ and $\beta g$ are both perfect squares.

$\alpha f$ and $\beta g$ are both perfect squares, so if $\alpha g$ to be a perfect square and $g\ge f$, $\frac{g}{f}$ must be a perfect square, too. Thus, $g$ is $f$ times a square, but $g$ cannot divide any squares besides 1, so $g=f$. Similarly, if $f\ge g$, then $f=g$ for our rules to keep working.


Lemma 3: Getting to the answer

We can permute $l$ numbers with the same $k$ in $l!$ ways. We must have at least 67 numbers with a certain "$k$" so our product wil be divisible by 67. Obviously, then it will be divisible by 2, 3, and 5, and thus 2010, as well. Obviously, 67 squared is the smallest such number so that we can get a 67! term; here 67 k terms are "1." To get 67 $k$ terms as $f$, in general, we need numbers all the way up to f(67) squared. Thus we need the integers $1, 4, \dots , 67^2$, so $67^2=4489$ is the answer.



Note: We can write $P(n)=\prod_{1\le i\le n,\, i\text{ squarefree}}{\left\lfloor\sqrt{n/i}\right\rfloor!}$.

The smallest $n$ such that for some $i$ the factorial is divisible by 67 is when $n=67^2, i=67$.

Invalid username
Login to AoPS