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 32: Line 32:
 
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.
 
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.
  
−
~ Lincoln Liu (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'''

Revision as of 08:41, 18 April 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=173421"