Carl chooses a functional expression* $E$ which is a finite nonempty string formed from a set $x_1, x_2, \dots$ of variables and applications of a function $f$, together with addition, subtraction, multiplication (but not division), and fixed real constants. He then considers the equation $E = 0$, and lets $S$ denote the set of functions $f \colon \mathbb R \to \mathbb R$ such that the equation holds for any choices of real numbers $x_1, x_2, \dots$. (For example, if Carl chooses the functional equation $$ f(2f(x_1)+x_2) - 2f(x_1)-x_2 = 0, $$ then $S$ consists of one function, the identity function. (a) Let $X$ denote the set of functions with domain $\mathbb R$ and image exactly $\mathbb Z$. Show that Carl can choose his functional equation such that $S$ is nonempty but $S \subseteq X$. (b) Can Carl choose his functional equation such that $|S|=1$ and $S \subseteq X$? *These can be defined formally in the following way: the set of functional expressions is the minimal one (by inclusion) such that (i) any fixed real constant is a functional expression, (ii) for any positive integer $i$, the variable $x_i$ is a functional expression, and (iii) if $V$ and $W$ are functional expressions, then so are $f(V)$, $V+W$, $V-W$, and $V \cdot W$. Proposed by Carl Schildkraut
Problem
Source: ELMO 2019 Problem 6, 2019 ELMO Shortlist A5
Tags: algebra, functional equation, function
26.06.2019 01:07
26.06.2019 01:23
26.06.2019 01:37
USJL wrote:
Nice solution!
26.06.2019 02:54
pieater314159 wrote: USJL wrote:
Nice solution!
26.06.2019 03:44
This is far from the simplest solution and parts of it might be redundant but I think this works. The first thing to note is that if neither $x_1$ nor $x_2$ appears in the functional equations $E_1$ and $E_2$ then $$x_1E_1 + x_2E_2 = 0$$$\forall x_1,x_2 \in \mathbb{R}$ iff $E_1 = 0$ and $E_2 = 0$. So it suffices to find a finite list of functional equations so that exactly one function $f$ satisfies each equation and $f \in X$. 1. $$f(-x^2) = 0$$$f$ maps negative numbers to zero. 2. $$(f(f(x)) - f(x))(f(-f(x)) + f(x))) = 0$$If $y> 0$ is in the image of $f$, then $f$ fixes $y$. And if $y$ is negative, then $-y$ is also in the image of $f$. 3. $$(f(f(x) + 1) - f(x) -1)(f(-f(x) + 1) + f(x) -1) = 0$$If $y \geq 1$ is in the image of $f$, then $y+1$ is also in the image of $f$. 4. $$f(x)(f(f(x) -1) -f(x) + 1)(f(-f(x) - 1) + f(x) +1) = 0$$If $y \geq 1$ is in the image of $f$, then $y-1$ is also in the image of $f$. 5. $$f(0) = 0$$6.$$f(1) -1= 0$$The non-negative integers are a subset of the image of $f$. 7. $$f(f(x) + \frac{1}{2}) + f(f(x)) = 0$$If $y > 0$ is in the image of $f$, then so is $-y$. 8. $$f(f(x)^4 - f(x)^2) - f(x)^4 +f(x)^2 = 0$$. If $y \in (0,1)$ then $y$ is not in the image of $f$ and so by 4. if $y$ is not an integer, $y$ is not in the image of $f$. So $\text{Im}(f) = \mathbb{Z}$. 9. $$f(x)(x-f(x))(x-\frac{1}{2} + f(x-\frac{1}{2})) = 0$$If $f(y) \neq 0$ then $y$ is an integer or an integer plus $\frac{1}{2}$. Thus, the only function that satisfies each of the above equations is \[ f(x) = \left\{ \begin{array}{ll} x & x\in \mathbb{Z}_+\\ -(x-1/2) & x-\frac{1}{2} \in \mathbb{Z}_+ \\ 0 & else \\ \end{array} \right. \] And it is easy to check this satisfies each of the equations
26.06.2019 03:47
Let $f_0(x) = x$ if $x$ is an integer and $f_0(x) = 0$ otherwise. Let us try to find a functional equation the only solution of which is $f_0$! First of all we need an equation the only solution of which is $g_0$, where $g_0(x) = 0$ unless $x = 0$, when $g_0(0) = 1$. Clearly$$x^2g(x)^2 + (g(0) - 1)^2 = 0 \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(1)$$will do it. In what follows we shall use that if $f$ is required to simultaneously a few equations $E_i = 0$, then this can be done by setting $E = 0$ where $E = \sum_i E_i^2$ (or just $\sum_i E_i$ if the $E_i$'s are already nonnegative). Note that $g_0(x) = f_0(x + 1)f_0(\sqrt{2}x + 1)$, so (1) in terms of $f$ can be replaced by$$ x^2(f(x+1)f(\sqrt{2}x + 1))^2 + (f(1) - 1)^2 = 0.\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(2)$$We need that $f(x + 1) = f(x) + 1$ if $x$ is an integer, and this requirement should not be imposed if $x$ is not an integer. Now $f_0^2(x) + g_0^2(x)$ is not zero precisely on the integers, so the requirement can be put in the form$$\left[(f(x+1) - f(x) - 1)^2 + (f(x) - f(x-1) - 1)^2 \right](f(x)^2 + g(x)^2) = 0$$(I included two recurrence forms for an easier induction below). We also need that $f(x + 1) = f(x)$ if $x$ is not an integer, and since $x - f_0(x) \neq 0$ for such $x$, this can be put in the form$$\left[(f(x + 1) - f(x))^2 + (f(x) - f(x - 1))^2\right](x - f(x))^2 = 0.$$The most difficult is to achieve that $f(x) = 0$ for all $0 < x < 1$. This we do by requiring$$g(x(1 - x) - y^2)y^2f(x)^2 = 0.$$Indeed, since $x(1 - x) < 0$ if $x \notin [0, 1]$, the only situation when $g(x(1 - x) - y^2)y^2 \neq 0$ is when $x \in (0, 1)$ and $y = \sqrt{x(1 - x)}$, and then the equation forces $f(x)$ to be $0$. Thus, $f_0$ should be the only solution of \begin{align*} & \left[(f(x + 1) - f(x) - 1)^2 + (f(x) - f(x - 1) - 1)^2\right](f(x)^2 + g(x)^2) \\ + & \left[(f(x + 1) - f(x))^2 + (f(x) - f(x - 1))^2\right](x - f(x))^2 \\ + & g(x(1 - x) - y^2)y^2 f(x)^2 + f(0)^2 + (f(1) - 1)^2 = 0, \end{align*}with the $g$ satisfying (1), or, if we do not want $g$ in the equation, then use (2) and $g(x) = f(x + 1)f(\sqrt{2}x + 1)$ and write \begin{align*} & x^2(f(x + 1)f(\sqrt{2}x + 1))^2 \\ + & \left[(f(x+1)-f(x)-1)^2+(f(x)-f(x-1)-1)^2\right](f(x)^2+(f(x+1)f(\sqrt{2}x+1))^2) \\ + & \left[(f(x+1)-f(x))^2+(f(x)-f(x-1))^2\right](x-f(x))^2 \\ + & (f(x(1-x)-y^2+1)f(\sqrt{2}(x(1-x)-y^2)+1))^2y^2f(x)^2+f(0)^2+(f(1)-1)^2=0. \end{align*}It is easy to check the $f_0$ is a solution, so let us just convince ourselves that there are no other solutions. $f(0) = 0$, $f(1) = 1$ are clear. Then the first row shows that $f(x+ 1)f(\sqrt{2}x + 1) = 0$ for all $x \neq 0$, and for $x = 0$ its value is $1$. Setting $x = 0$ into the equation the second row shows that $f(1) = 1$ (we know that anyway) and $f(-1) = -1$. Setting $x = 1$ the same row shows that $f(2) = 2$, and for $x = -1$ we obtain $f(-2) = -2$. Following this way we get by induction $f(x) = x$ for integers. Let now $x \in (0, 1)$ and $y = \sqrt{x(1 - x)}$. Then the last row shows that $f(x) = 0$. Using this, we get from the third row that $f = 0$ on $(1, 2)$, as well as on $(-1, 0)$. Using these values again an induction based on the third row gives $f(x) = 0$ for all $x \in (n, n + 1)$ where $n$ is an integer, hence $f$ must, indeed, be $f_0$.
26.06.2019 04:30
The following is an example of functional equation with variables $a_1,a_2,a_3,a_4,x$ that satisfy both $\left(a\right)$ and $\left(b\right)$: $$a_1x^2f\left(-x^2+2\right)+a_2\left(f\left(x\right)+f\left(x+1\right)\right)\left(f\left(x\right)+f\left(x+1\right)-1\right)f\left(x+1\right)+a_3\left(f\left(x^2+2\right)-f\left(x^2\right)-1\right)\left(f\left(x^2+2\right)-f\left(x^2\right)+1\right)+a_4\left(f\left(x^2+3\right)+f\left(x^2+2\right)-f\left(x^2+1\right)-f\left(x^2\right)\right)=0$$ Plugging in $\left(a_1,a_2,a_3,a_4\right)=\left(1,0,0,0\right)$ and then the other three possible permutations we get this: $$x^2f\left(-x^2+2\right)=0\ \ \forall\ \ x\in\mathbb{R}\qquad\hspace*{\fill}\left(1\right)$$$$\left(f\left(x\right)+f\left(x+1\right)\right)\left(f\left(x\right)+f\left(x+1\right)-1\right)f\left(x+1\right)=0\ \ \forall\ \ x\in\mathbb{R}\qquad\hspace*{\fill}\left(2\right)$$$$\left(f\left(x^2+2\right)-f\left(x^2\right)-1\right)\left(f\left(x^2+2\right)-f\left(x^2\right)+1\right)=0\ \ \forall\ \ x\in\mathbb{R}\qquad\hspace*{\fill}\left(3\right)$$$$f\left(x^2+3\right)+f\left(x^2+2\right)-f\left(x^2+1\right)-f\left(x^2\right)=0\ \ \forall\ \ x\in\mathbb{R}\qquad\hspace*{\fill}\left(4\right)$$ Now, $$\left(1\right)\Leftrightarrow f\left(x\right)=0\ \forall\ x<2\qquad\hspace*{\fill}\left(1.1\right)$$Considering together $\left(1.1\right)$ and $\left(2\right)$ (this one with $x=y-1$), we get that $$\forall\ y\in\left[2,3\right)\ \ f\left(y\right)\stackrel{\left(2\right)}{\in}\{-f\left(y-1\right),-f\left(y-1\right)+1,0\}\stackrel{\left(1\right)}{=}\{0,1\}\qquad\hspace*{\fill}\left(2.1\right)$$Besides, looking at $\left(3\right)$ with $x=\sqrt{y-2}$ where $y\in\left[2,3\right)$, we also have $$f\left(y\right)\in\{f\left(y-2\right)+1,f\left(y-2\right)-1\}\stackrel{\left(1\right)}{=}\{-1,1\}\qquad\hspace*{\fill}\left(3.1\right)$$$\left(2.1\right)$ and $\left(3.1\right)\Rightarrow f\left(x\right)=1\ \ \forall x\in\left[2,3\right)\ \ \ \left(*\right)$.
At this point to finish the problem we just need to show a function $f$ with image $\mathbb{Z}$ that is a solution to the beginning equation. Simply define $f$ as follows: $$ \begin{cases} f\left(x\right)=0\ \ \forall\ x<0\\ f\left(x\right)=\left\lfloor \frac{x}{2}\right\rfloor\left(-1\right)^{\left\lfloor x\right\rfloor}\ \ \forall\ x\ge0 \end{cases} $$ The image is indeed $\mathbb{Z}$, to show this take a generic $n\in\mathbb{Z}_{\ge0}$ and note that $f\left(2n\right)=n$ while $f\left(2n+1\right)=-n$. To check that this function satisfy the beginning equation there is just a couple of simple cases to be analysed, that for brevity I omit here.
26.06.2019 07:54
I tried for 4 hours without any success, then while chatting with ayan.nmath I realized I didnt read condition (i) (that any real number is a valid functional expression) and solved this within one hour lol, so I think this is very wrong ? I claim $$ \left\{ f(0) - f(1) \right\}^2 + \left\{ \biggl( (y+yx^2-1)^2 + f(y)^2\biggr) \cdot \biggl( f(y+yx^2-1) - f(y+yx^2) -1 \biggr) \right\}^2 = 0 $$satisfies both (a) and (b) Let $P(x,y)$ denote what it usually means, $P( x, \frac{1}{1+x^2})$ says for any $z \in (0, 1]$ we have $f(z) = 0$, and we clan extend it over all reals using $P(1, \frac{z+1}{2})$, which tells that if $z = 0$, then $f(0) = f(1)$, otherwise $f(z) = f(z+1) - 1$. Combining these two we get $f(z) = \left\{\begin{matrix} \lceil z \rceil - 1 \; \; \; \; \; \; \; z \not \in \mathbb{Z} \\ z \; \; \; \; \; \; \; \; \; \; \; \; \; \; z \in \mathbb{Z}_{\leq 0} \\ \; \; z-1 \; \; \; \; \; \; \; \; \; \; \; \;z \in \mathbb{Z}_{\geq 1} \end{matrix}\right.$, so done ?
26.06.2019 09:40
USJL wrote: pieater314159 wrote:
bern-1-16-4-13 wrote:
Here's a variant a couple of us thought of, but to my knowledge no one has solved yet: what happens when you replace $\mathbb{Z}$ with $\mathbb{Q}$? Can the first part still be completed? What about the second?
27.06.2019 22:50
29.06.2019 03:28
Our aim is to generate the unique solution $f(2m-1)=m, f(2m)=-m$ for positive integers $m$ and $f(m) = 0$ otherwise. Note that we can reduce the question into a combination of ‘AND’ (sum of squares = 0) and ‘OR’ (product of terms) conditions. First start by fixing $f(m)$ for natural numbers $m$. This can be done by letting $f(1)=1,f(2)=-1,...,f(10)=-5$ and inductively defining the remaining natural numbers (e.g. by setting $f(x) = -f(x-1)+1$ OR ($f(2x)=2f(x)$ AND $f(x) = -f(x-1)$)). Now we add the condition $(f(x)-f(y))(f(2-(f(x)-f(y))^2-z^2)z (=0)$. Note that $f(1) \neq 0$; but if $0<f(x)-f(y)<1$ we can always choose nonzero $z$ such that $2-(f(x)-f(y))^2-z^2=1$, a contradiction. So $f(x)-f(y)=0$ or $\geq 1$; since $f$ already spans all integers, we must have $f(x)$ is an integer for all $x$, solving a). To make this solution unique, it suffices to add a condition such as $f(x)=0,\frac{x+1}{2}$ or $-\frac{x}{2}$.
02.04.2020 19:57
Unfortunately there is a typo in the OP. "Carl" should instead be "Snorlax." The answer to part (b) is yes. Claim: There is a unique sequence of integers $\ldots$, $a_{-1}$, $a_0$, $a_1$, $\ldots$ such that $a_n=0$ for all $n<0$; $a_n-a_{n-2}\in\{1,-1\}$ for all $n\ge0$. $a_0\in\{0,1\}$; $a_n+a_{n+1}=a_{n-2}+a_{n-1}$ for all $n\ge0$. Proof. If $a_0=0$, then $a_n-a_{n-2}\in\{1,-1\}$ does not hold for $n=0$. Hence $a_0=1$, and the recurrence $a_{n+1}=a_{n-1}+a_{n-2}-a_n$ guarantees there is at most one such sequence. The unique sequence is that obeying $a_n=0$ for all $n\le0$, and for all positive integers $m$, we have $a_{2m-2}=m$ and $a_{2m-1}=-m$. $\blacksquare$ Note for functional expressions $E_1$, $E_2$, the functional expression $E=E_1E_2$ equals $0$ if and only if either $E_1=0$ or $E_2=0$; the functional expression $E=E_1^2+E_2^2$ equals $0$ if and only if $E_1=E_2=0$. This yields the following construction: \begin{align*} 0&=\left[xf\left(-x^2\right)\right]^2+\left[\left(f\left(x^2\right)-f\left(x^2-2\right)\right)^2-1\right]^2\\ &\quad+\left[(x-1)f(1-x)f(x)\big(f(x)-1\big)\right]^2\\ &\quad+\left[f\left(x^2\right)+f\left(x^2+1\right)-f\left(x^2-2\right)-f\left(x^2-1\right)\right]^2. \end{align*}The above is equivalent to all of the following conditions holding simultaneously: $f(x)=0$ for all $x<0$; $f(x)-f(x-2)\in\{1,-1\}$ for all $x\ge0$; $f(x)\in\{0,1\}$ for all $x\in[0,1)$; $f(x)+f(x+1)=f(x-2)+f(x-1)$ for all $x\ge0$. Thus for all $0\le\nu<1$, the sequence $a_n=f(n+\nu)$ obeys the claim, so the functional equation has a single solution: \[f(x)=\begin{cases} 0&\text{if }x<0\\ m&\text{if }\lfloor x\rfloor=2m-2,\;m\in\mathbb Z_{>0}\\ -m&\text{if }\lfloor x\rfloor=2m-1,\;m\in\mathbb Z_{>0}. \end{cases}\]
02.11.2020 05:02
Fantastic problem! Here's a little motivation (since I think a similar solution has been posted as well): To tackle this problem, we need to use 2 facts: The first being $\sum_i P_i(x)^2 = 0 \rightarrow P_i(x) = 0$ for all $i$ and the other one is $P_i(x)$ vanishes as its root (Note: "$P_i$ is not a polynomial, and define root to be values such that the output is $0$.) We want to construct a sequence of $f(\mathbb{R}) = \mathbb{Z}$ with several equations, and suppose we did find an equation $a = b$, we can use $P_1(x) = (a - b)$ to be our "first condition" which must be verified later on. Furthermore, suppose that we have an equation $a = b$, which is true except for a finite amount of cases, when $x = c_1, c_2, \dots, c_k$. We can use the second idea and consider $P_1(x) = (a - b) \prod_i (x - c_i)$ since this means that this polynomial vanishes when input is $c_i$ for some $1 \le i \le k$, so we don't need to consider this condition. First, we can just ignore all the negative reals by taking $f(n) = 0$ for any $n \le 0$, this is achievable by taking $P_1(x) = -x^2$. Now, let us consider the sequence $\{ a_n \} : 0, 0, 0, \dots, 0, -1, 1, -2, 2, \dots$ The most crucial thing about this sequence is the fact that it satisfies $a_{n + 3} + a_{n + 2} = a_{n + 1} + a_n$, except for $(0,0,0,-1)$. Thus, we can have $P_2(x) = (f(x + 3) + f(x + 2) - f(x + 1) - f(x))\prod_{a \in f^{-1}(-1)} (x - a)$ where we define $f^{-1}(-1)$ to be the possible values $a$ such that $f(a) = -1$, and for such values we can consider $P_i(x) = (f(a) + 1)$. For that reason, we can consider the construction \[ f(-x^2)^2 + \left( (f(x + 3) + f(x + 2) - f(x + 1) - f(x))(x + 2) \right)^2 + (f(1) + 1)^2 = 0 \]Let's prove this work. This can be dissect into the following condition: 1. $f(-x^2) = 0$, for all $x \in \mathbb{R}$. 2. $f(x + 3) + f(x + 2) = f(x + 1) + f(x)$, for all $x \in \mathbb{R}_{\not= -2}$. 3. $f(1) = -1$. For any $x \notin \mathbb{Z}$, we can represent it as $f(y + n)$ where $y \le 0$ and $n \in \mathbb{N}$. So the first and second criteria can be "lifted" out to show for any $x \notin \mathbb{Z}, f(x) = 0$. For $x \in \mathbb{Z}$, it is easy to check that we get the sequence $f(1) = -1, f(2) = 1, f(3) = -2, \dots$ just like how we wanted.
05.03.2024 22:36
Solved with dolphinday and mathboy100. Yes. Clearly part b implies part a. Consider the FE $(xf(-x^2))^2 + \Bigg ( (f(x^2) - f(x^2 - 1))^2 - 1\Bigg )^{420} + \Bigg(f(x^2 + 1) - 2f(x^2) + f(x^2 - 1) \Bigg)^{434} + (f(x-x) + 1)^{1434} + \Bigg (x ^2 (f(x^2) - f(x^2 - 1) - 1) (f(x^2 - 1) - f(x^2 - 1 - 1)-1) (f(x^2 - 1) - f(x^2 - 1 - 1)+1) \Bigg)^{69420} = 0$
05.03.2024 23:05
Here's a slightly different solution path(incomplete) that uses mostly the same idea as @above; There does exist a functional equation satisfying said conditions. We can split $E$ into several subset functions $F_i$ and take the square of them so that they must equal $0$(by trivial inequality). So then $E = F_0^2 + F_1^2 \dots \implies F_0, F_1, F_2, \dots = 0$. We have $F_0 = f(x^2+1)-f(x) - (f(x^2)-f(x^2-1))$. Let $F_1 = xf(-x^2)$. This forces negative $x$ to be $0$. We can let $F_2 = ((f(x^2) - f(x^2 - 1))^2 - 1)^2$. This is equivalent to $f(y) - f(y-1) = \{-1, 1\}$ for nonnegative $y$. Note that we now get that all values $f(x)$ are $\in \mathbb Z$. We now let $F_3 = f(0.434) + 1$ which forces $f(0.434) = -1$. Then $F_4 = f(1.434) + 2$ which implies $f(1.434) = -2$ similarly. Then from $f(x) - f(x-1) = 1$ we get that all values of $f(x.434) = -(x + 1)$. Similarly we can set $f(0.0434) = 1$ and $f(1.0434) = 2$, from which we can guarantee that we get all integers, positive and nonpositive. So our full equation is \[E = (xf(-x^2))^2 + ((f(x^2) - f(x^2 - 1))^2 - 1)^2 + (f(x^2+1)-f(x) -(f(x^2)-f(x^2-1))^2\]\[+ (f(0.434) + 1)^2 + (f(1.434) + 2)^2 + (f(0.0434) - 1)^2 + (f(1.0434) - 2)^2\] note that this does not finish since we have to limit the number of possible functions to $1$(by essentially forcing all values other than $0.0434$ and $0.434$); I'll fix it later.
08.04.2024 19:44
We claim that \begin{align*} &f(-x_1^2)^2 + (f(1) - 1)^2 + (f(0.5) + 1)^2 + \\ &(f(x_1 - 1) - 2f(x_1) + f(x_1 + 1))^2x_1^2(x_1 + 0.5)^2 \end{align*}works. This means that $f$ is $0$ on $(-\infty, 0]$, that $f(1) = 1$, $f(0.5) = -1$, $f(1 + n) = 1 + n$, $f(0.5 + n) = -1 - n$, and $f(x) = 0$ for non-integers.
10.07.2024 20:59
07.11.2024 00:20
Solved with math_comb01 (who admits orz pro max). So notice that by making sum of squares of equations you can have multiple functional equations at the same time that equal to zero (alternatively multiply all by a variable not used before, that also works), and also by product of two functional equations being equal to zero we can force a conditional result (meaning a thing being equal to either of elements of a set) which allows us to have our construction to be more versatile. We claim that the answer for b) is yes which automatically implies a), so now we provide a construction. We will set $f(x^2+2)-f(x^2)={-1,1}$ also $f(2-x^2)=0$ for all $x \ne 0$, also $f(x^2+1)+f(x^2)={0,1}$, now just notice that this covers all integers as $f(2n)=n, f(2n+1)=-n$ for all positive integers $n$, and in fact it's easy to check that the only function that works is $f(x)=0$ for all $x \le 0$ and for all $x>0$ we have $f(x)=\left\lfloor \frac{x}{2} \right\rfloor (-1)^{\lfloor x \rfloor}$ as the only solution, you can check this by strong induction on the floor of the pre-image, therefore we are done .