Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(This is Problem 1 of the 2019 IMO along with one solution. Please feel free to add more solutions which may be more elegant, and to correct this one if it is deemed incorrect.)
 
(→‎Solution 5)
 
(15 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
'''''Problem:'''''
+
==Problem==
  
−
''Let Z be the set of integers. Determine all functions f : Z → Z such that, for all
+
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 a and b, f(2a) + 2f(b) = f(f(a + b))''
+
integers <math>a</math> and <math>b</math>, <cmath>f(2a) + 2f(b) = f(f(a + b)).</cmath>
  
−
'''Solution 1:'''
+
==Solution 1 ==
  
−
Let us substitute 0 in for a to get:
+
Let us substitute <math>0</math> in for <math>a</math> to get
−
f(0) + 2f(b) = f(f(b))  
+
<cmath>f(0) + 2f(b) = f(f(b)).</cmath>
  
−
Now, let x = f(b) to get and f(0) equal some constant c:
+
Now, since the domain and range of <math>f</math> are the same, we can let <math>x = f(b)</math> and <math>f(0)</math> equal some constant <math>c</math> to get
−
c + 2x = f(x).
+
<cmath>c + 2x = f(x).</cmath>
−
Therefore, we have found that '''all''' solutions must be of the form f(x) = 2x + c.
+
Therefore, we have found that '''all''' solutions must be of the form <math>f(x) = 2x + c.</math>
  
−
Plugging back into the original equation, we have: 4a + c + 4b + 2c = 4a + 4b + 2c + c which is true. Therefore, we know that f(x) = 2x + c 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
 +
<cmath>f(2x)+2f(-x)=f(f(0)),</cmath>
 +
<cmath>f(2(x+k))+2f(-(x+k))=f(f(0)),</cmath>
 +
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. (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>
 +
 
 +
==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
 +
==Solution 5==
 +
 
 +
We all know how to solve a functional equation (unless you haven’t learned about it). We just plug in some trivial values and see where it takes us. Alright if <math>a=0</math>, this means <cmath>f(0)+2f(b)=f(f(b))</cmath> We know that <math>f(0)</math> is constant and we can see that <math>f(b)</math> is not constant (because it varies depends on the value of b), so let <math>f(b)</math> be a variable. This means we are making this a function of f(b). This yields that <cmath>f((f(b)))=2(f(b))+f(0)</cmath>. This is a linear function (in terms of f(b))! However, we are not done yet. We have to show that this works. When <math>b=0</math> and plugging in our function yields: <cmath>4a+2f(0)= f(f(a) \implies 4a+2f(0)= f(2a+f(0)) \implies 4a+2f(0)=4a+2f(0)</cmath> and the last part is indeed true so we are good. Don’t forget the 0 function this works also. Let us verify that the 0 function works. This means <math>0+0=0</math>, which is true and a so called “trivial” solution. Now let us prove this rigorously. Take <math>(a,b)</math> when they equal <math>(-1,x)</math> and <math>(0,x-1)</math> (I chose it that way since they are 1 apart from each other; Really you could have chosen <math>(y,x)</math> and <math>(y+1,x-1)</math> and that would work). We will show that this is linear or below. Substitute in the equations for both yields <cmath> f(0)+2f(x-1)=f(f(x-1)) \qquad \text{and} \qquad f(-1)+ 2f(x)=f(f(x-1))</cmath> Equating and then subtracting yields <cmath>2(f(x)-f(x-1))=f(0)-f(-1)</cmath>. From this equation how do we know this is linear? Well treat the f(x) and f(x-1) like variables and dividing by two we can see that <math>(f(-1)-f(0))/2</math> is constant since -1 and 0 are fixed values. And since the difference is constant and <math>x</math> and <math>x-1</math> are one apart this tells you that it is a linear function as the difference is constant, i.e 5x+4 is linear since the first positive x’s yields are 4, 9, 14… and we can see the difference is the same. Therefore we proved that the functions we said are good.
 +
 
 +
Side note: I am referring to the linear function <math>2x+b</math> where <math>b \in \mathbb{R}</math> and the constant function which is <math>0</math>.
 +
 
 +
~EaZ_Shadow
 +
 
 +
==See Also==
 +
 
 +
{{IMO box|year=2019|before=First Problem|num-a=2}}

Latest revision as of 21:17, 15 October 2024

Problem

Let $\mathbb{Z}$ be the set of integers. Determine all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that, for all integers $a$ and $b$, \[f(2a) + 2f(b) = f(f(a + b)).\]

Solution 1

Let us substitute $0$ in for $a$ to get \[f(0) + 2f(b) = f(f(b)).\]

Now, since the domain and range of $f$ are the same, we can let $x = f(b)$ and $f(0)$ equal some constant $c$ to get \[c + 2x = f(x).\] Therefore, we have found that all solutions must be of the form $f(x) = 2x + c.$

Plugging back into the original equation, we have: $4a + c + 4b + 2c = 4a + 4b + 2c + c$ which is true. Therefore, we know that $f(x) = 2x + c$ 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 $f$ is surjective)

Solution 2

We plug in $a=-b=x$ and $a=-b=x+k$ to get \[f(2x)+2f(-x)=f(f(0)),\] \[f(2(x+k))+2f(-(x+k))=f(f(0)),\] respectively.

Setting them equal to each other, we have the equation \[f(2x)+2f(-x)=f(2(x+k))+2f(-(x+k)),\] and moving "like terms" to one side of the equation yields \[f(2(x+k))-f(2x)=2f(-x)-2f(-(x+k)).\] Seeing that this is a difference of outputs of $f,$ we can relate this to slope by dividing by $2k$ on both sides. This gives us \[\frac{f(2x+2k)-f(2x)}{2k}=\frac{f(-x)-f(-x-k)}{k},\] which means that $f$ is linear. (Functional equations don't work like that unfortunately)

Let $f(x)=mx+n.$ Plugging our expression into our original equation yields $2ma+2mb+3n=m^2a+m^2b+mn+n,$ and letting $b$ be constant, this can only be true if $2m=m^2 \implies m=0,2.$ If $m=0,$ then $n=0,$ which implies $f(x)=0.$ However, the output is then not all integers, so this doesn't work. If $m=2,$ we have $f(x)=2x+n.$ Plugging this in works, so the answer is $f(x)=2x+c$ for some integer $c.$

Solution 3:

The only solutions are $f(x)=0, 2x+c.$ For some integer $c.$

Obviously these work. We prove these are the only linear solutions. Plug $a=0$ and $b=0$ separately to get that $f(2x)=2f(x)-f(0).$ Plug $(0, a+b)$ to see $f(0)+f(a+b)=f(a)+f(b),$ and subtracting $2f(0)$ from both sides shows $f(a)-f(0)$ to be additive thus linear by Cauchy since this is on integers. Thus, $f(a)$ is linear, and so we are done since it can be easily shown that $0$ and $2x+c$ are the only linear solutions by plugging $mx+n$ into the equation.


Solution 4: This works as well

We claim the only solutions are $f\equiv0$ and $f(x)=2x+c$ for some integer $c$., which obviously work. Plugging in $(0,n)$ and $(1,n-1)$ give $f(0)+2f(n)=f(f(n))=f(2)+2f(n-1)$, so $f(n)-f(n-1)=\frac{f(2)-f(0)}2$. Since this difference is constant and $f\colon\mathbb Z\rightarrow\mathbb Z$, we must have $f$ is linear (finite differences or induction). It is easy to see the only linear solutions are those specified above. $\blacksquare$

~ Ezra Guerrero

Solution 5

We all know how to solve a functional equation (unless you haven’t learned about it). We just plug in some trivial values and see where it takes us. Alright if $a=0$, this means \[f(0)+2f(b)=f(f(b))\] We know that $f(0)$ is constant and we can see that $f(b)$ is not constant (because it varies depends on the value of b), so let $f(b)$ be a variable. This means we are making this a function of f(b). This yields that \[f((f(b)))=2(f(b))+f(0)\]. This is a linear function (in terms of f(b))! However, we are not done yet. We have to show that this works. When $b=0$ and plugging in our function yields: \[4a+2f(0)= f(f(a) \implies 4a+2f(0)= f(2a+f(0)) \implies 4a+2f(0)=4a+2f(0)\] and the last part is indeed true so we are good. Don’t forget the 0 function this works also. Let us verify that the 0 function works. This means $0+0=0$, which is true and a so called “trivial” solution. Now let us prove this rigorously. Take $(a,b)$ when they equal $(-1,x)$ and $(0,x-1)$ (I chose it that way since they are 1 apart from each other; Really you could have chosen $(y,x)$ and $(y+1,x-1)$ and that would work). We will show that this is linear or below. Substitute in the equations for both yields \[f(0)+2f(x-1)=f(f(x-1)) \qquad \text{and} \qquad f(-1)+ 2f(x)=f(f(x-1))\] Equating and then subtracting yields \[2(f(x)-f(x-1))=f(0)-f(-1)\]. From this equation how do we know this is linear? Well treat the f(x) and f(x-1) like variables and dividing by two we can see that $(f(-1)-f(0))/2$ is constant since -1 and 0 are fixed values. And since the difference is constant and $x$ and $x-1$ are one apart this tells you that it is a linear function as the difference is constant, i.e 5x+4 is linear since the first positive x’s yields are 4, 9, 14… and we can see the difference is the same. Therefore we proved that the functions we said are good.

Side note: I am referring to the linear function $2x+b$ where $b \in \mathbb{R}$ and the constant function which is $0$.

~EaZ_Shadow

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_IMO_Problems/Problem_1&oldid=229978"