Find all integer $c\in\{0,1,...,2016\}$ such that the number of $f:\mathbb{Z}\rightarrow\{0,1,...,2016\}$ which satisfy the following condition is minimal: (1) $f$ has periodic $2017$ (2) $f(f(x)+f(y)+1)-f(f(x)+f(y))\equiv c\pmod{2017}$ Proposed by William Chao
Problem
Source: 2017 Taiwan TST 2nd round day 2 P4
Tags: function, algebra, combinatorics, number theory, functional equation
v_Enhance
15.04.2017 14:58
問一下, "2nd round day 2" 是指獨立研究第二天，還是模擬競賽第二天？ I think this problem was proposed by GSJL.
YaWNeeT
15.04.2017 16:55
模擬競賽，以前AoPS上的Taiwan TST好像都是用Quiz代表獨研，Day代表模競，所以我才寫Day 2 XDD
YaWNeeT
19.04.2017 05:02
Answer:$c=1,1008,1009,2016$ ,and the number of $f$ is $2017$.
Let's consider this question in $\mathbb{Z}/2017\mathbb{Z}$
Note that $(cx+k)$ satisfies the condition (where $k=0,1,...,2016$). First, I'll prove there is other solution when $c\neq 1,1008,1009,2016$:
When $c\neq 0$ ,let $f_0(2017n+1)=f_0(2017n+c+1)=f_0(2017n+2c+1)=c$, and let $f_0(x)=0$ for the others.$f_0(x)+f_0(y)$ can only be $0,c,2c$,but since $c\neq 1,1008,1009,2016$, we have $0,c,2c\notin \{1,c+1,2c+1\}$, so $f_0(f_0(x)+f_0(y))=0$ and $f_0(f_0(x)+f_0(y)+1)=c$. So $f_0$ satisfies the condition, and $f_0$ is different from $cx+k$.
When $c=0$,let $f_0(2017n+6)=f_0(2017n+7)=3$, and let $f_0(x)=1$ for the others.$f_0(x)+f_0(y)$ can only be $2,4,6$ ,and $f_0(2)=f_0(3)=f_0(4)=f_0(5)$，$f_0(6)=f_0(7)$ ,so $f_0$ satisfies the condition, and $f_0$ is different from $cx+k$.
Next, I'll prove when $c=1,1008,1009,2016$, all solutions are $cx+k$:
Assume $f$ is a solution satisfies the condition, we we'll prove $f$ is onto first. If $f$ is not onto, we can find a longest "good sequence" $\{a_i\}_{i=1}^r$ in the range of $f$,where "good sequence" means a sequence in the form $a_i=ci+d$. Since $2017$ is a prime ,and $f$ is not into,the longest good sequence we can find has finite length. Substitute $(x,y)$ into (2) such that $(f(x),f(y))=(a_i,a_j)$,$i,j=1,2,...,r$:
When$c=1$,let $b_i=f(a_1+a_i),b_{r+1}=f(a_1+a_r+1)$.
When$c=1008$,let $b_i=f(a_{r+1-i}+a_{r+1-i}),b_{r+1}=f(2a_1+1)$.
When$c=1009$,let $b_i=f(a_i+a_i),b_{r+1}=f(2a_r+1)$.
When$c=2016$,let $b_i=f(a_1+a_{r+1-i}),b_{r+1}=f(2a_1+1)$.
Then we have $\{b_i\}_{i=1}^{r+1}$ as a longer good sequence, a contradiction!So $f$ is onto ,and we get $f(x+1)-f(x)\equiv c\pmod{2017},\forall x$.So there exists $k$ such that $f(x)=cx+k$.
pad
01.09.2020 04:14
The answer is $c=1,2016,1008,1009$. Work entirely in $\mathbb{F}_{2017}$. Let $P(x,y)$ denote the FE. Claim: For $c=1$ and $c=2016$, we must have $f(z)=cz+C$ for some constant $C$. Proof: Suppose $c=1$. Then $P(x,0)$ gives $f(f(x)+f(0)+1) = f(f(x)+f(0))+1$. Adding $f(0)$ to both sides and letting $g(x)=f(x)+f(0)$ makes this $g(g(x)+1) = g(g(x))+1$, i.e. \[ y \in \text{Im}(g) \implies g(y+1)=g(y)+1. \](For $c=2016$, this is analogously $g(y+1)=g(y)-1$, and the following argument is very similar with this adjustment.) Now, consider a graph $G$ with vertices $0,1,\ldots,2016$ and draw an arrow $z\to z+1$ iff $z\in \text{Im}(g)$. Consider the maximal consecutive subsequence in the set $\text{Im}(g)$ and call it $a,a+1,\ldots,b$; this is a maximal path of $G$. Note that $g(a),g(a+1),\ldots,g(b) \in \text{Im}(g)$, and \[ g(a+1)=g(a)+1, \ g(a+2)=g(a+1)+1, \ \ldots, \ g(b+1)=g(b)+1.\]Hence $g(a),\ldots,g(b+1)$ is also a path in $G$. But it is longer, contradicting maximality. Therefore, $G$ has no paths. Since the image is nonempty, $G\not = \emptyset$, hence it has a cycle. If $k$ is the length of the cycle, we need $g(a+k)=g(a)$, i.e. $g(a)+k=g(a)$, so we must have $k=2017$. Therefore, $G=C_{2017}$. But this means $g$ is surjective, since it hits every element; hence $\text{Im}(g) = \{0,1,\ldots,2016\}$. Therefore, $g(y+1)=g(y)+1$ for all $y$, which means $g(y)=y+C$ for some constant $C$, as claimed. $\blacksquare$ Claim: For $c=1008$ and $c=1009$, we must have $f(z)=cz+C$ for some constant $C$. Proof: WLOG $c=1009$ (the case $c=1008$ is very similar). Using the same setup as the previous claim, consider instead the maximal path for $g(2z)$, operating $g$ twice changes the $+1009$ to a $+1$. $\blacksquare$ A corollary of the claim is that there are exactly 2017 such functions for $c= \pm 1, \pm 1008$. Using this information, we can eliminate all the bad $c$. Claim: For a fixed $c\not \in \{1,2016,1008,1009\}$, there are more than 2017 functions that work. Proof: Note that $P(x,y)$ rewrites as \[ f(z+1) = f(z) + c, \ \ \forall z \in \text{Im}(f) + \text{Im}(f). \]If $c=0$, take $\text{Im}(f)=\{0,1\}$ and $f(0)=f(1)=1$ and all others 0. Else, take $\text{Im}(f)=\{0,c\}$, so that $\text{Im}(f) + \text{Im}(f)=\{0,c,2c\}$. So we must have $f(1)=f(0)+c$, $f(c+1)=f(c)+c$, and $f(2c+1)=f(2c)+c$. Hence \[ f(1)=f(c+1)=f(2c+1)=c, \qquad f(0)=f(c)=f(2c)=0\]since the narrow image of $f$ forces this. This works since $\{0,1,c,c+1,2c,2c+1\}$ are pairwise distinct by our assumption about $c$. Now, there are $2^{2011}>2017$ options for all the other values of $f$; these all work since the only restrictions were on the determined 6 values of $f$. $\blacksquare$
Really hard problem. The hardest part about this problem is getting a foothold to work from, and realizing the main steps to the solution. I quickly realized that actually solving (finding all solutions) to the FE for all $c$ except $c=1$ would be way too hard; in particular, once I rephrased the FE in terms of the image of $f$, it is very hard to control the image unless $c=\pm 1$. Proving linear for $c=\pm 1$ is like a problem on its own -- a problem on arrows.
After this, the only way to handle the $c\not = \pm1$ cases it to just construct a lot of pathological solutions, and prove its more than 2017; this is again like a problem of its own. The idea here is to use the image rephrasing of the FE to make a construction with a very narrow image to force stuff. But this construction fails for $c=\pm 1008$, and handling this on its own requires thought but is not too hard given the ideas of $c=\pm 1$.
i3435
27.01.2023 04:02
Initially I thought ans was only $c=1$, oops. Work $\bmod 2017$. The answer is $c=1,-1,\frac{1}{2},-\frac{1}{2}$. Let $P(x,y)$ be the FE. The FE always has the solution $f(x)=cx+d$ for any $d$, so there are at least 2017 solutions. For $c\neq 1,-1,\frac{1}{2},-\frac{1}{2}$, we can show that there exists an additional solution. If $c=0$, then the solution $f(x)=0$ if $x\neq 69$ and $f(x)=1$ if $x=69$ works. If $c\neq 0$, then let $f(0)=f(c)=f(2c)=0$ and let the other outputs of $f$ be $c$. This above construction hinges on the fact that $0,c,2c,1,c+1,2c+1$ are all distinct. I give an outline that if $c=1,-1,\frac{1}{2},-\frac{1}{2}$, the FE only has the linear solutions. Suppose $k$ is the largest integer such that $f(a),f(a+1),\dots ,f(a+k)$ is an arithmetic sequence with common difference $c$ for these $c$. Then by considering $P(f(a+k),f(a+k)),P(f(a+k),f(a+k-1)),P(f(a+k-1),f(a+k-1)),\dots , P(f(a),f(a))$, if $k\neq 2017$ then $k$ is not maximal. However if $k$ is $2017$, then the function is linear, as desired.
YaoAOPS
29.04.2023 23:07
We claim that the values of $c$ are $1$, $1008$, $1009$, and $2016$. Define $c \cdot g(x) = f(x)$ such \[ g(c \cdot (g(x) + g(y)) + 1) \equiv g(c \cdot (g(x) + g(y))) + 1 \pmod{2017} \] It remains to find the number of functions of the form $g$. Let $I$ be the image, and define \[ S = \{c(i_1 + i_2) \mid i_1, i_2 \in I\} \]Then, for $s \in S$, \[ f(s + 1) \equiv f(s) + 1 \pmod{2017} \] Claim: If $c = 1, 1008, 1009, 2016$, then there are only $2017$ possible functions. Proof: There exists a $k$ such $f(k + 1) \equiv f(k) + 1 \pmod{2017}$. Then, $I$ contains $f(k)$ and $f(k) + 1$ so $S$ contains $cf(k), cf(k) + c, 2f(k) + 2c$. We can repeat this, as $n$ consecutive values in $I$ implies $n$ consecutive values in $S$, and $n$ consecutive values in $S$ implies $n+1$ consecutive values in $I$. This forces $f(x + 1) = f(x) + 1$ which eventually leaves exactly $2017$ functions of the form $f(x) = x + c$. We now construct a counter example for other $c$. Let $I = \{0, 1\}$ so $S = \{0, c, 2c\}$, none of which are consecutive. Then set $f(0) = f(c) = f(2c) = 0$, $f(1) = f(c + 1) = f(2c + 1) = 1$, and the remaining values can be set arbitrarily, which leaves a result larger than $2017$.