Difference between revisions of "2010 USAJMO Problems/Problem 1"

Latest revision as of 14:28, 28 October 2024

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\leq k\leq n$ . Find with proof the smallest $n$ such that $P(n)$ is a multiple of $2010$ .

Solution 1

We claim that the smallest $n$ is $67^2 = \boxed{4489}$ .

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]\mid jk\in S\}$ 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\mid P(n)$ , we must have $67\mid n_m!$ for the class $C_m$ with the most elements. This means $n_m\geq 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\geq 5$ , and even more so $n_m\geq 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\mid kg_m$ and thus $p\mid k$ . Therefore $g_m\mid 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\leq 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\geq 67^2$ . This condition is necessary and sufficient.

Solution 2

Solution 1 can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":

It is possible to write all positive integers $n$ in the form $p\cdot m^2$ , where $m^2$ is the largest perfect square dividing $n$ , so $p$ is not divisible by the square of any prime. Obviously, one working permutation of $[n]$ is simply $(1, 2, \ldots, n)$ ; this is acceptable, as $ka_k$ is always $k^2$ in this sequence.

Lemma 1. We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities $p$ .

Proof. Let $p_k$ and $m_k$ be the values of $p$ and $m$ , respectively, for a given $k$ as defined above, such that $p$ is not divisible by the square of any prime. We can obviously permute two numbers which have the same $p$ , since if $p_j = p_w$ where $j$ and $w$ are 2 values of $k$ , then $j\cdot w = p_j^2\cdot m_j^2\cdot m_w^2$ , which is a perfect square. This proves that we can permute any numbers with the same value of $p$ .

End Lemma

Lemma 2. We will prove the converse of Lemma 1: Let one number have a $p$ value of $\phi$ and another, $\gamma$ . $\phi\cdot f$ and $\gamma\cdot g$ are both perfect squares.

Proof. $\phi\cdot f$ and $\gamma\cdot g$ are both perfect squares, so for $\phi\cdot \gamma$ to be a perfect square, if $g$ is greater than or equal to $f$ , $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 = 1f$ ; $g = f$ . Similarly, if $f\geq g$ , then $f = g$ for our rules to keep working.

End Lemma

We can permute $l$ numbers with the same $p$ in $l!$ ways. We must have at least 67 numbers with a certain $p$ so our product will be divisible by 67. Obviously, then it will also be divisible by 2, 3, and 5, and thus 2010, as well. Toms as $h$ , in general, we need numbers all the way up to $h\cdot 67^2$ , so obviously, $67^2$ is the smallest such number such that we can get a $67!$ term; here 67 $p$ terms are 1. Thus we need the integers $1, 2, \ldots, 67^2$ , so $67^2$ , or $\boxed{4489}$ , is the answer.

Solution 3 (Not a formal proof but understandable)

We claim the smallest $n$ is $67^2 = \boxed{4489}$ Looking at small cases we see that $P(n)$ changes every time n increases to a perfect square. We find that we can not permute the non squares around because $n$ (not a perfect square) $*a_w$ where $w \neq n$ will not give a perfect square. But we can permute the perfect squares around to other perfect squares since a square times a square makes another square we can do this (# of squares below $n$ )! times. So now we need to find $n = a^2$ such that $a!$ is divisible by $2010$ which largest prime factor is $67$ so, $n$ is $n$ is $67^2 = \boxed{4489}$ ~bjump

Solution Number Sense

We have to somehow calculate the number of permutations for a given $n$ . How in the world do we do this? Because we want squares, why not call a number $k=m*s^2$ , where $s$ is the largest square that allows $m$ to be non-square? $m=1$ is the only square $m$ can be, which only happens if $k$ is a perfect square.

For example, $126 = 14 * 3^2$ , therefore in this case $k=126, m = 14, s = 3$ .

I will call a permutation of the numbers $P$ , while the original $1, 2, 3, 4, ...$ I will call $S$ .

Note that essentially we are looking at "pairing up" elements between $P$ and $S$ such that the product of $P_k$ and $S_k$ is a perfect square. How do we do this? Using the representation above.

Each square has to have an even exponent of every prime represented in its prime factorization. Therefore, we can just take all exponents of the primes $mod 2$ and if there are any odd numbers, those are the ones we have to match- in effect, they are the $m$ numbers mentioned at the beginning.

By listing the $m$ values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical $m$ s can be matched together. With such a solid idea let me prove it.

If we were to "pair up" numbers with different $m$ s, take for example $S_{18}$ with an $m$ of $2$ and $P_{18}=26$ with an $m$ of $26$ , note that their product gives a supposed $m$ of $13$ because the $2$ values cancel out. But then, what happens to the extra $13$ left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different $m$ values, and the smaller one is $m_1$ , in order for the product to leave a square, the larger $m$ value has to have not just $m_1$ but another square inside it, which is absurd because we stipulated at the beginning that $m$ was square-free except for the trivial multiplication identity, 1.

Now, how many ways are there to do this? If there are $c_1$ numbers with $m=1$ , there are clearly $(c_1)!$ ways of sorting them. The same goes for $m=2, 3, etc.$ by this logic. Note that the $P(n)$ as stated by the problem requires a $67$ thrown in there because $2010=2*3*5*67$ , so there has to be a $S_n$ with 67 elements with the same $m$ . It is evident that the smallest $n$ will occur when $m=1$ , because if $m$ is bigger we would have to expand $n$ to get the same number of $m$ values. Finally, realize that the only numbers with $m=1$ are square numbers! So our smallest $n=67^2=4489$ , and we are done.

I relied on looking for patterns a lot in this problem. When faced with combo/number theory, it is always good to draw a sketch. Never be scared to try a problem on the USAJMO. It takes about 45 minutes. Well, it's 2010 and a number 1. Cheers!

-expiLnCalc

Solution 4

It's well known that there exists $f(n)$ and $g(n)$ such that $n = f(n) \cdot g(n)$ , no square divides $f(n)$ other than 1, and $g(n)$ is a perfect square.

Lemma:  is a perfect square if and only if

We prove first: If $f(k) = f(a_k)$ , $k \cdot a_k$ is a perfect square.

$k \cdot a_k = f(k) \cdot g(k) \cdot f(a_k) \cdot g(a_k) = f(k)^2 \cdot g(k) \cdot g(a_k)$ , which is a perfect square.

We will now prove: If $k \cdot a_k$ is a perfect square, $f(k) = f(a_k)$ .

We do proof by contrapositive: If $f(k) \neq f(a_k)$ , $k \cdot a_k$ is not a perfect square.

$v_p(k)$ is the p-adic valuation of k. (Basically how many factors of p you can take out of k)

Note that if $f(k) \neq f(a_k)$ , By the Fundamental Theorem of Arithmetic, $f(k)$ and $f(a_k)$ 's prime factorization are different, and thus there exists a prime p, such that $v_p(f(k)) \neq v_p(f(a_k))$ . Also, since $f(k)$ and $f(a_k)$ is squarefree, $v_p(k), v_p(a_k) \leq 1$ . Thus, $v_p(k \cdot a_k) = 1$ , making $k \cdot a_k$ not a square.

End Lemma

Thus, we can only match k with $a_k$ if they have the same f value. Thus, to find P(k), we can do it by f value, permuting the $a_k$ with f value 1, then 2, ... Thus, our answer is:

$P(n) = \prod_{1 \leq i \leq n, g(i) = 1} \left\lfloor \sqrt{\frac{n}{i}} \right \rfloor !$

For all $n < 67^2$ , $P(n)$ doesn't have a factor of 67. However, if $n = 67^2$ , the first term will be a multiple of 2010, and thus the answer is $67^2 = \boxed{4489}$

-Alexlikemath

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Solution 5(stupid but simple)

The answer is 4489.(67 squared)

Proof

We start with trying to fulfill ways to do $P(n)$ . When n is 1 there is one way to do it and fulfill $ka_k$ as a perfect square. Same with the numbers 2 and 3. The order for both of these number are all in increasing order $1,2$ $1,2,3$ Now when it comes to 4 we could do $1,2,3,4$ and $4,2,3,1$ This means when n is a perfect square it increases where $k$ and $a_k$ are perfect squares. The prime factorization of 2010 is: $2010=2*5*3*67$ Because we only care about 67, the biggest divisor we do 67 squared because $n$ has to be a square. $67^2=4489$

-Multpi12

@@ Line 2: / Line 2: @@
 A permutation of the set of positive integers <math>[n] = \{1, 2, \ldots, n\}</math> is a sequence <math>(a_1, a_2, \ldots, a_n)</math> such that each element of <math>[n]</math> appears precisely one time as a term of the sequence. For example, <math>(3, 5, 1, 2, 4)</math> is a permutation of <math>[5]</math>. Let <math>P(n)</math> be the number of permutations of <math>[n]</math> for which <math>ka_k</math> is a perfect square for all <math>1\leq k\leq n</math>. Find with proof the smallest <math>n</math> such that <math>P(n)</math> is a multiple of <math>2010</math>.
-== Solutions ==
+== Solution 1 ==
 We claim that the smallest <math>n</math> is <math>67^2 = \boxed{4489}</math>.
-=== Solution 1 ===
 Let <math>S = \{1, 4, 9, \ldots\}</math> be the set of positive perfect squares. We claim that the relation <math>R = \{(j, k)\in [n]\times[n]\mid jk\in S\}</math> is an equivalence relation on <math>[n]</math>.
 * It is reflexive because <math>k^2\in S</math> for all <math>k\in [n]</math>.
@@ Line 19: / Line 18: @@
 Thus the equivalence class <math>C_m = \{g_mk^2\leq n\}</math>. With <math>g_m = 1</math>, we get the largest possible <math>n_m</math>. This is just the set of squares in <math>[n]</math>, of which we need at least <math>67</math>, so <math>n\geq 67^2</math>. This condition is necessary and sufficient.
-=== Solution 2 ===
+== Solution 2 ==
-This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
+Solution 1 can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
 It is possible to write all positive integers <math>n</math> in the form <math>p\cdot m^2</math>, where <math>m^2</math> is the largest perfect square dividing <math>n</math>, so <math>p</math> is not divisible by the square of any prime. Obviously, one working permutation of <math>[n]</math> is simply <math>(1, 2, \ldots, n)</math>; this is acceptable, as <math>ka_k</math> is always <math>k^2</math> in this sequence.
@@ Line 37: / Line 36: @@
 We can permute <math>l</math> numbers with the same <math>p</math> in <math>l!</math> ways. We must have at least 67 numbers with a certain <math>p</math> so our product will be divisible by 67. Obviously, then it will also be divisible by 2, 3, and 5, and thus 2010, as well. Toms as <math>h</math>, in general, we need numbers all the way up to <math>h\cdot 67^2</math>, so obviously, <math>67^2</math> is the smallest such number such that we can get a <math>67!</math> term; here 67 <math>p</math> terms are 1. Thus we need the integers <math>1, 2, \ldots, 67^2</math>, so <math>67^2</math>, or <math>\boxed{4489}</math>, is the answer.
+== Solution 3 (Not a formal proof but understandable) ==
+We claim the smallest <math>n</math> is <math>67^2 = \boxed{4489}</math>
+Looking at small cases we see that <math>P(n)</math> changes every time n increases to a perfect square. We find that we can not permute the non squares around because <math>n</math> (not a perfect square) <math>*a_w</math> where <math>w \neq n</math> will not give a perfect square. But we can permute the perfect squares around to other perfect squares since a square times a square makes another square we can do this (# of squares below <math>n</math>)! times. So now we need to find <math>n = a^2</math> such that <math>a!</math> is divisible by <math>2010</math> which largest prime factor is <math>67</math> so, <math>n</math> is <math>n</math> is <math>67^2 = \boxed{4489}</math>
+~bjump
 ==Solution Number Sense==
@@ Line 56: / Line 60: @@
 I relied on looking for patterns a lot in this problem. When faced with combo/number theory, it is always good to draw a sketch. Never be scared to try a problem on the USAJMO. It takes about 45 minutes. Well, it's 2010 and a number 1. Cheers!
+-expiLnCalc
+==Solution 4==
+It's well known that there exists <math>f(n)</math> and <math>g(n)</math> such that <math>n = f(n) \cdot g(n)</math>, no square divides <math>f(n)</math> other than 1, and <math>g(n)</math> is a perfect square.
+ Lemma: <math>k \cdot a_k</math> is a perfect square if and only if <math>f(k) = f(a_k)</math>
+We prove first: If <math>f(k) = f(a_k)</math>, <math>k \cdot a_k</math> is a perfect square.
+<math>k \cdot a_k = f(k) \cdot g(k) \cdot f(a_k) \cdot g(a_k) = f(k)^2 \cdot g(k) \cdot g(a_k)</math>, which is a perfect square.
+We will now prove: If <math>k \cdot a_k</math> is a perfect square, <math>f(k) = f(a_k)</math>.
+We do proof by contrapositive: If <math>f(k) \neq f(a_k)</math>, <math>k \cdot a_k</math> is not a perfect square.
+<math>v_p(k)</math> is the p-adic valuation of k. (Basically how many factors of p you can take out of k)
+Note that if <math>f(k) \neq f(a_k)</math>, By the Fundamental Theorem of Arithmetic, <math>f(k)</math> and <math>f(a_k)</math>'s prime factorization are different, and thus there exists a prime p, such that <math>v_p(f(k)) \neq v_p(f(a_k))</math>. Also, since <math>f(k)</math> and <math>f(a_k)</math> is squarefree, <math>v_p(k), v_p(a_k) \leq 1</math>. Thus, <math>v_p(k \cdot a_k) = 1</math>, making <math>k \cdot a_k</math> not a square.
+ End Lemma
+Thus, we can only match k with <math>a_k</math> if they have the same f value. Thus, to find P(k), we can do it by f value, permuting the <math>a_k</math> with f value 1, then 2, ... Thus, our answer is:
+<math>P(n) = \prod_{1 \leq i \leq n, g(i) = 1} \left\lfloor \sqrt{\frac{n}{i}} \right \rfloor !</math>
+For all <math>n < 67^2</math>, <math>P(n)</math> doesn't have a factor of 67. However, if <math>n = 67^2</math>, the first term will be a multiple of 2010, and thus the answer is <math>67^2 = \boxed{4489}</math>
+-Alexlikemath
 {{alternate solutions}}
+==Solution 5(stupid but simple)==
+The answer is 4489.(67 squared)
+Proof
+We start with trying to fulfill ways to do <math>P(n)</math>. When n is 1 there is one way to do it and fulfill <math>ka_k</math> as a perfect square. Same with the numbers 2 and 3. The order for both of these number are all in increasing order <cmath>1,2</cmath> <cmath>1,2,3</cmath> Now when it comes to 4 we could do <cmath>1,2,3,4</cmath> and <cmath>4,2,3,1</cmath> This means when n is a perfect square it increases where <math>k</math> and <math>a_k</math> are perfect squares. The prime factorization of 2010 is: <cmath>2010=2*5*3*67</cmath> Because we only care about 67, the biggest divisor we do 67 squared because <math>n</math> has to be a square.<cmath>67^2=4489</cmath>
+-Multpi12
 == See Also ==

2010 USAJMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search