Difference between revisions of "2014 USAMO Problems/Problem 2"
(→Solution 4) |
m (→Alternative Solution) |
||
(One intermediate revision by one other user not shown) | |||
Line 40: | Line 40: | ||
Then we can let <math>k</math> be anything except 0, and get <math>f(x)</math> is 0 for all <math>x \equiv 3 \pmod{4}</math> except <math>-m^2</math>. Also since <math>x^2f(-x) = f(x)^2</math>, we have <math>f(x) = 0 \Rightarrow f(-x) = 0</math>, so <math>f(x)</math> is 0 for all <math>x \equiv 1 \pmod{4}</math> except <math>m^2</math>. So <math>f(x)</math> is 0 for all <math>x</math> except <math>\pm m^2</math>. Since <math>f(m) \neq 0</math>, <math>m = \pm m^2</math>. Squaring, <math>m^2 = m^4</math> and dividing by <math>m</math>, <math>m = m^3</math>. Since <math>f(m^3) = 0</math>, <math>f(m) = 0</math>, which is a contradiction for <math>m \neq 1</math>. However, if we plug in <math>x = 1</math> with <math>f(1) = 1</math> and <math>y</math> as an arbitrary large number with <math>f(y) = 0</math> into the original equation, we get <math>0 = 1</math> which is a clear contradiction, so our only solutions are <math>f(x) = 0</math> and <math>f(x) = x^2</math>. | Then we can let <math>k</math> be anything except 0, and get <math>f(x)</math> is 0 for all <math>x \equiv 3 \pmod{4}</math> except <math>-m^2</math>. Also since <math>x^2f(-x) = f(x)^2</math>, we have <math>f(x) = 0 \Rightarrow f(-x) = 0</math>, so <math>f(x)</math> is 0 for all <math>x \equiv 1 \pmod{4}</math> except <math>m^2</math>. So <math>f(x)</math> is 0 for all <math>x</math> except <math>\pm m^2</math>. Since <math>f(m) \neq 0</math>, <math>m = \pm m^2</math>. Squaring, <math>m^2 = m^4</math> and dividing by <math>m</math>, <math>m = m^3</math>. Since <math>f(m^3) = 0</math>, <math>f(m) = 0</math>, which is a contradiction for <math>m \neq 1</math>. However, if we plug in <math>x = 1</math> with <math>f(1) = 1</math> and <math>y</math> as an arbitrary large number with <math>f(y) = 0</math> into the original equation, we get <math>0 = 1</math> which is a clear contradiction, so our only solutions are <math>f(x) = 0</math> and <math>f(x) = x^2</math>. | ||
− | == | + | ==Solution 2== |
− | Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and <math>f(yf(y))</math> must also be an integer, therefore <math>\frac{f(x)^2}{x}</math> is an integer. If <math>x</math> divides <math>f(x)^2</math> for all integers <math>x \ne 0</math>, then <math>x</math> must be a factor of <math>f(x)</math>, therefore <math>f(0)=0</math>. Now, by setting <math>y=0</math> in the original equation, this simplifies to <math>xf(-x)=\frac{f(x)^2}{x}</math>. Assuming <math>x \ne 0</math>, we have <math>x^2f(-x)=f(x)^2</math>. Substituting in <math>-x</math> for <math>x</math> gives us <math>x^2f(x)=f(-x)^2</math>. Substituting in <math>\frac{f(x)^2}{x^2}</math> in for <math>f(-x)</math> in the second equation gives us <math>x^2f(x)=\frac{f(x)^4}{x^4}</math>, so <math>x^6f(x)=f(x)^4</math>. In particular, if <math>f(x) \ne 0</math>, then we have <math>f(x)^3=x^6</math>, therefore <math>f(x)</math> is equivalent to <math>0</math> or <math>x^2</math> for every integer <math>x</math>. Now, we shall prove that if for some integer <math>t \ne 0</math>, if <math>f(t)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. If we assume <math>f(y)=0</math> and <math>y \ne 0</math> in the original equation, this simplifies to <math>xf(-x)+y^2f(2x)=\frac{f(x)^2}{x}</math>. However, since <math>x^2f(-x)=f(x)^2</math>, we can rewrite this equation as <math>\frac{f(x)^2}{x}+y^2f(2x)=\frac{f(x)^2}{x}</math>, <math>y^2f(2x)</math> must therefore be equivalent to <math>0</math>. Since, by our initial assumption, <math>y \ne 0</math>, this means that <math>f(2x)=0</math>, so, if for some integer <math>y \ne 0</math>, <math>f(y)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. The contrapositive must also be true, i.e. If <math>f(x) \ne 0</math> for all integers <math>x</math>, then there is no integral value of <math>y \ne 0</math> such that <math>f(y)=0</math>, therefore <math>f(x)</math> must be equivalent for <math>x^2</math> for every integer <math>x</math>, including <math>0</math>, since <math>f(0)=0</math>. Thus, <math>f(x)=0, x^2</math> are the only possible solutions. | + | Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and <math>f(yf(y))</math> must also be an integer, therefore <math>\frac{f(x)^2}{x}</math> is an integer. If <math>x</math> divides <math>f(x)^2</math> for all integers <math>x \ne 0</math>, then <math>x</math> must be a factor of <math>f(x)</math>, therefore <math>f(0)=0</math>. Now, by setting <math>y=0</math> in the original equation, this simplifies to <math>xf(-x)=\frac{f(x)^2}{x}</math>. Assuming <math>x \ne 0</math>, we have <math>x^2f(-x)=f(x)^2</math>. Substituting in <math>-x</math> for <math>x</math> gives us <math>x^2f(x)=f(-x)^2</math>. Substituting in <math>\frac{f(x)^2}{x^2}</math> in for <math>f(-x)</math> in the second equation gives us <math>x^2f(x)=\frac{f(x)^4}{x^4}</math>, so <math>x^6f(x)=f(x)^4</math>. In particular, if <math>f(x) \ne 0</math>, then we have <math>f(x)^3=x^6</math>, therefore <math>f(x)</math> is equivalent to <math>0</math> or <math>x^2</math> for every integer <math>x</math>. Now, we shall prove that if for some integer <math>t \ne 0</math>, if <math>f(t)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. If we assume <math>f(y)=0</math> and <math>y \ne 0</math> in the original equation, this simplifies to <math>xf(-x)+y^2f(2x)=\frac{f(x)^2}{x}</math>. However, since <math>x^2f(-x)=f(x)^2</math>, we can rewrite this equation as <math>\frac{f(x)^2}{x}+y^2f(2x)=\frac{f(x)^2}{x}</math>, <math>y^2f(2x)</math> must therefore be equivalent to <math>0</math>. Since, by our initial assumption, <math>y \ne 0</math>, this means that <math>f(2x)=0</math>, so, if for some integer <math>y \ne 0</math>, <math>f(y)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. The contrapositive must also be true, i.e. If <math>f(x) \ne 0</math> for all integers <math>x</math>, then there is no integral value of <math>y \ne 0</math> such that <math>f(y)=0</math>, therefore <math>f(x)</math> must be equivalent for <math>x^2</math> for every integer <math>x</math>, including <math>0</math>, since <math>f(0)=0</math>. Thus, <math>f(x)=0, x^2</math> are the only possible solutions. |
==Solution 3== | ==Solution 3== | ||
Line 59: | Line 59: | ||
==Solution 4== | ==Solution 4== | ||
− | Let the given assertion be <math>P(x, y)</math>. We try <math>P(x, 0)</math> and get <math>xf(2c-x)=f(x)^2/x+c</math>, where <math>f(0)=c</math>. We plug in <math>x=c</math> and get <math>cf(c)=f(c)^2/c+c</math>. Rearranging and solving for <math>c^2</math> gives us <math>c^2=\frac{f(c)^2}{f(c)-1}</math>. Obviously, the only <math>c</math> that works such that the RHS is an integer is <math>c=0</math>, and thus <math>f(0)=0</math>. | + | Let the given assertion be <math>P(x, y)</math>. We try <math>P(x, 0)</math> and get <math>xf(2c-x)=f(x)^2/x+c</math>, where <math>f(0)=c</math>. We plug in <math>x=c</math> and get <math>cf(c)=f(c)^2/c+c</math>. Rearranging and solving for <math>c^2</math> gives us <math>c^2=\frac{f(c)^2}{f(c)-1}</math>. Obviously, the only <math>c</math> that works such that the RHS is an integer is <math>c=0</math>, and thus <math>f(0)=0</math>. |
We use this information on assertion <math>P(x,0)</math> and obtain <math>xf(-x)=f(x^2)/x</math>, or <math>f(-x)=\frac{f(x)^2}{x^2}</math>. Thus, <math>f(x)</math> is an even function. It follows that <math>f(x)=0, x^2</math> for each <math>x</math>. We now prove that <math>f(x)=x^2</math>, f(x)=0$ are the only solutions. [in progress] ~SigmaPiE | We use this information on assertion <math>P(x,0)</math> and obtain <math>xf(-x)=f(x^2)/x</math>, or <math>f(-x)=\frac{f(x)^2}{x^2}</math>. Thus, <math>f(x)</math> is an even function. It follows that <math>f(x)=0, x^2</math> for each <math>x</math>. We now prove that <math>f(x)=x^2</math>, f(x)=0$ are the only solutions. [in progress] ~SigmaPiE |
Latest revision as of 12:41, 3 March 2024
Problem
Let be the set of integers. Find all functions
such that
for all
with
.
Solution
Note: This solution is kind of rough. I didn't want to put my 7-page solution all over again. It would be nice if someone could edit in the details of the expansions.
Lemma 1: .
Proof: Assume the opposite for a contradiction. Plug in
(because we assumed that
),
. What you get eventually reduces to:
which is a contradiction since the LHS is divisible by 2 but not 4.
Then plug in into the original equation and simplify by Lemma 1. We get:
Then:
Therefore, must be 0 or
.
Now either is
for all
or there exists
such that
. The first case gives a valid solution. In the second case, we let
in the original equation and simplify to get:
But we know that
, so:
Since
is not 0,
is 0 for all
(including 0). Now either
is 0 for all
, or there exists some
such that
. Then
must be odd. We can let
in the original equation, and since
is 0 for all
, stuff cancels and we get:
for
.
Now, let
and we get:
Now, either both sides are 0 or both are equal to
. If both are
then:
which simplifies to:
Since
and
is odd, both cases are impossible, so we must have:
Then we can let
be anything except 0, and get
is 0 for all
except
. Also since
, we have
, so
is 0 for all
except
. So
is 0 for all
except
. Since
,
. Squaring,
and dividing by
,
. Since
,
, which is a contradiction for
. However, if we plug in
with
and
as an arbitrary large number with
into the original equation, we get
which is a clear contradiction, so our only solutions are
and
.
Solution 2
Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and must also be an integer, therefore
is an integer. If
divides
for all integers
, then
must be a factor of
, therefore
. Now, by setting
in the original equation, this simplifies to
. Assuming
, we have
. Substituting in
for
gives us
. Substituting in
in for
in the second equation gives us
, so
. In particular, if
, then we have
, therefore
is equivalent to
or
for every integer
. Now, we shall prove that if for some integer
, if
, then
for all integers
. If we assume
and
in the original equation, this simplifies to
. However, since
, we can rewrite this equation as
,
must therefore be equivalent to
. Since, by our initial assumption,
, this means that
, so, if for some integer
,
, then
for all integers
. The contrapositive must also be true, i.e. If
for all integers
, then there is no integral value of
such that
, therefore
must be equivalent for
for every integer
, including
, since
. Thus,
are the only possible solutions.
Solution 3
Let's assume Substitute
to get
This means that is a perfect square. However, this is impossible, as it is equivalent to
Therefore,
Now substitute
to get
Similarly,
From these two equations, we can find either
or
Both of these are valid solutions on their own, so let's see if there are any solutions combining the two.
Let's say we can find and
Then
(NEEDS FIXING:
, so the RHS is
instead of
.)
If then
which is only possible when
This contradicts our assumption. Therefore,
This forces
due to the right side of the equation. Let's consider the possibility
Substituting
into the original equation yields
which is impossible. So
and there are no solutions "combining"
and
Therefore our only solutions are and
Solution 4
Let the given assertion be . We try
and get
, where
. We plug in
and get
. Rearranging and solving for
gives us
. Obviously, the only
that works such that the RHS is an integer is
, and thus
.
We use this information on assertion and obtain
, or
. Thus,
is an even function. It follows that
for each
. We now prove that
, f(x)=0$ are the only solutions. [in progress] ~SigmaPiE