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 "2014 USAMO Problems/Problem 2"

(→‎Alternative Solution)
(→‎Alternative Solution)
Line 39: Line 39:
  
 
==Alternative Solution==
 
==Alternative Solution==
−
Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and <math>f(yf(y))</math> must also be an integer, therefore <math>\frac{f(x)^2}{x}</math> is an integer. If <math>x</math> divides <math>f(x)^2</math> for all integers <math>x \ne 0</math>, then <math>x</math> must be a factor of <math>f(x)</math>, therefore <math>f(0)=0</math>. Now, by setting <math>y=0</math> in the original equation, this simplifies to <math>xf(-x)=\frac{f(x)^2}{x}</math>. Assuming <math>x \ne 0</math>, we have <math>x^2f(-x)=f(x)^2</math>. Substituting in <math>-x</math> for <math>x</math> gives us <math>x^2f(x)=f(-x)^2</math>. Substituting in <math>\frac{f(x)^2}{x^2}</math> in for <math>f(-x)</math> in the second equation gives us <math>x^2f(x)=\frac{f(x)^4}{x^4}</math>, so <math>x^6f(x)=f(x)^4</math>. In particular, if <math>f(x) \ne 0</math>, then we have <math>f(x)^3=x^6</math>, therefore <math>f(x)=0, x^2</math> for every <math>x</math>. Now, we just have to prove that if for some integer <math>t \ne 0</math>, if <math>f(t)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. If we assume <math>f(y)=0</math> and <math>y \ne 0</math> in the original equation, this simplifies to <math>xf(-x)+y^2f(2x)=\frac{f(x)^2}{x}. However, since </math>x^2f(-x)=f(x)^2<math>, we can rewrite this equation as </math>\frac{f(x)^2}{x}+y^2f(2x)=\frac{f(x)^2}{x}<math>, </math>y^2f(2x)<math> must therefore be equivalent to </math>0<math>. Since, by our initial assumption, </math>y \ne 0<math>, this means that </math>f(2x)=0<math>, so, if for some integer </math>y \ne 0<math>, </math>f(y)=0<math>, then </math>f(x)=0<math> for all integers </math>x<math>. The contrapositive must also be true, i.e. If </math>f(x) \ne 0<math> for all integers </math>x<math>, then there is no integral value of </math>y \ne 0<math> such that </math>f(y)=0<math>, therefore </math>f(x)<math> must be equivalent for </math>x^2<math> for every integer </math>x<math>, including </math>0<math>, since </math>f(0)=0<math>. Thus, </math>f(x)=0, x^2$ are the only possible solutions.  
+
Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and <math>f(yf(y))</math> must also be an integer, therefore <math>\frac{f(x)^2}{x}</math> is an integer. If <math>x</math> divides <math>f(x)^2</math> for all integers <math>x \ne 0</math>, then <math>x</math> must be a factor of <math>f(x)</math>, therefore <math>f(0)=0</math>. Now, by setting <math>y=0</math> in the original equation, this simplifies to <math>xf(-x)=\frac{f(x)^2}{x}</math>. Assuming <math>x \ne 0</math>, we have <math>x^2f(-x)=f(x)^2</math>. Substituting in <math>-x</math> for <math>x</math> gives us <math>x^2f(x)=f(-x)^2</math>. Substituting in <math>\frac{f(x)^2}{x^2}</math> in for <math>f(-x)</math> in the second equation gives us <math>x^2f(x)=\frac{f(x)^4}{x^4}</math>, so <math>x^6f(x)=f(x)^4</math>. In particular, if <math>f(x) \ne 0</math>, then we have <math>f(x)^3=x^6</math>, therefore <math>f(x)=0, x^2</math> for every <math>x</math>. Now, we just have to prove that if for some integer <math>t \ne 0</math>, if <math>f(t)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. If we assume <math>f(y)=0</math> and <math>y \ne 0</math> in the original equation, this simplifies to <math>xf(-x)+y^2f(2x)=\frac{f(x)^2}{x}</math>. However, since <math>x^2f(-x)=f(x)^2</math>, we can rewrite this equation as <math>\frac{f(x)^2}{x}+y^2f(2x)=\frac{f(x)^2}{x}</math>, <math>y^2f(2x)</math> must therefore be equivalent to <math>0</math>. Since, by our initial assumption, <math>y \ne 0</math>, this means that <math>f(2x)=0</math>, so, if for some integer <math>y \ne 0</math>, <math>f(y)=0</math>, then <math>f(x)=0</math> for all integers <math>x</math>. The contrapositive must also be true, i.e. If <math>f(x) \ne 0</math> for all integers <math>x</math>, then there is no integral value of <math>y \ne 0</math> such that <math>f(y)=0</math>, therefore <math>f(x)</math> must be equivalent for <math>x^2</math> for every integer <math>x</math>, including <math>0</math>, since <math>f(0)=0</math>. Thus, <math>f(x)=0, x^2</math> are the only possible solutions.  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Functional Equation Problems]]
 
[[Category:Functional Equation Problems]]

Revision as of 11:05, 4 January 2019

Problem

Let $\mathbb{Z}$ be the set of integers. Find all functions $f : \mathbb{Z} \rightarrow \mathbb{Z}$ such that \[xf(2f(y)-x)+y^2f(2x-f(y))=\frac{f(x)^2}{x}+f(yf(y))\] for all $x, y \in \mathbb{Z}$ with $x \neq 0$.

Solution

Note: This solution is kind of rough. I didn't want to put my 7-page solution all over again. It would be nice if someone could edit in the details of the expansions.

Lemma 1: $f(0) = 0$. Proof: Assume the opposite for a contradiction. Plug in $x = 2f(0)$ (because we assumed that $f(0) \neq 0$), $y = 0$. What you get eventually reduces to: \[4f(0)-2 = \left( \frac{f(2f(0))}{f(0)} \right)^2\] which is a contradiction since the LHS is divisible by 2 but not 4.

Then plug in $y = 0$ into the original equation and simplify by Lemma 1. We get: \[x^2f(-x) = f(x)^2\] Then:

\begin{align*} x^6f(x) &= x^4(-x)^2f(-(-x))\\ &= x^4f(-x)^2\\ &= f(x)^4 \end{align*}

Therefore, $f(x)$ must be 0 or $x^2$.

Now either $f(x)$ is $x^2$ for all $x$ or there exists $a \neq 0$ such that $f(a)=0$. The first case gives a valid solution. In the second case, we let $y = a$ in the original equation and simplify to get: \[xf(-x) + a^2f(2x) = \frac{f(x)^2}{x}\] But we know that $xf(-x) = \frac{f(x)^2}{x}$, so: \[a^2f(2x) = 0\] Since $a$ is not 0, $f(2x)$ is 0 for all $x$ (including 0). Now either $f(x)$ is 0 for all $x$, or there exists some $m \neq 0$ such that $f(m) = m^2$. Then $m$ must be odd. We can let $x = 2k$ in the original equation, and since $f(2x)$ is 0 for all $x$, stuff cancels and we get: \[y^2f(4k - f(y)) = f(yf(y))\] [b]for $k \neq 0$.[/b] Now, let $y = m$ and we get: \[m^2f(4k - m^2) = f(m^3)\] Now, either both sides are 0 or both are equal to $m^6$. If both are $m^6$ then: \[m^2(4k - m^2)^2 = m^6\] which simplifies to: \[4k - m^2 = \pm m^2\] Since $k \neq 0$ and $m$ is odd, both cases are impossible, so we must have: \[m^2f(4k - m^2) = f(m^3) = 0\] Then we can let $k$ be anything except 0, and get $f(x)$ is 0 for all $x \equiv 3 \pmod{4}$ except $-m^2$. Also since $x^2f(-x) = f(x)^2$, we have $f(x) = 0 \Rightarrow f(-x) = 0$, so $f(x)$ is 0 for all $x \equiv 1 \pmod{4}$ except $m^2$. So $f(x)$ is 0 for all $x$ except $\pm m^2$. Since $f(m) \neq 0$, $m = \pm m^2$. Squaring, $m^2 = m^4$ and dividing by $m$, $m = m^3$. Since $f(m^3) = 0$, $f(m) = 0$, which is a contradiction for $m \neq 1$. However, if we plug in $x = 1$ with $f(1) = 1$ and $y$ as an arbitrary large number with $f(y) = 0$ into the original equation, we get $0 = 1$ which is a clear contradiction, so our only solutions are $f(x) = 0$ and $f(x) = x^2$.

Alternative Solution

Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and $f(yf(y))$ must also be an integer, therefore $\frac{f(x)^2}{x}$ is an integer. If $x$ divides $f(x)^2$ for all integers $x \ne 0$, then $x$ must be a factor of $f(x)$, therefore $f(0)=0$. Now, by setting $y=0$ in the original equation, this simplifies to $xf(-x)=\frac{f(x)^2}{x}$. Assuming $x \ne 0$, we have $x^2f(-x)=f(x)^2$. Substituting in $-x$ for $x$ gives us $x^2f(x)=f(-x)^2$. Substituting in $\frac{f(x)^2}{x^2}$ in for $f(-x)$ in the second equation gives us $x^2f(x)=\frac{f(x)^4}{x^4}$, so $x^6f(x)=f(x)^4$. In particular, if $f(x) \ne 0$, then we have $f(x)^3=x^6$, therefore $f(x)=0, x^2$ for every $x$. Now, we just have to prove that if for some integer $t \ne 0$, if $f(t)=0$, then $f(x)=0$ for all integers $x$. If we assume $f(y)=0$ and $y \ne 0$ in the original equation, this simplifies to $xf(-x)+y^2f(2x)=\frac{f(x)^2}{x}$. However, since $x^2f(-x)=f(x)^2$, we can rewrite this equation as $\frac{f(x)^2}{x}+y^2f(2x)=\frac{f(x)^2}{x}$, $y^2f(2x)$ must therefore be equivalent to $0$. Since, by our initial assumption, $y \ne 0$, this means that $f(2x)=0$, so, if for some integer $y \ne 0$, $f(y)=0$, then $f(x)=0$ for all integers $x$. The contrapositive must also be true, i.e. If $f(x) \ne 0$ for all integers $x$, then there is no integral value of $y \ne 0$ such that $f(y)=0$, therefore $f(x)$ must be equivalent for $x^2$ for every integer $x$, including $0$, since $f(0)=0$. Thus, $f(x)=0, x^2$ are the only possible solutions.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_USAMO_Problems/Problem_2&oldid=100066"