Таблицы Брадиса

При к 1 утверждение очевидно.

При к 1 утверждение очевидно.

Элементы математики в задачах - Г. А. Мерзон

Задача 14. Докажите, что если а + - целое, то ак + \ целое при любом к.

Решение. Для доказательства задачи воспользуемся обощенным принципом математической индукции.

База индукции. При к = 1 утверждение очевидно.

Шаг индукции. Пусть а + ^ целое, и ак + ^ целое для всех к, не превосходящих К (в частности, для к = К и для к = К - 1). Докажем тогда, что и аК+1 + будет целым. Рассмотрим равенство:

(а + ±) • [ак + = (,1К+1 + + (а*-1 +                                      .

Левая часть — целое число, так как она является произведением це­лых чисел (они целые по предположению). В правой части число, записанное во вторых скобках, также является целым по предполо­жению индукции. Значит, число в первых скобках тоже целое.

Задача 15*. В классе каждый болтун дружит хотя бы с одним молчу­ном. При этом болтун молчит, если в кабинете находится нечетное число его друзей-молчунов. Докажите, что учитель может выгнать из класса не более половины учеников так, чтобы все болтуны молчали.

Решение. Будем называть группу школьников этого класса «молча­ливой», если после удаления из класса остальных школьников все болтуны этой группы молчат. Заметим, что в задаче фактически требуется найти «молчаливую» группу школьников, содержащую не менее половины класса.

Воспользуемся обобщенным принципом математической индук­ции. База индукции для п = 3 очевидна.

Метод математической индукции                          117

Шаг индукции. Предположим, что утверждении задачи выполнено для любого класса, в котором не более N человек. Рассмотрим класс, в котором N +1 человек. Если в классе ровно один молчун, то класс уже молчит, и никого выгонять не надо. Пусть теперь в классе хотя бы два молчуна. Назовем одного из них Саша. Пусть с Сашей дружит к человек. По предположению индукции, среди остальных N — к учени­цу          N — к ков найдется «молчаливая» группа М не менее чем из —— учеников.