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)
m (added a See Also section)
Line 73: Line 73:
  
 
Q.E.D.
 
Q.E.D.
 +
 +
== See Also ==
 +
{{USAJMO newbox|year=2005|before=First Question|num-a=3}}
 +
 +
[[Category:Olympiad Number Theory Problems

Revision as of 10:40, 15 April 2012

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 $p$ value of $\phi$ and another, $\gamma$. $\phi\cdot f$ and $\gamma\cdot g$ are both perfect squares.

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

END LEMMA

Q.E.D.

See Also

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

[[Category:Olympiad Number Theory Problems

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