Difference between revisions of "2014 USAMO Problems/Problem 2"

Latest revision as of 11:41, 3 March 2024

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\bigl(x^2f(x)\bigr)\\ &= x^4\bigl((-x)^2f(-(-x))\bigr)\\ &= 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))$ for $\mathbf{k \neq 0}$ . 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$ .

Solution 2

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)$ is equivalent to $0$ or $x^2$ for every integer $x$ . Now, we shall 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.

Solution 3

Let's assume $f(0)\neq 0.$ Substitute $(x,y)=(2f(0),0)$ to get $2f(0)^2=f(2f(0))^2/2f(0)+f(0)$ $2f(0)^2(2f(0)-1)=f(2f(0))^2$

This means that $2(2f(0)-1)$ is a perfect square. However, this is impossible, as it is equivalent to $2\pmod{4}.$ Therefore, $f(0)=0.$ Now substitute $x\neq 0, y=0$ to get $xf(-x)=\frac{f(x)^2}{x} \implies x^2f(-x)=f(x)^2.$ Similarly, $x^2f(x)=f(-x)^2.$ From these two equations, we can find either $f(x)=f(-x)=0,$ or $f(x)=f(-x)=x^2.$ Both of these are valid solutions on their own, so let's see if there are any solutions combining the two.

Let's say we can find $f(x)=x^2, f(y)=0,$ and $x,y\neq 0.$ Then $xf(-x)+y^2f(2x)=f(x)^2/x.$ $y^2f(2x)=x-x^3.$ (NEEDS FIXING: $f(x)^2/x= x^4/x = x^3$ , so the RHS is $0$ instead of $x-x^3$ .)

If $f(2x)=4x^2,$ then $y^2=\frac{x-x^3}{4x^2}=\frac{1-x^2}{4x},$ which is only possible when $y=0.$ This contradicts our assumption. Therefore, $f(2x)=0.$ This forces $x=\pm 1$ due to the right side of the equation. Let's consider the possibility $f(2)=0, f(1)=1.$ Substituting $(x,y)=(2,1)$ into the original equation yields $0=2f(0)+1f(2)=0+f(1)=1,$ which is impossible. So $f(2)=f(-2)=4$ and there are no solutions "combining" $f(x)=x^2$ and $f(x)=0.$

Therefore our only solutions are $\boxed{f(x)=0}$ and $\boxed{f(x)=x^2.}$

Solution 4

Let the given assertion be $P(x, y)$ . We try $P(x, 0)$ and get $xf(2c-x)=f(x)^2/x+c$ , where $f(0)=c$ . We plug in $x=c$ and get $cf(c)=f(c)^2/c+c$ . Rearranging and solving for $c^2$ gives us $c^2=\frac{f(c)^2}{f(c)-1}$ . Obviously, the only $c$ that works such that the RHS is an integer is $c=0$ , and thus $f(0)=0$ .

We use this information on assertion $P(x,0)$ and obtain $xf(-x)=f(x^2)/x$ , or $f(-x)=\frac{f(x)^2}{x^2}$ . Thus, $f(x)$ is an even function. It follows that $f(x)=0, x^2$ for each $x$ . We now prove that $f(x)=x^2$ , f(x)=0$ are the only solutions. [in progress] ~SigmaPiE

@@ Line 7: / Line 7: @@
 Proof: Assume the opposite for a contradiction. Plug in <math>x = 2f(0)</math> (because we assumed that <math>f(0) \neq 0</math>), <math>y = 0</math>. What you get eventually reduces to:
 <cmath>4f(0)-2 = \left( \frac{f(2f(0))}{f(0)} \right)^2</cmath>
-which is a contradiction since the RHS is divisible by 2 but not 4.
+which is a contradiction since the LHS is divisible by 2 but not 4.
 Then plug in <math>y = 0</math> into the original equation and simplify by Lemma 1. We get:
 <cmath>x^2f(-x) = f(x)^2</cmath>
 Then:
-\[
-\begin{align*}
+<cmath>\begin{align*}
-x^6f(x) &= x^4(-x)^2f(-(-x)) \\
+x^6f(x) &= x^4\bigl(x^2f(x)\bigr)\\
-&= x^4f(-x)^2 \\
+&= x^4\bigl((-x)^2f(-(-x))\bigr)\\
+&= x^4(-x)^2f(-(-x))\\
+&= x^4f(-x)^2\\
 &= f(x)^4
-\end{align*}
+\end{align*}</cmath>
-\]
 Therefore, <math>f(x)</math> must be 0 or <math>x^2</math>.
@@ Line 27: / Line 29: @@
 Since <math>a</math> is not 0, <math>f(2x)</math> is 0 for all <math>x</math> (including 0). Now either <math>f(x)</math> is 0 for all <math>x</math>, or there exists some <math>m \neq 0</math> such that <math>f(m) = m^2</math>. Then <math>m</math> must be odd. We can let <math>x = 2k</math> in the original equation, and since <math>f(2x)</math> is 0 for all <math>x</math>, stuff cancels and we get:
 <cmath>y^2f(4k - f(y)) = f(yf(y))</cmath>
-[b]for <math>k \neq 0</math>.[/b]
+<b>for <math>\mathbf{k \neq 0}</math>.</b>
 Now, let <math>y = m</math> and we get:
 <cmath>m^2f(4k - m^2) = f(m^3)</cmath>
@@ Line 36: / Line 38: @@
 Since <math>k \neq 0</math> and <math>m</math> is odd, both cases are impossible, so we must have:
 <cmath>m^2f(4k - m^2) = f(m^3) = 0</cmath>
-Then we can let <math>k</math> be anything except 0, and get <math>f(x)</math> is 0 for all <math>x \equiv 3 \pmod{4}</math> except <math>-m^2</math>.  Also since <math>x^2f(-x) = f(x)^2</math>, we have <math>f(x) = 0 \Rightarrow f(-x) = 0</math>, so <math>f(x)</math> is 0 for all <math>x \equiv 1 \pmod{4}</math> except <math>m^2</math>. So <math>f(x)</math> is 0 for all <math>x</math> except <math>\pm m^2</math>. Since <math>f(m) \neq 0</math>, <math>m = \pm m^2</math>. Squaring, <math>m^2 = m^4</math> and dividing by <math>m</math>, <math>m = m^3</math>. Since <math>f(m^3) = 0</math>, <math>f(m) = 0</math>, which is a contradiction, so our only solutions are <math>f(x) = 0</math> and <math>f(x) = x^2</math>.
+Then we can let <math>k</math> be anything except 0, and get <math>f(x)</math> is 0 for all <math>x \equiv 3 \pmod{4}</math> except <math>-m^2</math>.  Also since <math>x^2f(-x) = f(x)^2</math>, we have <math>f(x) = 0 \Rightarrow f(-x) = 0</math>, so <math>f(x)</math> is 0 for all <math>x \equiv 1 \pmod{4}</math> except <math>m^2</math>. So <math>f(x)</math> is 0 for all <math>x</math> except <math>\pm m^2</math>. Since <math>f(m) \neq 0</math>, <math>m = \pm m^2</math>. Squaring, <math>m^2 = m^4</math> and dividing by <math>m</math>, <math>m = m^3</math>. Since <math>f(m^3) = 0</math>, <math>f(m) = 0</math>, which is a contradiction for <math>m \neq 1</math>. However, if we plug in <math>x = 1</math> with <math>f(1) = 1</math> and <math>y</math> as an arbitrary large number with <math>f(y) = 0</math> into the original equation, we get <math>0 = 1</math> which is a clear contradiction, so our only solutions are <math>f(x) = 0</math> and <math>f(x) = x^2</math>.
+==Solution 2==
+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)</math> is equivalent to <math>0</math> or <math>x^2</math> for every integer <math>x</math>. Now, we shall 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.
+==Solution 3==
+Let's assume <math>f(0)\neq 0.</math> Substitute <math>(x,y)=(2f(0),0)</math> to get <cmath>2f(0)^2=f(2f(0))^2/2f(0)+f(0)</cmath>
+<cmath>2f(0)^2(2f(0)-1)=f(2f(0))^2</cmath>
+This means that <math>2(2f(0)-1)</math> is a perfect square. However, this is impossible, as it is equivalent to <math>2\pmod{4}.</math> Therefore, <math>f(0)=0.</math> Now substitute <math>x\neq 0, y=0</math> to get <cmath>xf(-x)=\frac{f(x)^2}{x} \implies x^2f(-x)=f(x)^2.</cmath>
+Similarly, <cmath>x^2f(x)=f(-x)^2.</cmath>
+From these two equations, we can find either <math>f(x)=f(-x)=0,</math> or <math>f(x)=f(-x)=x^2.</math> Both of these are valid solutions on their own, so let's see if there are any solutions combining the two.
+Let's say we can find <math>f(x)=x^2, f(y)=0,</math> and <math>x,y\neq 0.</math> Then <cmath>xf(-x)+y^2f(2x)=f(x)^2/x.</cmath>
+<cmath>y^2f(2x)=x-x^3.</cmath> (NEEDS FIXING: <math>f(x)^2/x= x^4/x = x^3</math>, so the RHS is <math>0</math> instead of <math>x-x^3</math>.)
+If <math>f(2x)=4x^2,</math> then <math>y^2=\frac{x-x^3}{4x^2}=\frac{1-x^2}{4x},</math> which is only possible when <math>y=0.</math> This contradicts our assumption. Therefore, <math>f(2x)=0.</math> This forces <math>x=\pm 1</math> due to the right side of the equation. Let's consider the possibility <math>f(2)=0, f(1)=1.</math> Substituting <math>(x,y)=(2,1)</math> into the original equation yields  <cmath>0=2f(0)+1f(2)=0+f(1)=1,</cmath> which is impossible. So <math>f(2)=f(-2)=4</math> and there are no solutions "combining" <math>f(x)=x^2</math> and <math>f(x)=0.</math>
+Therefore our only solutions are <math>\boxed{f(x)=0}</math> and <math>\boxed{f(x)=x^2.}</math>
+==Solution 4==
+Let the given assertion be <math>P(x, y)</math>. We try <math>P(x, 0)</math> and get <math>xf(2c-x)=f(x)^2/x+c</math>, where <math>f(0)=c</math>. We plug in <math>x=c</math> and get <math>cf(c)=f(c)^2/c+c</math>. Rearranging and solving for <math>c^2</math> gives us <math>c^2=\frac{f(c)^2}{f(c)-1}</math>. Obviously, the only <math>c</math> that works such that the RHS is an integer is <math>c=0</math>, and thus <math>f(0)=0</math>.
+We use this information on assertion <math>P(x,0)</math> and obtain <math>xf(-x)=f(x^2)/x</math>, or <math>f(-x)=\frac{f(x)^2}{x^2}</math>. Thus, <math>f(x)</math> is an even function. It follows that <math>f(x)=0, x^2</math> for each <math>x</math>. We now prove that <math>f(x)=x^2</math>, f(x)=0$ are the only solutions. [in progress] ~SigmaPiE
+[[Category:Olympiad Algebra Problems]]
+[[Category:Functional Equation Problems]]

Page

Toolbox

Search