Difference between revisions of "2019 IMO Problems/Problem 1"
(Fixed up latex. Fixed error in solution 2.) |
Aiden22gao (talk | contribs) m |
||
(9 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | + | ==Problem== | |
− | + | Let <math>\mathbb{Z}</math> be the set of integers. Determine all functions <math>f : \mathbb{Z} \to \mathbb{Z}</math> such that, for all | |
− | + | integers <math>a</math> and <math>b</math>, <cmath>f(2a) + 2f(b) = f(f(a + b)).</cmath> | |
− | + | ==Solution 1 == | |
Let us substitute <math>0</math> in for <math>a</math> to get | Let us substitute <math>0</math> in for <math>a</math> to get | ||
Line 15: | Line 15: | ||
Plugging back into the original equation, we have: <math>4a + c + 4b + 2c = 4a + 4b + 2c + c</math> which is true. Therefore, we know that <math>f(x) = 2x + c</math> satisfies the above for any '''integral''' constant c, and that this family of equations is unique. | Plugging back into the original equation, we have: <math>4a + c + 4b + 2c = 4a + 4b + 2c + c</math> which is true. Therefore, we know that <math>f(x) = 2x + c</math> satisfies the above for any '''integral''' constant c, and that this family of equations is unique. | ||
− | ' | + | (This solution does not work though because we don't know that <math>f</math> is surjective) |
+ | |||
+ | ==Solution 2 == | ||
+ | |||
We plug in <math>a=-b=x</math> and <math>a=-b=x+k</math> to get | We plug in <math>a=-b=x</math> and <math>a=-b=x+k</math> to get | ||
<cmath>f(2x)+2f(-x)=f(f(0)),</cmath> | <cmath>f(2x)+2f(-x)=f(f(0)),</cmath> | ||
Line 21: | Line 24: | ||
respectively. | respectively. | ||
− | Setting them equal to each other, we have the equation <cmath>f(2x)+2f(-x)=f(2(x+k))+2f(-(x+k)),</cmath> and moving "like terms" to one side of the equation yields <cmath>f(2(x+k))-f(2x)=2f(-x)-2f(-(x+k)).</cmath> Seeing that this is a difference of outputs of <math>f,</math> we can relate this to slope by dividing by <math>2k</math> on both sides. This gives us <cmath>\frac{f(2x+2k)-f(2x)}{2k}=\frac{f(-x)-f(-x-k)}{k},</cmath> which means that <math>f</math> is linear. | + | Setting them equal to each other, we have the equation <cmath>f(2x)+2f(-x)=f(2(x+k))+2f(-(x+k)),</cmath> and moving "like terms" to one side of the equation yields <cmath>f(2(x+k))-f(2x)=2f(-x)-2f(-(x+k)).</cmath> Seeing that this is a difference of outputs of <math>f,</math> we can relate this to slope by dividing by <math>2k</math> on both sides. This gives us <cmath>\frac{f(2x+2k)-f(2x)}{2k}=\frac{f(-x)-f(-x-k)}{k},</cmath> which means that <math>f</math> is linear. (Functional equations don't work like that unfortunately) |
Let <math>f(x)=mx+n.</math> Plugging our expression into our original equation yields <math>2ma+2mb+3n=m^2a+m^2b+mn+n,</math> and letting <math>b</math> be constant, this can only be true if <math>2m=m^2 \implies m=0,2.</math> If <math>m=0,</math> then <math>n=0,</math> which implies <math>f(x)=0.</math> However, the output is then not all integers, so this doesn't work. If <math>m=2,</math> we have <math>f(x)=2x+n.</math> Plugging this in works, so the answer is <math>f(x)=2x+c</math> for some integer <math>c.</math> | Let <math>f(x)=mx+n.</math> Plugging our expression into our original equation yields <math>2ma+2mb+3n=m^2a+m^2b+mn+n,</math> and letting <math>b</math> be constant, this can only be true if <math>2m=m^2 \implies m=0,2.</math> If <math>m=0,</math> then <math>n=0,</math> which implies <math>f(x)=0.</math> However, the output is then not all integers, so this doesn't work. If <math>m=2,</math> we have <math>f(x)=2x+n.</math> Plugging this in works, so the answer is <math>f(x)=2x+c</math> for some integer <math>c.</math> | ||
+ | |||
+ | ==Solution 3:== | ||
+ | The only solutions are <math>f(x)=0, 2x+c.</math> For some integer <math>c.</math> | ||
+ | |||
+ | Obviously these work. We prove these are the only linear solutions. Plug <math>a=0</math> and <math>b=0</math> separately to get that <math>f(2x)=2f(x)-f(0).</math> Plug <math>(0, a+b)</math> to see <math>f(0)+f(a+b)=f(a)+f(b),</math> and subtracting <math>2f(0)</math> from both sides shows <math>f(a)-f(0)</math> to be additive thus linear by Cauchy since this is on integers. Thus, <math>f(a)</math> is linear, and so we are done since it can be easily shown that <math>0</math> and <math>2x+c</math> are the only linear solutions by plugging <math>mx+n</math> into the equation. | ||
+ | |||
+ | |||
+ | |||
+ | ==Solution 4: This works as well == | ||
+ | We claim the only solutions are <math>f\equiv0</math> and <math>f(x)=2x+c</math> for some integer <math>c</math>., which obviously work. Plugging in <math>(0,n)</math> and <math>(1,n-1)</math> give <math>f(0)+2f(n)=f(f(n))=f(2)+2f(n-1)</math>, so <math>f(n)-f(n-1)=\frac{f(2)-f(0)}2</math>. Since this difference is constant and <math>f\colon\mathbb Z\rightarrow\mathbb Z</math>, we must have <math>f</math> is linear (finite differences or induction). It is easy to see the only linear solutions are those specified above. <math>\blacksquare</math> | ||
+ | |||
+ | ~ Ezra Guerrero | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2019|before=First Problem|num-a=2}} |
Latest revision as of 01:42, 4 May 2024
Contents
Problem
Let be the set of integers. Determine all functions
such that, for all
integers
and
,
Solution 1
Let us substitute in for
to get
Now, since the domain and range of are the same, we can let
and
equal some constant
to get
Therefore, we have found that all solutions must be of the form
Plugging back into the original equation, we have: which is true. Therefore, we know that
satisfies the above for any integral constant c, and that this family of equations is unique.
(This solution does not work though because we don't know that is surjective)
Solution 2
We plug in and
to get
respectively.
Setting them equal to each other, we have the equation and moving "like terms" to one side of the equation yields
Seeing that this is a difference of outputs of
we can relate this to slope by dividing by
on both sides. This gives us
which means that
is linear. (Functional equations don't work like that unfortunately)
Let Plugging our expression into our original equation yields
and letting
be constant, this can only be true if
If
then
which implies
However, the output is then not all integers, so this doesn't work. If
we have
Plugging this in works, so the answer is
for some integer
Solution 3:
The only solutions are For some integer
Obviously these work. We prove these are the only linear solutions. Plug and
separately to get that
Plug
to see
and subtracting
from both sides shows
to be additive thus linear by Cauchy since this is on integers. Thus,
is linear, and so we are done since it can be easily shown that
and
are the only linear solutions by plugging
into the equation.
Solution 4: This works as well
We claim the only solutions are and
for some integer
., which obviously work. Plugging in
and
give
, so
. Since this difference is constant and
, we must have
is linear (finite differences or induction). It is easy to see the only linear solutions are those specified above.
~ Ezra Guerrero
See Also
2019 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |