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

Revision as of 22:54, 15 August 2014

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$ .

Solutions

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

Solution 1

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

This proof 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.

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

@@ Line 1: / Line 1: @@
-==Problem==
+== Problem ==
-A permutation of the set of positive integers <math>[n] = {1,2,\ldots,n}</math>
+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>.
-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 \le k \le n</math>. Find with proof the smallest <math>n</math> such that <math>P(n)</math>
-is a multiple of <math>2010</math>.
-==Solution==
+== Solutions ==
-We claim that the smallest n is <math>67^2 = \boxed{4489}</math>.
+We claim that the smallest <math>n</math> is <math>67^2 = \boxed{4489}</math>.
-===Proof 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] \mathrel{|} jk \in S\}</math>
-is an equivalence relation on <math>[n]</math>.
-<ul>
-<li>It is reflexive because <math>k^2 \in S</math> for all <math>k \in [n]</math>.
-<li> It is symmetric because <math>jk \in S \implies kj = jk \in S</math>.
-<li> It is transitive because if <math>jk \in S</math> and <math>kl \in S</math>, then
-<math>jk\cdot kl = jlk^2 \in S \implies jl \in S</math>, since <math>S</math> is closed
-under multiplication and a non-square times a square is always a non-square.
-</ul>
-We are restricted to permutations for which <math>ka_k \in S</math>, in other
+=== Solution 1 ===
-words to permutations that send each element of <math>[n]</math> into its
+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>.
-equivalence class. Suppose there are <math>N</math> equivalence classes: <math>C_1, \ldots,
+* It is reflexive because <math>k^2\in S</math> for all <math>k\in [n]</math>.
-C_N</math>. Let <math>n_i</math> be the number of elements of <math>C_i</math>, then
+* It is symmetric because <math>jk\in S\implies kj = jk\in S</math>.
-<math>P(n) = \prod_{i=1}^{N} n_i!.</math>
+* It is transitive because if <math>jk\in S</math> and <math>kl\in S</math>, then <math>jk\cdot kl = jlk^2\in S\implies jl\in S</math>, since <math>S</math> is closed under multiplication and a non-square times a square is always a non-square.
-Now <math>2010 = 2 \cdot 3 \cdot 5 \cdot 67</math>. In order that <math>2010 \mathrel{\vert}
+We are restricted to permutations for which <math>ka_k \in S</math>, in other words to permutations that send each element of <math>[n]</math> into its equivalence class. Suppose there are <math>N</math> equivalence classes: <math>C_1, \ldots, C_N</math>. Let <math>n_i</math> be the number of elements of <math>C_i</math>, then <math>P(n) = \prod_{i=1}^{N} n_i!</math>.
-P(n)</math>, we must have <math>67 \mathrel{\vert} n_m!</math> for the class <math>C_m</math> with the most
-elements. This means <math>n_m \ge 67</math>, since no smaller factorial will
-have <math>67</math> as a factor. This condition is sufficient, since <math>n_m!</math>
-will be divisible by <math>30</math> for <math>n_m \ge 5</math>, and even more so <math>n_m
-\ge 67</math>.
-The smallest element <math>g_m</math> of the equivalence class <math>C_m</math> is
+Now <math>2010 = 2\cdot 3\cdot 5\cdot 67</math>. In order that <math>2010\mid P(n)</math>, we must have <math>67\mid n_m!</math> for the class <math>C_m</math> with the most elements. This means <math>n_m\geq 67</math>, since no smaller factorial will have <math>67</math> as a factor. This condition is sufficient, since <math>n_m!</math> will be divisible by <math>30</math> for <math>n_m\geq 5</math>, and even more so <math>n_m\geq 67</math>.
-square-free, since if it were divisible by the square of a prime,
-the quotient would be a smaller element of <math>C_m</math>. Also, each prime
-<math>p</math> that divides <math>g_m</math> divides all the other elements <math>k</math> of <math>C_m</math>,
-since <math>p^2 \mathrel{\vert} g_mk</math> and thus <math>p \mathrel{\vert} k</math>. Therefore
-<math>g_m \mathrel{\vert} k</math> for all <math>k \in C_m</math>. The primes that are not in <math>g_m</math>
-occur an even number of times in each <math>k \in C_m</math>.
-Thus the equivalence class <math>C_m = \{g_mk^2 \le n\}</math>.
+The smallest element <math>g_m</math> of the equivalence class <math>C_m</math> is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of <math>C_m</math>. Also, each prime <math>p</math> that divides <math>g_m</math> divides all the other elements <math>k</math> of <math>C_m</math>, since <math>p^2\mid kg_m</math> and thus <math>p\mid k</math>. Therefore <math>g_m\mid k</math> for all <math>k\in C_m</math>. The primes that are not in <math>g_m</math> occur an even number of times in each <math>k\in C_m</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 \ge
-^2</math>. This condition is necessary and sufficient.
-===Proof 2===
+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 ===
 This proof 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.
+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.
-Lemma 1: We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities <math>p</math>.
+'''Lemma 1.''' We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities <math>p</math>.
-Let <math>p_k</math> and <math>m_k</math> be the values of <math>p</math> and <math>m</math>, respectively, for a given <math>k</math> as defined above, such that <math>p</math> is not divisible by the square of any prime. We can obviously permute two numbers which have the same <math>p</math>, since if <math>p_j = p_w</math> where <math>j</math> and <math>w</math> are 2 values of <math>k</math>, then <math>j\cdot w</math>=<math>p_j^2\cdot m_j^2\cdot m_w^2</math>, which is a perfect square. This proves that we can permute any numbers with the same value of <math>p</math>.
+''Proof.'' Let <math>p_k</math> and <math>m_k</math> be the values of <math>p</math> and <math>m</math>, respectively, for a given <math>k</math> as defined above, such that <math>p</math> is not divisible by the square of any prime. We can obviously permute two numbers which have the same <math>p</math>, since if <math>p_j = p_w</math> where <math>j</math> and <math>w</math> are 2 values of <math>k</math>, then <math>j\cdot w = p_j^2\cdot m_j^2\cdot m_w^2</math>, which is a perfect square. This proves that we can permute any numbers with the same value of <math>p</math>.
-END LEMMA
+'''End Lemma'''
-Lemma 2: We will prove the converse of Lemma 1: Let one number have a <math>p</math> value of <math>\phi</math> and another, <math>\gamma</math>. <math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares.
+'''Lemma 2.''' We will prove the converse of Lemma 1: Let one number have a <math>p</math> value of <math>\phi</math> and another, <math>\gamma</math>. <math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares.
-<math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares, so for <math>\phi\cdot \gamma</math> to be a perfect square, if <math>g</math> is greater than or equal to <math>f</math>, <math>g/f</math> must be a perfect square, too. Thus <math>g</math> is <math>f</math> times a square, but <math>g</math> cannot divide any squares besides <math>1</math>, so <math>g=1f</math>; <math>g=f</math>. Similarly, if <math>f\ge g</math>, then <math>f=g</math> for our rules to keep working.
+''Proof.'' <math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares, so for <math>\phi\cdot \gamma</math> to be a perfect square, if <math>g</math> is greater than or equal to <math>f</math>, <math>g/f</math> must be a perfect square, too. Thus <math>g</math> is <math>f</math> times a square, but <math>g</math> cannot divide any squares besides <math>1</math>, so <math>g = 1f</math>; <math>g = f</math>. Similarly, if <math>f\geq g</math>, then <math>f = g</math> for our rules to keep working.
-END LEMMA
+'''End Lemma'''
-Lemma 3: Getting to the answer
+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.
-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.
-END LEMMA
-Q.E.D.
+{{alternate solutions}}
 == See Also ==
+* <url>viewtopic.php?t=347303 Discussion on AoPS/MathLinks</url>
 {{USAJMO newbox|year=2010|before=First Question|num-a=2}}
 [[Category:Olympiad Number Theory Problems]]
 {{MAA Notice}}

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