AoPS - Problem

Source: 2021China South East Mathematical Olympiad Grade 10 P5

Tags: Sequence, number theory

Generals

29.07.2021 08:33

To commemorate the $43rd$ anniversary of the restoration of mathematics competitions, a mathematics enthusiast arranges the first $2021$ integers $1,2,\dots,2021$ into a sequence $\{a_n\}$ in a certain order, so that the sum of any consecutive $43$ items in the sequence is a multiple of $43$. (1) If the sequence of numbers is connected end to end into a circle, prove that the sum of any consecutive $43$ items on the circle is also a multiple of $43$; (2) Determine the number of sequences $\{a_n\}$ that meets the conditions of the question.

(1) By the condition, $a_i \equiv a_{43 + i} \pmod{43}$ for every $i$. (Using the convention $a_{2021 + i} = a_i$) It is easy to see that this observation solves (1). (2) For every residue class modulo $43$, there are exactly $47$ numbers in it from $\{1,2, \dots , 2021\}$. Thus, we must have $\{a_1 , a_2 , \dots , a_{43}\} = \{0,1, \dots , 42\}$ in modulo $43$. There are $43!$ number of ways to distribute the residues and, for each of them, since there are $47$ numbers congruent to that residue, there are $47!$ number of ways to arrange them. Thus, our answer is $43! \cdot (47!)^{43}$.