Difference between revisions of "2014 USAMO Problems/Problem 2"
m (→Solution: RHS -> LHS) |
m (→Alternative Solution) |
||
(20 intermediate revisions by 8 users not shown) | |||
Line 13: | Line 13: | ||
Then: | Then: | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
− | + | x^6f(x) &= x^4\bigl(x^2f(x)\bigr)\\ | |
− | &= x^4f(-x)^2 \\ | + | &= x^4\bigl((-x)^2f(-(-x))\bigr)\\ |
− | &= f(x)^4 | + | &= x^4(-x)^2f(-(-x))\\ |
− | \end{align*} | + | &= x^4f(-x)^2\\ |
+ | &= f(x)^4 | ||
+ | \end{align*}</cmath> | ||
Therefore, <math>f(x)</math> must be 0 or <math>x^2</math>. | 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: | 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> | <cmath>y^2f(4k - f(y)) = f(yf(y))</cmath> | ||
− | + | <b>for <math>\mathbf{k \neq 0}</math>.</b> | |
Now, let <math>y = m</math> and we get: | Now, let <math>y = m</math> and we get: | ||
<cmath>m^2f(4k - m^2) = f(m^3)</cmath> | <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: | 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> | <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]] |
Latest revision as of 11:41, 3 March 2024
Problem
Let be the set of integers. Find all functions such that for all with .
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: . Proof: Assume the opposite for a contradiction. Plug in (because we assumed that ), . What you get eventually reduces to: which is a contradiction since the LHS is divisible by 2 but not 4.
Then plug in into the original equation and simplify by Lemma 1. We get: Then:
Therefore, must be 0 or .
Now either is for all or there exists such that . The first case gives a valid solution. In the second case, we let in the original equation and simplify to get: But we know that , so: Since is not 0, is 0 for all (including 0). Now either is 0 for all , or there exists some such that . Then must be odd. We can let in the original equation, and since is 0 for all , stuff cancels and we get: for . Now, let and we get: Now, either both sides are 0 or both are equal to . If both are then: which simplifies to: Since and is odd, both cases are impossible, so we must have: Then we can let be anything except 0, and get is 0 for all except . Also since , we have , so is 0 for all except . So is 0 for all except . Since , . Squaring, and dividing by , . Since , , which is a contradiction for . However, if we plug in with and as an arbitrary large number with into the original equation, we get which is a clear contradiction, so our only solutions are and .
Solution 2
Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and must also be an integer, therefore is an integer. If divides for all integers , then must be a factor of , therefore . Now, by setting in the original equation, this simplifies to . Assuming , we have . Substituting in for gives us . Substituting in in for in the second equation gives us , so . In particular, if , then we have , therefore is equivalent to or for every integer . Now, we shall prove that if for some integer , if , then for all integers . If we assume and in the original equation, this simplifies to . However, since , we can rewrite this equation as , must therefore be equivalent to . Since, by our initial assumption, , this means that , so, if for some integer , , then for all integers . The contrapositive must also be true, i.e. If for all integers , then there is no integral value of such that , therefore must be equivalent for for every integer , including , since . Thus, are the only possible solutions.
Solution 3
Let's assume Substitute to get
This means that is a perfect square. However, this is impossible, as it is equivalent to Therefore, Now substitute to get Similarly, From these two equations, we can find either or 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 and Then (NEEDS FIXING: , so the RHS is instead of .)
If then which is only possible when This contradicts our assumption. Therefore, This forces due to the right side of the equation. Let's consider the possibility Substituting into the original equation yields which is impossible. So and there are no solutions "combining" and
Therefore our only solutions are and
Solution 4
Let the given assertion be . We try and get , where . We plug in and get . Rearranging and solving for gives us . Obviously, the only that works such that the RHS is an integer is , and thus .
We use this information on assertion and obtain , or . Thus, is an even function. It follows that for each . We now prove that , f(x)=0$ are the only solutions. [in progress] ~SigmaPiE