2019 USAMO Problems/Problem 1

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

\usepackage{amsmath}

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

2019 USAMO (Problems • Resources)
First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2019 USAMO Problems/Problem 1

Problem

Solution

See also