Let $A$ be a finite set of non-negative integers. Determine all functions $f:\mathbb{Z}_{\ge 0} \to A$ such that \[f(|x-y|)=|f(x)-f(y)|\]for each $x,y\in\mathbb Z_{\ge 0}$. Andrei Bâra
Problem
Source: Romanian NMO 2021 grade 9 P4
Tags: functional equation, algebra
17.04.2023 21:09
Miquel-point wrote: Let $A$ be a finite set of non-negative integers. Determine all functions $f:\mathbb{Z}_{\ge 0} \to A$ such that \[f(|x-y|)=|f(x)-f(y)|\]for each $x,y\in\mathbb Z_{\ge 0}$. Let $P(x,y)$ be the assertion $f(|x-y|)=|f(x)-f(y)|$ $P(x,x)$ $\implies$ $f(0)=0$ (and so $0\in A$) SInce $|A|$ is finite, $\exists u,M\in\mathbb Z_{\ge 0}$ such that $f(u)=M=\max(f(\mathbb Z_{\ge 0}))$ Let $x>u$ $P(x,x-u)$ $\implies$ $M=|f(x)-|f(x)-M||$ and so : Either $f(x)\ge M$ and so $f(x)=M$ Either $f(x)<M$ and so $M=|2f(x)-M|$ and so $f(x)=0$ So $\forall x>u$ : $f(x)\in\{0,M\}$ Since $|f(\mathbb Z_{\ge 0})|$ is finite, $\exists$ infinitely many $x>y$ such that $f(x)=f(y)$ and so $f(x-y)=0$ Let $U=f^{-1}(\{0\})$ and $a=\min (U\setminus\{0\})$ Since $x,y\in U$ implies $|x-y|\in U$, we easily get that $U=\{na\quad\forall n\in\mathbb Z_{\ge 0}\}$ $P(x+a,a)$ $\implies$ $f(x+a)=f(x)$ $\forall x\in\mathbb Z_{\ge 0}$ So $f(x+na)=f(x)$ and since $f(x)\in\{0,M\}$ $\forall x>u$, we get $f(x)\in\{0,M\}$ $\forall x\in\mathbb Z_{\ge 0}$ But $f(x)=f(y)=M$ implies $|x-y|\equiv 0\pmod a$ And so solutions : If $0\notin A$ : no solution If $A=\{0\}$ : one solution : $f\equiv 0$ If $0\in A$ and $|A|>1$, two solutions : 1) $f\equiv 0$ 2) $f(2n)=0$ and $f(2n+1)=M$ whatever is $M\in A\setminus\{0\}$
18.04.2023 03:30
maybe simpler solution if it works We'll show that $f(2n)=0$ for all $n\ge0$, and $f(2n+1)=c$ for some constant $c\ge0$, which satisfy the assertion (call the assertion $P(x,y)$). $P(0,0)\Rightarrow f(0)=0$ $P(x+1,x)\Rightarrow |f(x+1)-f(x)|=f(1)\Rightarrow f(x+1)=f(x)+g(x)f(1)$ for some $g:\mathbb Z_{\ge0}\to\{-1,1\}$. Then by applying this twice: $$f(x+2)=f(x)+g(x+1)f(1)+g(x)f(1)\qquad(*).$$ If $g(k+1)\ne g(k)$ for some $k$ then $g(k+1)=-g(k)$ so $f(k+2)=f(k)$ by $(*)$. Then: $$|f(n+2)-f(n)|=f(2)=|f(k+2)-f(k)|=0\Rightarrow f(n+2)=f(n).$$By induction on $(*)$, $f(2n)=0$ for all $n\ge0$ (starting from $f(0)=0$), and $f(2n+1)=c$ (starting from $c=f(1)$) for some constant $c\ge0$. If $g(x+1)=g(x)$ for all $x$, $g$ is constant. If $g(x)=-1$ we get by $(*)$: $f(3)=f(1)+g(2)f(1)+g(1)f(1)=-f(1)$ so $f(3)=f(1)=0$ Then after $P(x,1)$ we get $f(x-1)=f(x)$ for all $x\ge1$ so $f$ is all zero by induction. If $g(x)=1$ then $f(x+1)=f(x)+f(1)$ so by induction $f(x+n)=f(x)+nf(1)$ and setting $x=0$ gives $f(n)=nf(1)$. Since $A$ is finite, we get $f(1)=0$ which means, again, $f(n)=0$.