Difference between revisions of "2014 USAMO Problems/Problem 2"
(→Alternative Solution) |
(→Alternative Solution) |
||
Line 39: | Line 39: | ||
==Alternative Solution== | ==Alternative Solution== | ||
− | 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)=0, x^2</math> for every <math>x</math>. Now, we just have to 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}. However, since < | + | 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)=0, x^2</math> for every <math>x</math>. Now, we just have to 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. |
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] | ||
[[Category:Functional Equation Problems]] | [[Category:Functional Equation Problems]] |
Revision as of 12:05, 4 January 2019
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:
[b]for
.[/b]
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
.
Alternative Solution
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
for every
. Now, we just have to 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.