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.)
 
(→‎Problem)
 
(10 intermediate revisions by 6 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 one that actually works ==
 +
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.
 +
 
 +
~ LLL2019 (first to post correct solution on here)
 +
 
 +
==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 15:46, 17 April 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 one that actually works

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.

~ LLL2019 (first to post correct solution on here)

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

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=218275"