Difference between revisions of "2021 USAJMO Problems/Problem 1"
(→Solution 2 (Taken from Twitch Solves ISL)) |
(→Solution 2 (Taken from Twitch Solves ISL)) |
||
(18 intermediate revisions by 9 users not shown) | |||
Line 7: | Line 7: | ||
We will proceed with strong induction. The base case is simple, as plugging <math>a=1</math> into the second equation given within the problem gives <math>f(1)=f(1)^2</math>. Since <math>f(n)</math> can only return a positive integer value, we have that <math>f(1)=1</math>. | We will proceed with strong induction. The base case is simple, as plugging <math>a=1</math> into the second equation given within the problem gives <math>f(1)=f(1)^2</math>. Since <math>f(n)</math> can only return a positive integer value, we have that <math>f(1)=1</math>. | ||
− | Now we proceed with the inductive step. If the next number <math>n</math> is either a perfect square or can be represented as a sum of two perfect squares, then obviously <math>f(n)=1</math>, as it is either the product of two <math>f</math>-values that are both equal to <math>1</math> from the inductive assumption or is the square of an <math>f</math>-value that is equal to <math>1</math>, again due to the inductive assumption. Otherwise, we can use the Sum of Two Squares Theorem, which tells us that <math>n</math> has at least one prime in its prime factorization that is <math>3(mod 4)</math> and is raised to an odd power. | + | Now we proceed with the inductive step. If the next number <math>n</math> is either a perfect square or can be represented as a sum of two perfect squares, then obviously <math>f(n)=1</math>, as it is either the product of two <math>f</math>-values that are both equal to <math>1</math> from the inductive assumption or is the square of an <math>f</math>-value that is equal to <math>1</math>, again due to the inductive assumption. Otherwise, we can use the Sum of Two Squares Theorem, which tells us that <math>n</math> has at least one prime in its prime factorization that is <math>3(\mod 4)</math> and is raised to an odd power. |
Lemma 1: Given that <math>a^2+b^2=c^2</math> and <math>f(b)=f(c)=1</math>, we then have <math>f(a)=1</math>. | Lemma 1: Given that <math>a^2+b^2=c^2</math> and <math>f(b)=f(c)=1</math>, we then have <math>f(a)=1</math>. | ||
Line 29: | Line 29: | ||
==Solution 2 (Taken from Twitch Solves ISL)== | ==Solution 2 (Taken from Twitch Solves ISL)== | ||
− | The Answer is <math>\boxed{f\equiv 1}</math> which works but we want to prove that it's the only one. Claim: If <math>f(a)=f(b)=1</math> and a>b, then <math>f(a^2-b^2)= f(2ab)= 1</math>. Proof: We can write <math>1=f(a)=f(b)= f(a^2+b^2)= \sqrt{f((a^2+b^2)^2)} = \sqrt{f((a^2-b^2)^2+ (2ab)^2} = \sqrt{f(a^2-b^2)f(2ab)}</math>. We set it to <math>a=b=1</math> and we get that <math>f(1)=f(2)=1</math>. Easily by Induction it shows f(n)=1. We take if <math>n=2k</math> take <math>(u,v)=(k,1)</math> which <math>2uv=n</math>. If <math>n=2k+1</math>, just take <math>(u,v)= (k+1,k)</math> which <math>u^2-v^2=n</math>. Thus the only answer is <math>\boxed{f\equiv 1}</math> and we are done. | + | The Answer is <math>\boxed{f\equiv 1}</math> which works but we want to prove that it's the only one. Claim: If <math>f(a)=f(b)=1</math> and <math>a>b</math>, then <math>f(a^2-b^2)= f(2ab)= 1</math>. Proof: We can write <math>1=f(a)=f(b)= f(a^2+b^2)= \sqrt{f((a^2+b^2)^2)} = \sqrt{f((a^2-b^2)^2+ (2ab)^2)} = \sqrt{f(a^2-b^2)f(2ab)}</math>. We set it to <math>a=b=1</math> and we get that <math>f(1)=f(2)=1</math>. Easily by Induction it shows f(n)=1. We take if <math>n=2k</math> take <math>(u,v)=(k,1)</math> which <math>2uv=n</math>. If <math>n=2k+1</math>, just take <math>(u,v)= (k+1,k)</math> which <math>u^2-v^2=n</math>. Thus the only answer is <math>\boxed{f\equiv 1}</math> and we are done. |
==Solution 3 (clear Solution 2)== | ==Solution 3 (clear Solution 2)== | ||
Line 37: | Line 37: | ||
The following claim finishes the problem via induction: | The following claim finishes the problem via induction: | ||
+ | |||
Claim: If <math>f(n)=f(n-1)=1</math> for <math>n \ge 2</math>, we have <math>f(2n)=f(2n-1)=1</math>. | Claim: If <math>f(n)=f(n-1)=1</math> for <math>n \ge 2</math>, we have <math>f(2n)=f(2n-1)=1</math>. | ||
− | Proof: | + | |
− | Note that <math>f(n^2+1)=f(n)f(1)=1</math>, so <cmath>1=f(n^2+1)^2 = f((n^2+1)^2)=f(2n)f(n^2 -1)</cmath> implies <math>f(2n)=1</math>. | + | Proof: Note that <math>f(n^2+1)=f(n)f(1)=1</math>, so <cmath>1=f(n^2+1)^2 = f((n^2+1)^2)=f(2n)f(n^2 -1)</cmath> implies <math>f(2n)=1</math>. |
+ | |||
Note that <math>f(2n^2 -2n+1)=f(n)f(n-1)=1</math>, so <cmath>1=f(2n^2 - 2n+1)^2 = f((2n^2-2n+1)^2)=f(2n-1)f(2n^2 -2n)</cmath> implies <math>f(2n-1)=1</math>. <math>\square</math> | Note that <math>f(2n^2 -2n+1)=f(n)f(n-1)=1</math>, so <cmath>1=f(2n^2 - 2n+1)^2 = f((2n^2-2n+1)^2)=f(2n-1)f(2n^2 -2n)</cmath> implies <math>f(2n-1)=1</math>. <math>\square</math> | ||
Thus, the only solution is <math>\boxed{f\equiv 1}</math>. | Thus, the only solution is <math>\boxed{f\equiv 1}</math>. | ||
+ | ==Video Solution by the Power of Logic== | ||
+ | https://www.youtube.com/watch?v=Q1NUBUYvOJc | ||
+ | |||
+ | ~The Power of Logic | ||
== See Also == | == See Also == | ||
{{USAJMO newbox|year=2021|before=First Question |num-a=2}} | {{USAJMO newbox|year=2021|before=First Question |num-a=2}} |
Latest revision as of 18:07, 19 August 2024
Contents
Problem
Let denote the set of positive integers. Find all functions
such that for positive integers
and
Solution
I claim that the only function that satisfies the constraints outlined within the problem is the function
for all positive integers
.
We will proceed with strong induction. The base case is simple, as plugging into the second equation given within the problem gives
. Since
can only return a positive integer value, we have that
.
Now we proceed with the inductive step. If the next number is either a perfect square or can be represented as a sum of two perfect squares, then obviously
, as it is either the product of two
-values that are both equal to
from the inductive assumption or is the square of an
-value that is equal to
, again due to the inductive assumption. Otherwise, we can use the Sum of Two Squares Theorem, which tells us that
has at least one prime in its prime factorization that is
and is raised to an odd power.
Lemma 1: Given that and
, we then have
.
Proof: Note that the first condition in the problem tells us that , or
. Using the second condition gives us
. Plugging in the values of
and
gives us that
.
Now we will attempt to repeatedly remove prime factors that are and taken to an odd power, and we will move from the largest prime down to the smallest prime that satisfies above conditions. The prime factors will be removed by constructing a Pythagorean Triple with the prime being the smallest leg in the form of
(this will always work as
(not 3 mod 4), and this method works via Lemma 1). We will then prove the ending numbers that we achieve via removing all the
primes(which I will refer to as "tips") are equal to 1 b/c they can be expressed as the sum of two squares or is a perfect square(Sum of Two Squares Theorem). For example, if we took the number
, we would first aim to remove the
by splitting it into
and
, so
would become
and
.
is divisible by
to an odd power, so we transform it into
and
. These two don't have any divisors that are
raised to an odd power so we leave it alone, as sum of two squares will work on them or they are perfect squares.
does have a prime factor that is
, but it is an even power so we leave it alone. In this case, the tips are
,
, and
. However, now we need to prove two key facts: using this Pythagorean Triple Method will never generate another
prime that is bigger than the current one we are working on or create more primes or keep the same number of primes in the tips' prime factorizations., as otherwise it could cause an infinite cycle, and also we must prove when we use Sum of Two Squares/Perfect Square given in the second condition on the tips the square root of the square(s) used will never be greater than or equal to
.
The first claim can be proved rather simply. Note that can have no prime factors greater than or equal to
, as it can be factored as
, which are both less than
and are integers(
must be an integer due to
must being odd(not equal to
)). For
, we can prove something a bit more general.
Lemma 2: For any positive integer , all prime factors of
must be
.
Proof: Note that if , then we also must have
, or
. Now we can apply Fermat's Little Theorem to obtain
. Note that since
and
are obviously not
, as
, we have that
is a multiple of
, or
.
We can simply apply Lemma 2 to as
is obviously not
, and this means that a prime factor
will never be generated from this term. This completes the first of our two claims.
Now we proceed to the second of our two claims. Note that every time we use the method on based on prime
, we will multiply by around
, clearly less than
(if we multiply by
we would get
which is clearly greater than
). We will never have to use the same prime twice in our method, so at max in the end we will multiply
by the product of a little less than all
primes that divide it, which is less than
itself for
greater than or equal to
(the smallest 3 mod 4 prime), meaning that the largest number that we must use two squares on that is generated by out method is less than
. We need to prove that the two squares that sum to this are both less than
, which is quite trivial, as they are less than
, which obviously means it must be less than
. This proves the second of our claims.
This completes the second case of the inductive step, and therefore completes both the induction and the problem. ~Solution by hyxue
Solution 2 (Taken from Twitch Solves ISL)
The Answer is which works but we want to prove that it's the only one. Claim: If
and
, then
. Proof: We can write
. We set it to
and we get that
. Easily by Induction it shows f(n)=1. We take if
take
which
. If
, just take
which
. Thus the only answer is
and we are done.
Solution 3 (clear Solution 2)
The answer is , which works.
To show it is necessary, we first get
, so
.
Then, we get
.
The following claim finishes the problem via induction:
Claim: If for
, we have
.
Proof: Note that , so
implies
.
Note that , so
implies
.
Thus, the only solution is .
Video Solution by the Power of Logic
https://www.youtube.com/watch?v=Q1NUBUYvOJc
~The Power of Logic
See Also
2021 USAJMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.