Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Proof 2)
(Made technical edits to second solution: 1) No need to restate problem twice 2) Diverted the two pairs of double-definition variables (k and n) 3) Fixed some wording issues (p can be 1, a square), etc)
Line 52: Line 52:
 
This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
 
This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
  
−
A permutation of the set of positive integers <math>[n] = {1, 2, . . . , n}</math> is a sequence <math>(a_1 , a_2 , . . . , a_n)</math> such that each element of [n] 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 n such that <math>P(n)</math> is a multiple of 2010.
+
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.
  
−
Solution:
+
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>.
  
−
Write all positive integers in the form <math>k(n^2)</math>, where n squared is the largest perfect square dividing n, so k is not a perfect square. Obviously, we can write the positive integers in the form 1, 2, ,3... y; this is acceptable, as n times a sub n is always n squared in this sequence.
+
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>.
−
 
 
−
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 <math>k</math>, the term multiplied by <math>n^2</math>, as if k(w) squared times m is a perfect square and so is k(j) squared times q, then k_m and k_q 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"
 
  
 
END LEMMA
 
END LEMMA
  
−
Lemma 2: We will prove the connverse of Lemma 1: Let one number have a k value of feta and another, gamma. feta times f and gamma times g are both perfect squares.
+
Lemma 2: We will prove the converse of Lemma 1: Let one number have a k value of feta and another, gamma. feta times f and gamma times g are both perfect squares.
  
 
f and gamma g are both perfect squares, so for feta g to be a perfect square, so 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 and g=f. Similarly, if f>=g, then f=g for our rules to keep working.
 
f and gamma g are both perfect squares, so for feta g to be a perfect square, so 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 and g=f. Similarly, if f>=g, then f=g for our rules to keep working.

Revision as of 20:53, 6 April 2011

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 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] \mathrel{|} 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 \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.

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

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 k value of feta and another, gamma. feta times f and gamma times g are both perfect squares.

f and gamma g are both perfect squares, so for feta g to be a perfect square, so 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 and g=f. Similarly, if f>=g, then f=g for our rules to keep working.

END LEMMA

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 produc 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^2)$. Thus we need the integers $1, 2,... 67^2$, so $67^2$, or 4489, is the answer.

END LEMMA

Q.E.D.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAJMO_Problems/Problem_1&oldid=38077"