МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ и КОМБИНАТОРИКА

Решения

1. (9-10) Докажите, что  делится на 6.
Решение. При  выражение  делится на 8. Предположим, что при  выражение имеет вид , то есть делится на 6. Тогда , т.е.  делится на 6 и при , так как  - целое число. Следовательно,  делится на 6 при любом n.

2. (9-10) Докажите, что для любого натурального  справедливо неравенство .
Решение. При  и   имеем  , следовательно,  .

3. (8-10) Докажите: .
Решение. Обозначим .
I.  . Итак, равенство справедливо при .
II. Предположим, что верно равенство . 
Тогда 
 что и требовалось доказать.

4. (8-10) Докажите: .
Решение. При  равенство выполняется. Допустим равенство выполняется при , то есть  или . Тогда при    имеем 
 .
5. (9-10) Известно, что  - целое число. Докажите, что  - также целое число при любом целом .
Решение. I.  При    - целое число.
II. Предположим, что число   целое при любом натуральном . Тогда   - целое число, но  Вторая скобка в правой части – целое число (по индуктивному предположению), сумма двух скобок – целое число, значит, первое слагаемое   - то же целое число. Следовательно  - целое число при любом целом .
6. (9-10) Докажите, что при любом натуральном  число  делится на  и не делится на .
Решение. Обозначим .
I.  При   имеем . Итак,  делится на  и не делится на .
II. Пусть при   число  делится на  и не делится на , т.е. , где М не делится на 3. Тогда  

. Очевидно, что  делится на  и не делится на . Следовательно, утверждение доказано для любого натурального  .

7. (8-10) Сколькими способами можно раскрасить круг, разбитый на  равных секторов с помощью  красок, если  – простое число  и каждый сектор раскрашиваем одной краской? Две раскраски, совпадающие при повороте  круга, считаем одинаковыми.
Решение. Каждый сектор можно раскрасить в любой из  цветов, поэтому для круга с  секторами получим   раскрасок, среди которых   не одноцветных. Каждая из этих раскрасок поворотами переходит в   одинаковую с ней, значит, существенно различных не одноцветных раскрасок будет , откуда общее число раскрасок равно .

8. (8-10) Каких чисел больше среди целых чисел первой тысячи, включая и 1000: в записи которых есть хоть одна единица, или среди цифр которых единиц нет?
Решение. Числа первой тысячи, в записи которых нет единицы, это те, у которых цифра сотен, десятков и единиц – любая из 9 цифр 0, 2, 3, …, 9, но надо исключить 0 (как последовательность трех нулей), поэтому таких чисел имеется  Значит, чисел, у которых есть цифра 1, имеется  Итак, больше чисел, в записи которых нет цифры 1.

9. (8-10) Из цифр 1, 2, 3, 4, 5, 6, 7 составляют всевозможные семизначные числа, в записи которых каждая цифра участвует только один раз. Докажите, что сумма всех этих чисел делится на 9.
Решение. Всего чисел . В каждом разряде каждая цифра встречается  раз, поэтому сумма цифр в любом разряде равна  
 и делится на 9, т.к. равна .

10. (9-10) На окружности отмечены 10 точек. Сколько можно провести незамкнутых несамопересекающихся ломаных с вершинами во всех этих точках?
Решение. Возьмем одну из точек в качестве начала ломаных. Тогда для проведения первого звена – две возможности, второго – тоже две возможности (т.к. следующая выбираемая вершина будет одной из двух соседних с построенным звеном) и так далее, до построения восьмого звена включительно, которое соединит последнюю вершину построенной ломаной с одной из двух оставшихся точек, для построения же последнего – девятого звена – уже нет выбора и имеется лишь одна возможность. Так мы строим  ломаных, один из двух концов которых находится в выбранной точке, но любая из 10 точек может быть началом, поэтому  - удвоенное число ломаных (т.к. каждую ломаную будем подсчитывать дважды, меняя роли начала и конца), а общее число ломаных .