Let , and let denote the set of functions . For a function , let where denotes with 2021 copies of . Compute the remainder when is divided by the prime 2017, where the sum is over all functions in .
Solution
The key idea is that if and only if for some . To see this, let and consider This sequence has 2022 terms that are all in , so we must have a repeat. Suppose with . Then . In particular, for , we have with . On the other hand, if , then letting gives . We will compute the number of for which for some , and then multiply by 2021. We do this by casework on the minimum possible value of . Given , we just need to choose distinct values in for each of . We have ways to do this. For each of the other values with not yet determined, we can do anything we want, giving choices. So, Taking this mod 2017, all terms with reduce to 0, and reduces to for . We are thus left with
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.