Difference between revisions of "2019 USAMO Problems/Problem 1"

Latest revision as of 17:04, 5 April 2021

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

Let $f^r(x)$ denote the result when $f$ is applied to $f^{r-1}(x)$ , where $f^1(x)=f(x)$ . $\hfill \break \hfill \break$ If $f(p)=f(q)$ , then $f^2(p)=f^2(q)$ and $f^{f(p)}(p)=f^{f(q)}(q)$

$\implies p^2=f^2(p)\cdot f^{f(p)}(p)=f^2(q)\cdot f^{f(q)}(q)=q^2$

$\implies p=\pm q$

$\implies p=q$ since $p,q>0$ .

Therefore, $f$ is injective. It follows that $f^r$ is also injective.

Lemma 1: If $f^r(b)=a$ and $f(a)=a$ , then $b=a$ .

Proof:

$f^r(b)=a=f^r(a)$ which implies $b=a$ by injectivity of $f^r$ .

Lemma 2: If $f^2(m)=f^{f(m)}(m)=m$ , and $m$ is odd, then $f(m)=m$ .

Proof:

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

Since $k\neq0$ , $f^{f(k)}(k)=k$

$\implies f^m(k)=k$

$\implies f^{gcd(m, 2)}(k)=k$

$\implies f(k)=k$

This proves Lemma 2.

I claim that $f(m)=m$ for all odd $m$ .

Otherwise, let $m$ be the least counterexample.

Since $f^2(m)\cdot f^{f(m)}(m)=m^2$ , either

$(1) f^2(m)=k<m$ , contradicted by Lemma 1 since $k$ is odd and $f^2(k)=k$ .

$(2) f^{f(m)}(m)=k<m$ , also contradicted by Lemma 1 by similar logic.

$(3) f^2(m)=m$ and $f^{f(m)}(m)=m$ , which implies that $f(m)=m$ by Lemma 2. This proves the claim.

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.

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.

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

@@ Line 3: / Line 3: @@
 ==Solution==
-\usepackage{amsmath}
-<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.
+Let <math>f^r(x)</math> denote the result when <math>f</math> is applied to <math>f^{r-1}(x)</math>, where <math>f^1(x)=f(x)</math>.
-<math>\newline\newline</math>
+<math>\hfill \break \hfill \break</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>.
+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)</math>
-\newline
-Therefore, <math>f</math> is injective.
+<math>\implies p^2=f^2(p)\cdot f^{f(p)}(p)=f^2(q)\cdot f^{f(q)}(q)=q^2</math>
-<math>\newline\newline</math>
-Lemma 1: If <math>f^r(b)=a</math> and <math>f(a)=a</math>, then b=a.
+<math>\implies p=\pm q</math>
-<math>\newline\newline</math>
+<math>\implies p=q</math> since <math>p,q>0</math>.
+Therefore, <math>f</math> is injective. It follows that <math>f^r</math> is also injective.
+Lemma 1: If <math>f^r(b)=a</math> and <math>f(a)=a</math>, then <math>b=a</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>f^r(b)=a=f^r(a)</math> which implies <math>b=a</math> by injectivity of <math>f^r</math>.
-<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>
-<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>
+Since <math>k\neq0</math>, <math>f^{f(k)}(k)=k</math>
-<math>\newline</math>
-<math>f^m(k)=k</math>
+<math>\implies f^m(k)=k</math>
-<math>\newline</math>
-<math>f^{gcd(m, 2)}=k</math>
+<math>\implies f^{gcd(m, 2)}(k)=k</math>
-<math>\newline</math>
-<math>m=f(k)=k</math>
+<math>\implies 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
+Since <math>f^2(m)\cdot f^{f(m)}(m)=m^2</math>, either
-<math>\newline</math>
-(1) <math>f^2(m)=k<m</math>, contradicted by Lemma 1 since <math>f(k)=k</math>.
+<math>(1) f^2(m)=k<m</math>, contradicted by Lemma 1 since <math>k</math> is odd and <math>f^2(k)=k</math>.
-<math>\newline</math>
-(2) <math>f^{f(m)}(m)=k<m</math>, also contradicted by Lemma 1.
+<math>(2) f^{f(m)}(m)=k<m</math>, also contradicted by Lemma 1 by similar logic.
-<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.
+<math>(3) 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>

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

Page

Toolbox

Search

Difference between revisions of "2019 USAMO Problems/Problem 1"

Latest revision as of 17:04, 5 April 2021

Problem

Solution

See also