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 "2019 USAMO Problems/Problem 1"

(→‎Solution)
(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
\usepackage{amsmath}
 
  
 
<math>\newline</math>
 
<math>\newline</math>
Line 52: Line 51:
 
<math>\newline</math>
 
<math>\newline</math>
  
−
<math>\newline</math>
 
−
Let <math>f^r(x)</math> denote the resulr when <math>f</math> is applied to <math>x</math> <math>r</math> times.
 
−
<math>\newline\newline</math>
 
−
If <math>f(p)=f(q)</math>, then <math>f^2(p)=f^2(q)</math> and <math>f^{f(p)}(p)=f^{f(q)}(q)\newline\implies p^2=f^2(p)\cdot f^{f(p)}(p)=f^2(q)\cdot f^{f(q)}(q)=q^2\newline\implies p=\pm q\newline\implies p=q</math>since <math>p,q>0</math>.
 
−
\newline
 
−
Therefore, <math>f</math> is injective.
 
−
<math>\newline\newline</math>
 
−
Lemma 1: If <math>f^r(b)=a</math> and <math>f(a)=a</math>, then b=a.
 
−
<math>\newline\newline</math>
 
−
Proof:
 
−
<math>\newline</math>
 
−
Otherwise, set <math>a</math>, <math>b</math>, and <math>r</math> to a counterexample of the lemma, such that <math>r</math> is minimized. By injectivity, <math>f(a)=a\implies f(b)\neq a</math>, so <math>r\neq1</math>. If <math>f^n(b)=a</math>, then <math>f^n-1(f(b))=a</math> and <math>f(b)\neq a</math>, a counterexample that contradicts our assumption that <math>r</math> is minimized, proving Lemma 1.
 
−
<math>\newline\newline</math>
 
−
Lemma 2: If <math>f^2(m)=f^{f(m)}(m)=m</math>, and <math>m</math> is odd, then <math>f(m)=m</math>.
 
−
<math>\newline\newline</math>
 
−
Proof:
 
−
<math>\newline</math>
 
−
Let <math>f(m)=k</math>. Since <math>f^2(m)=m</math>, <math>f(k)=m</math>. So, <math>f^2(k)=k</math>. <math>\newline f^2(k)\cdot f^{f(k)}(k)=k^2</math>.
 
−
<math>\newline</math>
 
−
Since <math>k\neq0</math>, <math>\newlinef^{f(k)}(k)=k</math>
 
−
<math>\newline</math>
 
−
<math>f^m(k)=k</math>
 
−
<math>\newline</math>
 
−
<math>f^{gcd(m, 2)}=k</math>
 
−
<math>\newline</math>
 
−
<math>m=f(k)=k</math>
 
−
<math>\newline</math>
 
−
This proves Lemma 2.
 
−
<math>\newline\newline</math>
 
−
I claim that <math>f(m)=m</math> for all odd <math>m</math>.
 
−
<math>\newline</math>
 
−
Otherwise, let <math>m</math> be the least counterexample.
 
−
<math>\newline</math>
 
−
Since <math>f^2(m)\cdot f^{f(m)}(m)</math>, either
 
−
<math>\newline</math>
 
−
(1) <math>f^2(m)=k<m</math>, contradicted by Lemma 1 since <math>f(k)=k</math>.
 
−
<math>\newline</math>
 
−
(2) <math>f^{f(m)}(m)=k<m</math>, also contradicted by Lemma 1.
 
−
<math>\newline</math>
 
−
(3) <math>f^2(m)=m</math> and <math>f^{f(m)}(m)=m</math>, which implies that <math>f(m)=m</math> by Lemma 2.
 
−
This proves the claim.
 
−
<math>\newline\newline</math>
 
−
By injectivity, <math>f(1000)</math> is not odd.
 
−
I will prove that <math>f(1000)</math> can be any even number, <math>x</math>. Let <math>f(1000)=x, f(x)=1000</math>, and <math>f(k)=k</math> for all other <math>k</math>. If <math>n</math> is equal to neither <math>1000</math> nor <math>x</math>, then <math>f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2</math>. This satisfies the given property.
 
−
<math>\newline</math>
 
−
If <math>n</math> is equal to <math>1000</math> or <math>x</math>, then <math>f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2</math> since <math>f(n)</math> is even and <math>f^2(n)=n</math>. This satisfies the given property.
 
−
<math>\newline</math>
 
  
  

Revision as of 20:46, 24 April 2019

Problem

Let $\mathbb{N}$ be the set of positive integers. A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the equation \[\underbrace{f(f(\ldots f}_{f(n)\text{ times}}(n)\ldots))=\frac{n^2}{f(f(n))}\]for all positive integers $n$. Given this information, determine all possible values of $f(1000)$.

Solution

$\newline$ Let $f^r(x)$ denote the resulr when $f$ is applied to $x$ $r$ times. $\newline\newline$ If $f(p)=f(q)$, then $f^2(p)=f^2(q)$ and $f^{f(p)}(p)=f^{f(q)}(q)\newline\implies p^2=f^2(p)\cdot f^{f(p)}(p)=f^2(q)\cdot f^{f(q)}(q)=q^2\newline\implies p=\pm q\newline\implies p=q$ since $p,q>0$. \newline Therefore, $f$ is injective. $\newline\newline$ Lemma 1: If $f^r(b)=a$ and $f(a)=a$, then b=a. $\newline\newline$ Proof: $\newline$ Otherwise, set $a$, $b$, and $r$ to a counterexample of the lemma, such that $r$ is minimized. By injectivity, $f(a)=a\implies f(b)\neq a$, so $r\neq1$. If $f^n(b)=a$, then $f^n-1(f(b))=a$ and $f(b)\neq a$, a counterexample that contradicts our assumption that $r$ is minimized, proving Lemma 1. $\newline\newline$ Lemma 2: If $f^2(m)=f^{f(m)}(m)=m$, and $m$ is odd, then $f(m)=m$. $\newline\newline$ Proof: $\newline$ Let $f(m)=k$. Since $f^2(m)=m$, $f(k)=m$. So, $f^2(k)=k$. $\newline f^2(k)\cdot f^{f(k)}(k)=k^2$.$\newline$ Since $k\neq0$, $\newlinef^{f(k)}(k)=k$ (Error compiling LaTeX. Unknown error_msg) $\newline$ $f^m(k)=k$ $\newline$ $f^{gcd(m, 2)}=k$ $\newline$ $m=f(k)=k$ $\newline$ This proves Lemma 2. $\newline\newline$ I claim that $f(m)=m$ for all odd $m$. $\newline$ Otherwise, let $m$ be the least counterexample. $\newline$ Since $f^2(m)\cdot f^{f(m)}(m)$, either $\newline$ (1) $f^2(m)=k<m$, contradicted by Lemma 1 since $f(k)=k$. $\newline$ (2) $f^{f(m)}(m)=k<m$, also contradicted by Lemma 1. $\newline$ (3) $f^2(m)=m$ and $f^{f(m)}(m)=m$, which implies that $f(m)=m$ by Lemma 2. This proves the claim. $\newline\newline$ By injectivity, $f(1000)$ is not odd. I will prove that $f(1000)$ can be any even number, $x$. Let $f(1000)=x, f(x)=1000$, and $f(k)=k$ for all other $k$. If $n$ is equal to neither $1000$ nor $x$, then $f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2$. This satisfies the given property. $\newline$ If $n$ is equal to $1000$ or $x$, then $f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2$ since $f(n)$ is even and $f^2(n)=n$. This satisfies the given property. $\newline$


The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2019 USAMO (Problems • Resources)
First Problem Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAMO_Problems/Problem_1&oldid=105489"