Maths Olympiad Prep

Library / /783 of 860

Combinatorics Difficulty 5.6 AIME, harder Find the answer

Let S={1,2,,2021}S=\{1,2, \ldots, 2021\}, and let F\mathcal{F} denote the set of functions f:SSf: S \rightarrow S. For a function fFf \in \mathcal{F}, let Tf={f2021(s):sS}T_{f}=\left\{f^{2021}(s): s \in S\right\} where f2021(s)f^{2021}(s) denotes f(f((f(s))))f(f(\cdots(f(s)) \cdots)) with 2021 copies of ff. Compute the remainder when fFTf\sum_{f \in \mathcal{F}}\left|T_{f}\right| is divided by the prime 2017, where the sum is over all functions ff in F\mathcal{F}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The key idea is that tTft \in T_{f} if and only if fk(t)=tf^{k}(t)=t for some k>0k>0. To see this, let sSs \in S and consider s,f(s),f(f(s)),,f2021(s)s, f(s), f(f(s)), \ldots, f^{2021}(s) This sequence has 2022 terms that are all in SS, so we must have a repeat. Suppose fm(s)=fn(s)f^{m}(s)=f^{n}(s) with 0n<m20210 \leq n<m \leq 2021. Then f2021(s)=f2021+mn(s)f^{2021}(s)=f^{2021+m-n}(s). In particular, for t=f2021(s)t=f^{2021}(s), we have fk(t)=tf^{k}(t)=t with k=mnk=m-n. On the other hand, if fk(t)=tf^{k}(t)=t, then letting s=f2021k2021(t)s=f^{2021 k-2021}(t) gives f2021(s)=tf^{2021}(s)=t. We will compute the number of ff for which fk(1)=1f^{k}(1)=1 for some kk, and then multiply by 2021. We do this by casework on the minimum possible value of kk. Given kk, we just need to choose distinct values in {2,,2021}\{2, \ldots, 2021\} for each of f1(1),f2(1),,fk1(1)f^{1}(1), f^{2}(1), \ldots, f^{k-1}(1). We have 2020!(2021k)!\frac{2020!}{(2021-k)!} ways to do this. For each of the 2021k2021-k other values with ff not yet determined, we can do anything we want, giving 20212021k2021^{2021-k} choices. So, fFTf=2021k=120212020!(2021k)!20212021k\sum_{f \in \mathcal{F}}\left|T_{f}\right|=2021 \sum_{k=1}^{2021} \frac{2020!}{(2021-k)!} \cdot 2021^{2021-k} Taking this mod 2017, all terms with k>4k>4 reduce to 0, and 20212021k2021^{2021-k} reduces to 45k4^{5-k} for k4k \leq 4. We are thus left with fFTf4[44+343+3242+32141]255(mod2017)\sum_{f \in \mathcal{F}}\left|T_{f}\right| \equiv 4\left[4^{4}+3 \cdot 4^{3}+3 \cdot 2 \cdot 4^{2}+3 \cdot 2 \cdot 1 \cdot 4^{1}\right] \equiv 255 \quad(\bmod 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.