Determine, whether exists function $f$, which assigns each integer $k$, nonnegative integer $f(k)$ and meets the conditions: $f(0) > 0$, for each integer $k$ minimal number of the form $f(k - l) + f(l)$, where $l \in \mathbb{Z}$, equals $f(k)$.
Problem
Source: 67 Polish MO 2016 Second Round - Problem 3
Tags: algebra, function, Poland
01.05.2018 10:48
mruczek wrote: Determine, whether exists function $f$, which assigns each integer $k$, nonnegative integer $f(k)$ and meets the conditions: $f(0) > 0$, for each integer $k$ minimal number of the form $f(k - l) + f(l)$, where $l \in \mathbb{Z}$, equals $f(k)$. Note that $\min_{y\in Z}(f(x-y)+f(y))=f(x)$ is equivalent to : c1) $f(x+y)\le f(x)+f(y)$ $\forall x,y\in\mathbb Z$ c2) $\forall x$, $\exists y$ such that $f(x)=f(x-y)+f(y)$ Let $m=\min_{x\in Z}f(x)$ ($m\ge 0$) Let $u$ such that $f(u)=m$ Using c2, $\exists v$ such that $m=f(u)=f(u-v)+f(v)\ge 2m$ and so $m=0$ Let $A=\{x\in\mathbb Z$ such that $f(x)=0\}$. Note that $0\notin A$ c1) implies then : c3) $a,b\in A$ implies $a+b\in A$ If all elements of $A$ are $>0$ : c2 is wrong for $x=\min (A)$ If all elements of $A$ are $<0$ : c2 is wrong for $x=\max (A)$ So $\exists a=\min(A\cap\mathbb Z_{>0})$ and $b=-\max(A\cap\mathbb Z_{<0})$ Let $u=\gcd(a,b)$ $\exists$ nonnegative integers $m,n,p,q$ such that $ma+n(-b)=u$ and $pa+q(-b)=-u$ Then , using c3, ge get that $u,-u\in A$ and so $u+(-u)=0\in A$, impossible And so $\boxed{\text{No such function}}$
14.02.2021 06:59
pco wrote: mruczek wrote: Determine, whether exists function $f$, which assigns each integer $k$, nonnegative integer $f(k)$ and meets the conditions: $f(0) > 0$, for each integer $k$ minimal number of the form $f(k - l) + f(l)$, where $l \in \mathbb{Z}$, equals $f(k)$. Note that $\min_{y\in Z}(f(x-y)+f(y))=f(x)$ is equivalent to : c1) $f(x+y)\le f(x)+f(y)$ $\forall x,y\in\mathbb Z$ c2) $\forall x$, $\exists y$ such that $f(x)=f(x-y)+f(y)$ Let $m=\min_{x\in Z}f(x)$ ($m\ge 0$) Let $u$ such that $f(u)=m$ Using c2, $\exists v$ such that $m=f(u)=f(u-v)+f(v)\ge 2m$ and so $m=0$ Let $A=\{x\in\mathbb Z$ such that $f(x)=0\}$. Note that $0\notin A$ c1) implies then : c3) $a,b\in A$ implies $a+b\in A$ If all elements of $A$ are $>0$ : c2 is wrong for $x=\min (A)$ If all elements of $A$ are $<0$ : c2 is wrong for $x=\max (A)$ So $\exists a=\min(A\cap\mathbb Z_{>0})$ and $b=-\max(A\cap\mathbb Z_{<0})$ Let $u=\gcd(a,b)$ $\exists$ nonnegative integers $m,n,p,q$ such that $ma+n(-b)=u$ and $pa+q(-b)=-u$ Then , using c3, ge get that $u,-u\in A$ and so $u+(-u)=0\in A$, impossible And so $\boxed{\text{No such function}}$ Sorry , but why $\min_{y\in Z}(f(x-y)+f(y))=f(x)$ is equivalent to $f(x+y)\le f(x)+f(y)$ $\forall x,y\in\mathbb Z$ ?
14.02.2021 07:10
@above put $x+y$ in $x$
16.02.2021 17:54
tommy2007 wrote: @above put $x+y$ in $x$ oh thanks