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"

m (remove name reveal of myself)
Line 1: Line 1:
−
'''''Problem:'''''
+
==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
 
''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>''
 
''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 <math>0</math> in for <math>a</math> to get
 
Let us substitute <math>0</math> in for <math>a</math> to get
Line 17: Line 17:
 
(This solution does not work though because we don't know that <math>f</math> is surjective)
 
(This solution does not work though because we don't know that <math>f</math> is surjective)
  
−
'''Solution 2:'''
+
==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 27: Line 28:
 
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 one that actually works'''
+
==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>
 
The only solutions are <math>f(x)=0, 2x+c.</math> For some integer <math>c.</math>
  
Line 34: Line 35:
 
~ LLL2019 (first to post correct solution on here)
 
~ LLL2019 (first to post correct solution on here)
  
−
'''Solution 4: This works as well'''
+
==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>
 
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
 
~ Ezra Guerrero

Revision as of 03:13, 21 July 2022

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_IMO_Problems/Problem_1&oldid=176091"