Maths Olympiad Prep

Library / /270 of 397

Algebra Difficulty 6.3 National Olympiad Prove it Taiwan

Find all integers c{0,1,,2016}c \in \{0, 1, \dots, 2016\} such that the number of functions f:Z{0,1,,2016}f: Z \rightarrow \{0, 1, \dots, 2016\} satisfying the following two conditions is minimized:
(1) The function ff has period 20172017;
(2) f(f(x)+f(y)+1)f(f(x)+f(y))c(mod2017)f(f(x) + f(y) + 1) - f(f(x) + f(y)) \equiv c \pmod{2017}.

Note: Here ZZ denotes the set of all integers.

Solution

What we want are c=1,1008,1009,2016c = 1, 1008, 1009, 2016, and the number of ff is 20172017.
Let a%ba\%b denote the remainder of aa divided by bb, where 0a%b<b0 \le a\%b < b.
Note that (cx+k)%2017(cx + k)\%2017 satisfies the condition (where k=0,1,,2016k = 0, 1, \dots, 2016).

In the following, we'll prove there is another solution when c1,1008,1009,2016c \ne 1, 1008, 1009, 2016:
When c0c \ne 0, let
f0(2017n+1)=f0(2017n+c+1)=f0(2017n+2c+1)=c, f_0(2017n + 1) = f_0(2017n + c + 1) = f_0(2017n + 2c + 1) = c,
let f0(x)=0f_0(x) = 0 for the others. (f0(x)+f0(y))%2017(f_0(x) + f_0(y))\%2017 can only be 0,c,2c%20170, c, 2c\%2017,
but since c1,1008,1009,2016c \ne 1, 1008, 1009, 2016, we have
0,c,2c%2017{1,(c+1)%2017,(2c+1)%2017}0, c, 2c\%2017 \notin \{1, (c+1)\%2017, (2c+1)\%2017\},
so
f0(f0(x)+f0(y))=0f_0(f_0(x) + f_0(y)) = 0, and f0(f0(x)+f0(y)+1)=cf_0(f_0(x) + f_0(y) + 1) = c.
So f0f_0 satisfies the condition, and f0f_0 is different from (cx+k)%2017(cx + k)\%2017.

Let f0(x)=1f_0(x) = 1 for the others. (f0(x)+f0(y)%2017f_0(x) + f_0(y)\%2017 can only be 2,4,62, 4, 6, and
f0(2)=f0(3)=f0(4)=f0(5)=f0(6)=f0(7), f_0(2) = f_0(3) = f_0(4) = f_0(5) = f_0(6) = f_0(7),
so f0f_0 satisfies the condition, and f0f_0 is different from (cx+k)%2017(cx + k)\%2017.

Next, we'll prove when c=1,1008,1009,2016c = 1, 1008, 1009, 2016, all solutions are (cx+k)%2017(cx + k)\%2017:
Assume ff is a solution satisfying the condition, we'll prove ff is onto first. If ff is not onto, we can find a longest "good sequence" {ai}i=1r\{a_i\}_{i=1}^r in the range of ff, where "good sequence" means a sequence in the form ai=(ci+d)%2017a_i = (ci + d)\%2017. Since 20172017 is a prime, and ff is not onto, the longest good sequence we found has finite length.

Substitute (x,y)(x, y) into (2) such that (f(x),f(y))=(ai,aj),i,j=1,2,,r(f(x), f(y)) = (a_i, a_j), i, j = 1, 2, \dots, r:
When c=1c = 1, let bi=f(a1+ai),br+1=f(a1+ar+1)b_i = f(a_1 + a_i), b_{r+1} = f(a_1 + a_r + 1).
When c=1008c = 1008, let bi=f(ar+1i+ar+1i),br+1=f(2a1+1)b_i = f(a_{r+1-i} + a_{r+1-i}), b_{r+1} = f(2a_1 + 1).
When c=1009c = 1009, let bi=f(ai+ai),br+1=f(2ar+1)b_i = f(a_i + a_i), b_{r+1} = f(2a_r + 1).
When c=2016c = 2016, let bi=f(a1+ar+1i),br+1=f(2a1+1)b_i = f(a_1 + a_{r+1-i}), b_{r+1} = f(2a_1 + 1).
Then we have {bi}i=1r+1\{b_i\}_{i=1}^{r+1} as a longer good sequence, contradiction! So ff is onto, and we get f(x+1)f(x)c(mod2017)f(x+1) - f(x) \equiv c \pmod{2017}, x\forall x. So there exists kk such that f(x)=(cx+k)%2017f(x) = (cx + k)\%2017.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.