Районная олимпиада, 2020-2021 учебный год, 9 класс

Сколько делителей числа $20! \cdot 21!$ являются точными квадратами или точными кубами? (Для любого натурального числа $n$ величина $n!$ (факториал натурального числа $n$) определяется как произведение всех натуральных чисел от 1 до $n$ включительно: $n! = 1\cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n.$)

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 82506.
Решение. Обозначим $S=20 ! \cdot 21 !$. Пусть $A$ — число делителей $S$, являющиеся полным квадратом, $B$ — полным кубом, $C$ — полной шестой степенью. Тогда ответом задачи будет число $A+B-C.$ Разложим $S$ на простые множители: $$S=20 ! \cdot 21 !=2^{36} \cdot 3^{17} \cdot 5^{8} \cdot 7^{5} \cdot 11^{2} \cdot 13^{2} \cdot 17^{2} \cdot 19^{2}.$$ Любой делитель числа $S$ можно представить в виде $$2^{a} \cdot 3^{b} \cdot 5^{c} \cdot 7^{d} \cdot 11^{e} \cdot 13^{f} \cdot 17^{g} \cdot 19^{h},$$ где $0 \leq a \leq 36,$ $0 \leq b \leq 17,$ $0 \leq c \leq 8,$ $0 \leq d \leq 5,$ $0 \leq e \leq 2,$ $0 \leq f \leq 2,$ $0 \leq g \leq 2,$ $0 \leq h \leq 2.$ Делитель числа $S$ будет точным квадратом, если показатели степеней простых чисел в его каноническом разложении будут кратны 2. Для показателя $a$ существует всего 19 вариантов $(a \in \{0,2,4,\ldots,36\})$, для числа $b$ 9 вариантов $(b \in\{0,2,4 \ldots, 16\}),$ для $c$ 5 вариантов $(c \in\{0,2,4,6,8\}),$ для $d$ 3 варианта $(d \in\{0,2,4\}),$ для $e$ 2 варианта $(e \in\{0,2\}),$ для $f$ 2 варианта $(f \in\{0,2\})$ для $g$ 2 варианта $(g \in\{0,2\}),$ для $h$ 2 варианта $(h \in\{0,2\})$. По правилу произведения, $$ A=19 \cdot 9 \cdot 5 \cdot 3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 =41040.$$ Аналогично, рассматривая возможные показатели, кратные 3, получим $$ B=13 \cdot 6 \cdot 3 \cdot 2 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1=468. $$ И, наконец, рассматривая возможные показатели, кратные 6, получим $$ C=7 \cdot 3 \cdot 2 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1=42. $$ Тогда $$A+B-C=41040+468-42=41466.$$

Разложим $20! \cdot 21!$ на простые множители:

$20! \cdot 21!=2^{36} \cdot 3^{17} \cdot 5^8 \cdot 7^5 \cdot 11^2 \cdot 13^2 \cdot 17^2 \cdot 19^2$

Пусть $A$ - кол-во делителей данного числа, являющимися также и полными квадратами, $B$ - точными кубами, $C$ - и полными квадратами, и полными кубами, т.е. точными шестыми степенями, т.к. если некоторое число - полный квадрат, в его каноническом разложений (или разложений на простые сомножители), все степени простых чисел - четные, если точный куб - кратны трем, и выходит, все степени делятся и на 2, и на 3, а $[2,3]=6$.

По правилу включений и исключений, искомый икс в задаче равен $A+B-C$.

A) Если $p_1^{\alpha_1}...p_n^{\alpha_n}$ является делителем данного числа, то, $\{p_1,.., p_n \} \subset \{2, 3, 5, 7, 11, 13, 17, 19 \}$, и соответственно, степень простого числа делителя должно быть не больше степени этого же простого числа в каноническом разложений делимого числа. Если $p_1^{\alpha_1}...p_n^{\alpha_n}$ - полный квадрат, то $\forall i, 2|{\alpha_i}$, для данных $\alpha_i$. Тогда, если $d$ - соответствующий свойствам $A$ делитель, то $d=2^{2\alpha_1} \cdot 3^{2\alpha_2} \cdot ... \cdot 19^{2\alpha_8}$, где, $\alpha_1 \le 18, \alpha_2 \le 8, ..., \alpha_8 \le 1$, причем некоторые из $\alpha_i$-тых могут быть равны нулю. По правилу умножения комбинаторики, получаем, $A=19 \cdot 9 \cdot 5 \cdot 3 \cdot 2^4$.

B, C) Аналогично, $B=13 \cdot 6 \cdot 3 \cdot 2, C=7 \cdot 3 \cdot 2$.

Ответ: $19 \cdot 9 \cdot 5 \cdot 3 \cdot 2^4+13 \cdot 6 \cdot 3 \cdot 2-7 \cdot 3 \cdot 2=41466$ делителей.