Читать онлайн «Математическая индукция»

А. Шень Математическая индукция Москва Издательство МЦНМО 2005 А. Шень Математическая индукция Издание второе, исправленное Москва Издательство МЦНМО 2004 ББК 22. 1 Ш47 Шень А. Ш47 Математическая индукция. — 2-е изд. , испр. — М. : МЦНМО, 2004. — 36 с: ил. ISBN 5-94057-138-7 В брошюре рассказывается (для школьников 7-11 классов) о методе математической индукции на примере 29 задач, из которых 19 снабжены подробными решениями. ББК 22. 1 Оригинал-макет предоставлен автором. Рисунки изготовлены автором в системе MetaPost. Иногда называют «неполной индукцией» переход от частных примеров к общим закономерностям. Бывает индукция и в физике (катушки индуктивности, явление самоиндукции). Но в этой брошюре мы говорим только о математической (полной) индукции. Что это такое, проще всего объяснить на примерах. Разберём несколько задач. Задача 1. Несколько прямых делят плоскость на части. Доказать, что можно раскрасить эти части в белый и чёрный цвет так, чтобы соседние части (имеющие общий отрезок границы) были разного цвета (как на рисунке 1). Рис. 1. Двуцветная раскраска. Решение. Заметим прежде всего, что не любую «карту» (части — страны, разделённые линиями границ) можно так раскрасить. Например, если Рис. 2. Карта, которую нельзя раскрасить в два цвета. 3 на рис. 2 верхняя страна белая, то две другие должны быть чёрными, хотя граничат между собой. Но для плоскости, разрезанной на части прямыми, такого случиться не может, и мы сейчас это докажем. Пусть прямая только одна. Тогда всё просто: одна полуплоскость белая, другая — чёрная (рис. 3). Рис. 3. Белая и чёрная полуплоскости. Если прямых две, получатся четыре части (рис. 4). Рис. 4. Две прямые, четыре части. Посмотрим, что произойдёт, если мы проведём третью прямую. Она поделит некоторые страны; при этом появятся новые участки границы, по обе стороны которых цвет один и тот же (рис. 5). Как же быть? С одной стороны от новой прямой поменяем цвета (белый сделаем чёрным и наоборот). Тогда новая прямая будет всюду разделять участки разного цвета. Другими словами, с одной стороны от прямой мы 4 Рис. 5. Новая прямая, берём позитив карты, а с другой — негатив (рис. 6). Рис. 6. Изменение цвета с одной стороны. (Придирчивый читатель спросит: а почему старые границы раскрашены правильно? Это легко понять: в позитивной части цвета не изменились, а в негативной оба цвета заменились на противоположные. ) Теперь ясно, что тем же способом можно добавить ещё одну прямую (перекрасив карту с одной стороны от неё), затем ещё одну и так далее — пока мы не получим нужную нам карту. Задача решена. Задача 2. Число 111 делится на 3, число 111 111 111 делится на 9, число 111... 111 (27 единиц) делится на 27. Доказать, что число 111 ... 111 {У1 единиц) делится на У1 при любом п.