Look here: http://www.artofproblemsolving.com/Wiki/index.php/USAJMO_2010_Problem_1 I know that there are a lot of things to improve, but I think I got it.

Sorry to revive, but I believe this post is warranted because the USAJMO is coming up very soon, and I would like to know any other possible solutions to this problem. Anyone?

When I first did this problem, I got the exact same solution as well; I don't believe there is another solution.

See my proof at http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=400185&p=2227412&hilit=permutation#p2227412.

@bogtro: that's what i did last year

If you do it like mavropnevma but don't word it as formally; and definitely no fancy operators. Could you still get a 7 if it is clearly right (exact same argument with different words)

Solution Lemma : ${P(n)= \prod_{k=1}^{n}\lfloor\sqrt{\frac{n}{k}}}\rfloor! $

BOGTRO wrote: Let the numbers 1 to n be divided into sets as follows: ${1, 4, \hdots, a^2}$ ${2, 8, \hdots, 2b^2}$ ${3, 12, \hdots, 3c^2}$, etc. Clearly, there are thus $\lfloor \sqrt{n} \rfloor! \cdot \lfloor \frac{\sqrt{n}}{2} \rfloor! \hdots$ permutations. Wait.. but isn't ${4, 16, \hdots 4d^2}$ a subset of ${1, 4, \hdots , a^2}$? How do you account for that (sorry fhr the revive, but I don't understand) It should be $\lfloor \sqrt{n} \rfloor! \cdot \lfloor \frac{\sqrt{n}}{2} \rfloor! \hdots$ divided by a ton of terms, right?

$4, 16, \ldots, 4d^2$ isn't listed - and in fact it isn't a part of BOGTRO's partition. Each of the parts of the partition is the set of all terms of the form $kx^2,$ where $k$ is square-free.

utkarshgupta wrote: Solution Lemma : ${P(n)= \prod_{k=1}^{n}\lfloor\sqrt{\frac{n}{k}}}\rfloor! $ @MSTang but in that case, this formula is incorrect, right?

I think so. Rather than $k = 1, 2, 3, \ldots, n,$ the product should be over all square-free integers $k$ from $1$ to $n.$

Sorry for the bump, but I feel this problem was worded really weird, this is just my opinion of course. Are most jmo problems worded like this? Am I the only one that feels this way about this problem? If someone could explain this part a little more, that would be very appreciated. Is this hard for a #1?? Thank you in advance. tenniskidperson3 wrote: Let $P (n)$ be the number of permutations of $[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. EDIT: Ok I think I finally understood the problem phew but it took me about 30 minutes to just understand this I would still like to know if I am the only one that felt it was worded weird..

What did you find weird about it? It looks unambiguous to me.

Basically i just grouped them in perfect squares, perfect squares*2, perfect squares*3, perfect squares*k for all k such that k is not divisible by a square. Then I got that the formula for P(n) must be ∏ floor(sqrt(n/k))! from k=1 to n where k is not divisible by a square (unless it is 1). Then I was stuck on how to find minimum but I thought of prime factorizing 2010 because we have factorial. So 2010=2*3*5*67, and from here i think it is clear that the smallest value of n is 67^2=4489. Can anyone check this to make sure I did not mess up?

vishy wrote: Can anyone check this to make sure I did not mess up? That looks fine to me, though obviously on an actual contest you would have to write out the details --- specifically, you need to (a) write out where the formula \[ P(n) = \prod_{k \text{ squarefree}} \left\lfloor \sqrt{\frac nk} \right\rfloor! \]comes from, (b) that $P(67^2)$ is indeed divisible by $2010$ (obvious), and (c) that $P(n)$ is not divisible by $2010$ for any $n < 67^2$ (which is just because no $67$ terms appear). I trust of course that you know all of this, just that during an olympiad these details need to be supplied.

So in an olympiad you would have to write out solutions even for non-proof problems? Oh ok yeah I knew the three parts and probably should have added them in my solution , great advice Thank you v_Enhance!

vishy wrote: So in an olympiad you would have to write out solutions even for non-proof problems? Yes, on an olympiad contest you need to write out complete proofs even if the problem doesn't specifically ask for it.

Does this solution work? I know it's similar to the other ones in the thread but the wording in my proof doesn't seem quite right to me...

The answer is $4489$, so let's prove it. Let $a_k=s_k\cdot t_k^2$ where $s_k$ is square-free. Then, we must have $k=s_k\cdot t_j^2$ for some integer $t_j$ in order for $ka_k$ to be a perfect square. So, consider the integers $s_k\cdot 1^2, s_k\cdot 2^2, \ldots$ that are at most $n$. Then, those numbers have to be placed in positions that is some permutation of them. The maximum $t$ such that $s_k\cdot t^2\leq n$ is $t=\left\lfloor\sqrt{\frac{n}{s_k}}\right\rfloor$, so we get \[P(n)=\left\lfloor\sqrt{\frac{n}{s_1}}\right\rfloor!\cdot \left\lfloor\sqrt{\frac{n}{s_2}}\right\rfloor!\cdot \left\lfloor\sqrt{\frac{n}{s_3}}\right\rfloor!\cdot \ldots\]where $s_1, s_2, s_3,\ldots$ is the increasing sequence of square-free positive integers. We know that $2010 = 2\cdot 3\cdot 5\cdot 67$, so we must have $\left\lfloor\sqrt{\frac{n}{s_1}}\right\rfloor = \left\lfloor\sqrt{n}\right\rfloor\geq 67$, so the minimum $n$ is $67^2 = 4489$, as desired.

We claim that the answer is $67^2=4489$. To see this, develop the following formula. Let each number $i$ in the set be $c_i\cdot x^2$, where $c_i$ is square free. In order for $ka_k$ to be a perfect square, the two $c_i$'s must be equal. For a given $c_i$, the number of permutations is: \[\left\lfloor\sqrt{\frac{n}{c_i}}\right\rfloor!.\] Thus, the formula for $P(n)$ is: \[\prod_{c}\left\lfloor\sqrt{\frac{n}{c}}\right\rfloor!,\]where the values of $c$ are all square-free integers from $1$ to $n$. If it were to be a multiple of $2010=67\cdot5\cdot3\cdot2$. It would need a $67$. Thus, $n$ must at least $67^2$, which also works when substituted.

to form a permutation first arrange the perfect squares in the perfect square indexes --> this has $\lfloor \sqrt{n} \rfloor!$ ways then arrange the perfect squares/2 in the perfect square/2 indexes --> this has $\lfloor \sqrt{n/2} \rfloor!$ ways then arrange the perfect squares/3 in the perfect square/3 indexes --> this has $\lfloor \sqrt{n/3} \rfloor!$ ways this repeats so $P(n)=(\lfloor \sqrt{n} \rfloor!)(\lfloor \sqrt{n/2} \rfloor!)..(\lfloor \sqrt{n/1434} \rfloor!)...$ To divide $2010$, it has to divide $67$, so $\lfloor \sqrt{n} \rfloor! \ge 67$ and $n \ge 67^2 = \boxed{4489}$

realized i haven't made a post here

(sketch) Let $S \subseteq\mathbb{N}$ be the set of squarefree numbers. Moreover, for any $s \in S$ let $f_s(n)$ be the number of positive integers $k \leq n$ where $sk$ is a square number. We explicitly give the formula \[ P(n) = \prod_{s \in S} f_s(n)! \]Note that if $2010$ divides $P(n)$ then $67$ divides $ \prod_{s \in S} f_s(n)!$. Note that $s \in S$ and $s>1$ then $f_s(n)<f_1(n)$, so if $67$ divides $ \prod_{s \in S} f_s(n)! $ then $67$ divides $f_1(n)!$. So, $f_1(n) \geq 67 \implies n \geq 67^2$. Note that $2010$ divides $P(67^2)$ so we are done

Yay, a combo I can actually solve! We claim that the answer is $67^2 = 4489.$ We will find an explicit formula for $P(n)$ to show this. Suppose we have an integer $1 \le k \le n.$ Write $k = xk_0^2,$ where $x$ is as small as possible (note that $x$ is squarefree). Thus we can actually categorize the different $1 \le k \le n$: those that are of the form $x^2,$ those of the form $2x^2,$ those of the form $3x^2,$ and so on, for every squarefree integer. If $m_k$ is the $k$th squarefree integer, then call each category $d_i$ the set of integers of the form $m_i x^2.$ Clearly each number in each category must be paired with itself in our final result. In particular, there are $\left\lfloor \sqrt{\frac{n}{m_k}} \right\rfloor$ numbers in the $d_k.$ Therefore, \[ P(n) = \prod_{i=1}^{\infty} \left\lfloor \sqrt{\frac{n}{m_i}} \right\rfloor !. \]Note that $2010$ is divisble by the prime number $67,$ so one of the terms has to be $67!$ if $n$ is minimized. It clearly must be $\lfloor \sqrt{n} \rfloor !$ since any other term would result in a larger value of $n$ (and $\lfloor \sqrt{n} \rfloor !$ would also contain the factor of $67$ already). The smallest value of $n$ that satisfies this is $n = 67^2.$ This works since $2010 \mid 67!.$

Let $S$ denote the set of squarefree integers. Then $P(n)$ can be expressed in the form \[\prod_{k \in S} \left \lfloor \sqrt{\frac nk} \right \rfloor !.\] We have $2010 = 2 \cdot 3 \cdot 5 \cdot 67$, so we need a factor of 67 in this product. The first time this occurs is when $n = \boxed{67^2}$ and $k=1$, so nothing less works. Clearly, we also have $2 \cdot 3 \cdot 5 \mid 67!$, so this value of $n$ is indeed valid. $\blacksquare$

Note that any perfect square may be paired up with any other perfect square— so that gives a “sub-permutation” of $\lfloor\sqrt n\rfloor !$ ways so far (as there are $\lfloor \sqrt n\rfloor$ perfect squares in our allowed range). If it’s $2$ times a perfect square, or $2k^2$ for some $k$, it may only be paired up with others of the same form. This adds another factor of $\lfloor\sqrt{\tfrac n2}\rfloor!$, using similar logic as above. We can continue this to get that $P(n)$ is \[\prod_{1\le \ell\le n}\left\lfloor\sqrt{\frac{n}{\ell}}\right\rfloor!\qquad \text{for all squarefree $\ell$.}\]Since $2010=2\cdot 3\cdot 5\cdot 67$, $67$ must be a factor of one of the $\lfloor\sqrt{\tfrac{n}{\ell}}\rfloor!$’s. If we want to minimize $n$, we can take $67$ to be a factor of $\lfloor \sqrt{n}\rfloor!$, and then $n=67^2$. It’s easy to check that $n=67^2$ works, so that is our answer. $\square$

I claim that the answer is $67^2$, or $4489$. Definitions. Define $S_{(n,b)}$ for some positive integer $n$ and positive integer $b$ not divisible by the square of any prime to be the set of all integers $0<k\leq n$ that can be expressed as $a^b$ for some positive integer $a$. In other words, $k\in S_{(n,b)}$ if and only if $\sqrt k=a\sqrt b$ for some $a$ in the set of natural numbers. Additionally, define a "good" permutation $P(n)$ to be a permutation such that $ka_k$ is a perfect square for all integers $k$ such that $1\leq k\leq n$. -- Now I claim that $4489$ works. Let the number of "good" permutations be $m$. Note that for any $k\in S_{(n,b)}$ for any $(n,b)$, the mapping of $k$ after the permutation, or $k$, must also be in $S_{(n,b)}$ in order for $ka_k$ to be a perfect square. Additionally, if $a_k\in S_{(n,b)}$, then $ka_k$ is indeed a perfect square. Therefore; \[m=\Pi_{b\leq n} |S_{(n,b)}|!,\]for all $b$ not divisible by the square of any prime. Note that since $S_{(4489,1)}=67$, we have that $67!\mid m$. Since $2010\mid 67!$, we must have that $2010\mid m$, as desired. Finally, note that since $67\mid 2010$, we must have that $67\mid|S_{(n,b)}|!$ for some $(n,b)$. Since $67$ is prime, this implies that \[|S_{(n,b)}|\geq 67 \iff n\geq 67^2b \iff n\geq 4489,\]since $b\geq1$. This is what we wished to prove, finishing the problem.

Let the numbers from 1 to n be divided into sets: ${1, 4, \cdots, a^2}$; ${2, 8, \cdots, 2a_1^2}$; ${3, 12, \cdots, 3a_2^2}$, and we continue in the same manner. If we order these sets, we get a permutation. Clearly, there are $\lfloor \sqrt{n} \rfloor! \cdot \lfloor \frac{\sqrt{n}}{2} \rfloor! \cdots$ permutations $\Rightarrow$ ${P(n)= \prod_{k=1}^{n}\lfloor\sqrt{\frac{n}{k}}}\rfloor!$ We have 2010 = 2.3.5.67 $\Rightarrow$ since we search the minimum of n it occurs when $67 \mid \lfloor \sqrt{n} \rfloor!$ $\Rightarrow$ $\lfloor \sqrt{n} \rfloor \geq 67$ $\Rightarrow$ $\sqrt{n} \geq 67$ $\Rightarrow$ $n \geq 67^2 = 4489$ $\Rightarrow$ n = 4489.

For a squarefree positive integer $s$, define $G_s$ as the set of positive integers at most $n$ of the form $sk^2$ where $k$ is an integer. $\textbf{Lemma 1.}$ Every integer in $\{1, 2, \dots, n \}$ belongs to some $G_s$. Proof. Simply divide any positive integer by its largest square factor, and let the result be $s$. Then that integer belongs to $G_s$ by definition. $\textbf{Lemma 2.}$ All $G_s$ are disjoint. Proof. For the sake of contradiction assume that some positive integer belongs in both $G_{s_A}$ and $G_{s_B}$ where $s_A$ and $s_B$ are distinct squarefree integers. Then for some integers $u$, $v$ we have $s_A u^2 = s_B v^2$ implying $s_A s_B$ is a square. By a simple $\nu_p$ argument it is easy to see that the latter can only occur when $s_A = s_B$, a contradiction. These two lemmas readily imply that the disjoint union of all $G_s$ is $\{1, 2, \dots, n \}$. Now the problem falls apart due to the following claim: $\textbf{Claim 1.}$ If $a$, $b$ are positive integers, then $ab$ is a square if and only if some $s$ exists where $a, b \in G_s$. Proof. The "if" part is obvious. For the "only if" part, for the sake of contradiction let $a = s_A u^2$ and $b = s_B v^2$ where $s_A$ and $s_B$ are distinct squarefree integers. Then $ab = s_A s_B u^2v^2$ is a square, which implies $s_A s_B$ is a square. Again, this can only happen when $s_A = s_B$, a contradiction. Now it is obvious that $P(n) = \prod_{s \text{ squarefree}} |G_s|!$. The largest of the $G_s$ is $G_1$, and since the largest prime factor of $2010$ is $67$ we must have $|G_1| \ge 67 \implies n \ge 67^2$. Now $n = 67^2$ works since $2010 \mid 67!$. The final answer is $67^2 = 4489$.

Just wondering, did you have to find the general formula for the solution, or could you write the solution without it?

The answer is $\boxed{67^2}$, a number far too large to compute in the timespan of the USAJMO. The key is that all squares must be permuted among each other giving us $\lfloor \sqrt{\frac{n}{k}} \rfloor !$ and generalizing this obvious statement. We then split the numbers into groups based on their largest squarefree factor $k$. In the previous case, $k=1$. Its not hard to see that all groups must be permuted within each other, giving us the answer of $$P(n) = \prod_{k \in \text{squarefree integers}} \lfloor \sqrt{\frac{n}{k}} \rfloor !$$We need a factor of $67$ in this and the conclusion immediately follows. No number smaller than $67^2$ will produce a factor of $67$ because the number being factorialied is smaller than that. @below yes

@above ru doing entry combo from otis lol I wrote this solution before but never had a chance to post it: Notice that for $k$ being a perfect square, since there are $\lfloor \sqrt{n} \rfloor$ perfect squares less than or equal to $n,$ and each of these squares match with such a $k,$ there are $\lfloor \sqrt{n} \rfloor!$ ways to order the perfect squares. Similarly, in general we apply this same logic to squarefree integers $k,$ (since if it wasn't squarefree it would have been counted when considering some squarefree number), we get that $$P(n) = \prod_{k \text{ squarefree}} \left(\left\lfloor \sqrt{\frac{n}{k}} \right\rfloor! \right).$$Clearly for $P(n)$ to be a multiple of $2010,$ it must be a multiple of $67,$ so one of the terms in the product is a multiple of $67.$ Thus to minimize $n,$ it must be $\lfloor \sqrt{n} \rfloor!$ so $n \geq 67^2.$ We can then see that clearly $n=67^2 = \boxed{4489}$ works, so this is our answer.