Количество делителей числа N
Прежде чем перейти к рассмотрению задачи о количестве делителей произвольного числа, решим вспомогательные задачи. Пусть студенту на сдачу выдали 5 одинаковых рублей, которые он положил в два кармана. Сколько существует вариантов расклада 5 рублей по двум карманам? Построим таблицу расклада.
1-й карман 5 р., 4 р., 3 р., 2 р., 1 р., 0 р.
2-й карман 0 р., 1 р., 2 р., 3 р., 4 р., 5 р.
Итого существует 6 вариантов расклада. Если раскладывается n предметов на 2 кучки, то существует n + 1 вариант.
Если раскладываются предметы нескольких типов на 2 кучки (ящики, корзины, множества), то такой расклад выполняется независимо для каждого типа предметов и результаты перемножаются.
IIример. Имеются цветы трех видов: 10 васильков, 15 незабудок, 12 ромашек. Требуется разложить их на 2 букета. Васильки на 2 букета можно разложить 11 способами, незабудки - 16, ромашки - 13 способами. Поскольку расклад каждого вида цветов выполняется независимо, то общее число вариантов расклада будет: 11 · 16 · 13.
Обобщим полученный результат. Пусть имеется предметов 1-го типа, - 2-го, ... - к-то. Требуется разложить эти предметы на 2 кучки.
Тогда полное число вариантов расклада равно ( +1)( +1)...( +1). Пусть имеется некоторое число N. Требуется определить количество делителей N.
Решение. Представим N в канонической форме, т. е.
Тогда задача о нахождении числа делителей N сводится к задаче раскладки степеней простых чисел на 2 делителя: т. е. решение будет:
Пример. N= 600 = Число делителей равно (3+1)(1+1 )(2+1) = 24.
Упражнения
1. Сколько делителей имеют числа: 1350, 1617, 8280, 10013?
2. Сколько вариантов при раскладке в домино?
3. Сколько разных ожерелий можно составить из 5 изумрудов, 4 рубинов и 6 сапфиров?
4. В вагон международного поезда, в купе которого имеется 2 дивана по 5 мест на каждом, входит 10 пассажиров. Из вошедших 4 человека хотят сидеть по ходу поезда, 3 против хода, а остальным - безразлично. Сколько вариантов рассадки пассажиров имеется у проводника вагона?
При решении комбинаторных задач для нахождения числа благоприятных комбинаций иногда удобнее вычислить число неблагоприятных комбинаций и вычесть их количество из общего числа комбинаций.
Пример 1. Из n различных чисел требуется отобрать k таких, чтобы в выбранное множество не входили s конкретных чисел. Общее число выборов из n по k:
Выберем теперь s конкретных чисел и остальные доберем способами. Это будет число неблагоприятных комбинаций. Число благоприятных комбинаций определится разностью
IIример 2. Из труппы в 15 человек нужно отобрать бригаду в которую должно входить не менее 5 человек. Сколько имеется вариантов выбора?
Подсчитаем число неблагоприятных комбинаций выбора, т. е. со¬ставим варианты бригад из 1,2,3,4 человек. Их количество равно:
= 15 + 105 + 455 + 1365 = 1940.
А общее количество бригад равно - 1. Разность дает число благоприятных комбинаций.
Упражнения
1. Обобщите решение последней задачи, если выбор выполняется из n человек, а в бригаду должно войти не менее k человек.
2. Сколько чисел меньших миллиона можно написать с помощью цифр а) 5. 6, 7; 6)3, 0, 9; в) 5, 7 ?
3. Найдите сумму всех трехзначных чисел, которые можно написать с помощью цифр 1, 2, 3, 4. Решите ту же задачу, если никакая цифра не должна повторяться дважды в записи каждого числа.
4. Комиссия из 7 человек хранит свои материалы в сейфе. Сколько должно быть замков на сейфе и сколько должно быть ключей у каждого члена комиссии, чтобы сейф мог быть открыт, если соберутся вместе не менее 4 членов комиссии, но не мог быть открыт при меньшем числе членов комиссии?
Для решения последней задачи можно использовать так называемые "равновесные" коды. Равновесными кодами длины n веса k называются двоичные последовательности длины n, содержащие ровно k единиц ( и n - k нулей). Число таких кодов определяется выражением:
Р(k, n -k). Выпишем, например, все коды длины 5 веса 3:
1)1 1 1 0 0
2) 1 1 0 1 0
3) 1 1 0 0 1
4) 1 0 1 1 0
5) 1 0 1 0 1
6) 1 0 0 1 1
7) 0 1 1 1 0
8) 0 1 1 0 1
9) 0 1 0 1 1
10) 0 0 1 1 1
Легко заметить, что каждый столбец содержит 6 единиц и 4 нуля. Кроме того, если взять любые два столбца и поставить их рядом, то всегда найдется комбинация 00. Если же взять три любых столбца, то комбинации 000 не будет.
Если теперь считать номера строк 1), 2),...,10) номерами ключей, а каждый столбец рассматривать как способ выдачи ключей конкретному члену комиссии, то мы получим решение поставленной задачи при 5 членах комиссии и пороговом значении h = 3. Если теперь построить таблицу кодов длины 7 веса 4, мы получим решение исходной задачи.
Полученное решение легко обобщить на произвольное число членов комиссии n и произвольный порог h. Действительно, если построить таблицу равновесных кодов длины n веса k, то число ключей будет равно Р(n, n - k) = n!((n - k)!k!), а сейф может быть открыт если соберется число членов комиссии равное h = n — k + 1.
Так, например, пусть n = 4, h = 3, т. е. число членов комиссии равно 4, а сейф должен открываться, если соберется не менее 3 членов комиссии. В общем случае k = n - h + 1.
Для конкретного примера k = 4 - 3 + 1 = 2; т. е. нужно построить таблицу равновесных кодов длины 4 веса 2:
1) 1 1 0 0
2) 1 0 1 0
3) 1 0 0 1
4) 0 1 1 0
5) 0 1 0 1
6) 0 0 1 1
Из таблицы видно, что сейф должен иметь в этом случае 6 замков, а ключи должны распределяться в соответствии с таблицей равновесных кодов, т. е. первый член комиссии (первый столбец) получает 1, 2 и 3 ключ, второй член комиссии получает 1, 4 и 5 ключ, третий член комиссии получает 2, 4 и 6 ключ и четвертый член комиссии получает 3, 5 и 6 ключ.