Сколько делителей числа 20! × 21! являются точными квадратами или точными кубами?
(Для любого натурального числа величина ! (факториал натурального числа
) определяется как произведение всех натуральных чисел от 1 до включительно: ! = 1 × 2 × 3 × · · · × ( − 1) × .)
Ответы
Запишем число 20! · 21! как умножение чисел:
20! · 21! = 1 · 2 · 3 · 4 · ... · 19 · 20 · 1 · 2 · 3 · ... · 19 · 20 · 21
Перепишем данное число максимально кратко:
1 · 2 · 3 · 4 · ... · 19 · 20 · 1 · 2 · 3 · ... · 19 · 20 · 21 = 1² · 2² · 3² · ... · 20² · 21
1² · 2² · 3² · ... · 20² · 21 = 2² · 3² · 2⁴ · 5² · (2² · 3²) · 7² · ... · 19² · (5² · 2⁴) · 3 · 7
Сгруппировав степени простых чисел, получаем:
20! · 21! = 2³⁶ · 3¹⁷ · 5⁸ · 7⁵ · 11² · 13² · 17² · 19²
Стоит понимать, что любое нужное нам число (то есть точные квадраты или кубы) мы можем записать с помощью всех записанных выше простых чисел в каком то своей степени. Причем, у каждого может быть независимо своя степень.
Точные квадраты:
Точными квадратами будут те числа, степени в простых делителях которых будут парными.
То есть, для множителя 2 возможно 19 способов: 0, 2, 4, 6, 8, ... , 32, 34, 36
Для множителя 3 возможно (17-1)/2 + 1 = 9 способов
и так далее.
Итого:
2 - 19; 3 - 9; 5 - 5; 7 - 3, 11 - 2, 13 - 2, ..., 19 - 2.
Исходя из правила произведения в комбинаторике, общее количество точных квадратов равно произведению всех способов у каждого простого множителя:
P₁ = 19 · 9 · 5 · 3 · 2 · 2 · 2 · 2 = 41040
Точные кубы:
Аналогично квадратам, но, единственное, количество способов меньше для каждого делителя:
13 для цифры 2
6 для цифры 3
3 для цифры 5
2 для цифры 7
и по 1 для дальнейших чисел, поскольку дальше идут лишь квадраты. Итого:
P₂ = 13 · 6 · 3 · 2 = 468
Но есть один нюанс:
Существуют точные шестые степени. Множество точных квадратов и кубов имеют множество точных шестых степеней. Поскольку эти шестые степени включаются дважды в нашем подсчете, нужно убрать один его подсчет.
Точные шестые степени:
7 способов для числа 2
3 способа для числа 3
2 способа для числа 5
и дальше по одному способу
Итого - P₃ = 42
Общее количество точных квадратов и кубов: P = P₁ + P₂ - P₃ = 41040 + 468 - 42 = 41466
Ответ: 41466