Maths Olympiad Prep

Library / /4 of 4

Number theory Difficulty 4.9 AIME Prove it Philippines

Problem:
Find the number of functions ff from the set S={0,1,2,,2020}S=\{0,1,2, \ldots, 2020\} to itself such that, for all a,b,cSa, b, c \in S, all three of the following conditions are satisfied:
(i) If f(a)=af(a)=a, then a=0a=0;
(ii) If f(a)=f(b)f(a)=f(b), then a=ba=b; and
(iii) If ca+b(mod2021)c \equiv a+b(\bmod 2021), then f(c)f(a)+f(b)(mod2021)f(c) \equiv f(a)+f(b)(\bmod 2021).

Solution

Solution:
Note that, from (i), our function is completely determined by f(1)f(1); i.e., f(a)af(1)f(a) \equiv a f(1) (mod2021)(\bmod 2021). Then, from (i) and (ii), we need that f(a)0f(a) \neq 0 if a0a \neq 0; otherwise, if a0a \neq 0 but f(a)=0,f(b)=f(a+b)f(a)=0, f(b)=f(a+b) for any bb. Thus, if a0a \neq 0, we need that af(1)0(mod2021)a f(1) \neq 0(\bmod 2021) for any aS\{0}a \in S \backslash\{0\}. If gcd(f(1),\operatorname{gcd}(f(1), 2021)=d>1,thennotethat, then note that a=2021dS\{0}a=\frac{2021}{d} \in S \backslash\{0\},andfrom(i),, and from (i), f(a) \equiv a f(1) 20210(mod\equiv 2021 \equiv 0(\bmod 2021). As we just established, this is not allowed. Hence, gcd(f(1),\operatorname{gcd}(f(1), 2021)=1.

Moreover, from (iii), we need that f(a)=af(1)≢a(mod2021)f(a)=a f(1) \not \equiv a(\bmod 2021) if a0a \neq 0; in other words, 2021a(f(1)1)2021 \nmid a(f(1)-1) if a0a \neq 0. By similar reasoning to earlier, suppose that gcd(f(1)1,2021)=d>1\operatorname{gcd}(f(1)-1,2021)=d>1.Then. Then a=2021dS\{0}a=\frac{2021}{d} \in S \backslash\{0\},and, and 2021 \mid a(f(1)-1);thus,; thus, f(a)=a.Wethusneedthatgcd(f(1)1,2021)=1. We thus need that \operatorname{gcd}(f(1)-1,2021)=1 as well.

We count the number of integers that satisfy both these conditions. We use complementary counting here; thus, we start by counting those that fail to satisfy at least one condition. Indeed, we count the number of values of f(1)f(1) that are not coprime to 2021. Either they are divisible by 43, or 47, or both. Since only 0 is divisible by both, by the principle of inclusion and exclusion, there are 47+431=8947+43-1=89 possible values of f(1)f(1) so that f(1)f(1) is not coprime to 2021. By the same reasoning, there are also 89 possible values of f(1)f(1) such that f(1)1f(1)-1 is not coprime to 2021. Finally, we count the values of f(1)f(1) for which neither f(1)f(1) nor f(1)1f(1)-1 is coprime to 2021. This happens precisely when 43f(1)43 \mid f(1) and 47f(1)147 \mid f(1)-1, or 47f(1)47 \mid f(1) and 43f(1)143 \mid f(1)-1. By the Chinese remainder theorem, each of these possibilities gives one value of f(1)f(1). Thus, by the principle of inclusion and exclusion, there are 2892=1762 \cdot 89-2=176 such values of f(1)f(1) that fail to satisfy at least one condition. This gives us 2021176=18452021-176=1845 possible values of f(1)f(1), and thus possible functions ff.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.