A function equation

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A function equation

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: 2017 Taiwan TST 2nd round day 2 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

64 posts

#1 h Apr 15, 2017, 2:58 AM • 5 Y

Y by v_Enhance, ThE-dArK-lOrD, crazyeyemoody907, Adventure10, Mango247

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

This post has been edited 4 times. Last edited by YaWNeeT, Apr 13, 2018, 1:18 PM
Reason: meow

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

528 posts

USJL

#2 h Apr 15, 2017, 8:26 AM • 1 Y

Y by Adventure10

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6857 posts

#3 h Apr 15, 2017, 11:58 AM • 3 Y

Y by v4913, crazyeyemoody907, Adventure10

問一下, "2nd round day 2" 是指獨立研究第二天，還是模擬競賽第二天？

I think this problem was proposed by GSJL.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

64 posts

#4 h Apr 15, 2017, 1:55 PM • 3 Y

Y by v_Enhance, Adventure10, Mango247

模擬競賽，以前AoPS上的Taiwan TST好像都是用Quiz代表獨研，Day代表模競，所以我才寫Day 2 XDD

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

64 posts

#5 h Apr 19, 2017, 2:02 AM • 2 Y

Y by v_Enhance, Adventure10

This post has been edited 1 time. Last edited by YaWNeeT, Apr 19, 2017, 2:20 AM
Reason: my poor English

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#6 h Sep 1, 2020, 1:14 AM • 5 Y

Y by hellomath010118, Nuterrow, crazyeyemoody907, chystudent1-_-, Lcz

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$

Remarks

This post has been edited 1 time. Last edited by pad, Sep 1, 2020, 1:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1349 posts

i3435

#7 h Jan 27, 2023, 1:02 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1484 posts

#8 h Apr 29, 2023, 8:07 PM

Y by

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$ .

This post has been edited 1 time. Last edited by YaoAOPS, Apr 29, 2023, 8:07 PM
Reason: spacing

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8844 posts

#9 h Yesterday at 4:00 AM

Y by

The answers are $c \in \{1, 1008, 1009, 2016\}$ . In fact, we will prove the following assertion:

Claim: If $c \in \{1, 1008, 1009, 2016\}$ , the only functions that work are the linear functions $f(n) \equiv cn + b \pmod {2017}$ .

Proof: Let $S$ denote the range of $f$ . For each nonnegative integer $k$ , we let a chain of length $k$ denote a sequence $\{r, r+1, \dots, r+(k-1)\}$ of residues all in $S$ . We will show that for every positive integer $k$ , there is a chain of length $k$ in $S$ , which will imply that $S = \mathbb F_{2017}$ .

The proof goes by induction. For the base case, there clearly exists a chain of length one. For the inductive step, suppose that we have a chain of length $k-1$ , say $\{r, r+1, \dots, r+(k-2)\}$ . Then, let $n_i$ denote the residue such that $f(n_i) = r + i$ for each $0 \leq i \leq k-2$ .

First, assume $c = \varepsilon \in \{-1, 1\}$ . By the given condition,
$\begin{align*} f(2r+1) - f(2r) &= f(f(n_0) + f(n_0) + 1) - f(f(n_0) + f(n_0)) = \varepsilon \\ f(2r+2) - f(2r+1) &= f(f(n_0) + f(n_1) + 1) - f(f(n_0) + f(n_1)) = \varepsilon \\ \vdots &\phantom= \vdots \\ f(2r+2k-3) - f(2r+2k-4) &= f(f(n_{k-2}) + f(n_{k-2}) + 1) - f(f(n_{k-2}) + f(n_{k-2})) = \varepsilon. \end{align*}$ So the sequence $\{f(2r), f(2r+1), \dots, f(2r+2k-3)\}$ is a chain of length $2k-2 \geq k-1$ for all $k \geq 2$ .

Next, assume that $2c = \varepsilon \in \{-1, 1\}$ , for the $c = \{1008, 1009\}$ case. Then, adding pairs of the equations above reads $f(2r + 2i + 2) -f(2r + 2i) = 2c = \varepsilon$ for each $0 \leq i \leq k-3$ . These $k-2$ equations yield that $\{f(2r), f(2r+2), \dots, f(2r+2k-4)\}$ is a chain of length $k-1$ . Similarly, $\{f(2r+1), f(2r+3), \dots, f(2r+2k-3)\}$ is a chain of length $k-1$ . In particular, $f(2r+1) = f(2r) + c$ .

Applying the same process on both of these chains, we get a chain of length $k-1$ beginning at $f(2f(2r) + \varepsilon)$ given by $\{f(2f(2r) + 2i + \varepsilon)\}_{i=0}^{k-2}$ and a chain of length $k-1$ beginning at $f(2f(2r+1) - \varepsilon) = f(2f(2r) - \varepsilon)$ given by $\{f(2f(2r) + 2i - \varepsilon)\}_{i=0}^{k-2}$ . Concatenating these chains yields a chain of length $k$ , finally. $\blacksquare$

So now $S = \mathbb F_{2017}$ , hence $S + S = \mathbb F_{2017}$ , hence $f$ must be linear. $\blacksquare$

On the other hand, for any $c \not \in \{1, 1008, 1009, 2016\}$ , the function $f$ defined by $f(2) = 1$ , $f(3) = c+1$ , $f(c+2) = 1$ , $f(c+3) = c+1$ , $f(2c+2) = 1$ , $f(2c+3) = c+1$ , and $f(n) = 1$ for $n$ not any of these values, noting that the inputs we designated are distinct, satisfies the condition, in addition to all classes of linear functions. Thus there are strictly more functions $f$ when $c \not \in \{1, 1008, 1009, 2016\}$ , as needed.

Remark: This is really hard for problem 4. Seeing and proving the $c \in \{1008, 1009\}$ case is especially tricky; it's quite easy to miss and one doesn't see it until the end, and the inductive argument is a mess to write up.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a