Количество делителей числа 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 ключ.





Закрыть