\documentclass[a4paper,11pt]{article}
\usepackage{circle,russcorr}
\setcounter{задача}{0}
\begin{document}
\заголовок{18 февраля 2004 г.}{Индукция}{17}

Пусть дана цепочка утверждений $A_1, A_2, \ldots, A_k, \ldots$\quad
Известно, что $A_1$ верно. Также известно, что утверждения
$A_1\Rightarrow A_2, A_2\Rightarrow A_3, \ldots, A_k\Rightarrow
A_{k+1}, \ldots$ верны. \Те у нас есть пронумерованные утверждения,
причём $A_k$ влечёт за собой $A_{k+1}$. Тогда все утверждения верны,
\тк $A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow \ldots\Rightarrow
A_n$ для произвольного $n$.

\bigskip

\z АО ``Пень\д инвент'' решило вырубить реликтовый сосновый лес, но
экологи запротестовали. Тогда гендиректор АО ``Пень\д инвент'' всех успокоил,
сказав: \лк В лесу $99\%$ сосен. Мы будем рубить только
сосны. После рубки их останется $98\%$ от всех деревьев\пк. Какую
часть леса хочет вырубить ``Пень\д инвент''?

\medskip

\z В последовательности $1, 1, 2, 3, 5, 8, 13, \ldots$ каждое
следующее число равно сумме двух предыдущих. \p Могут ли в ней
оказаться рядом два чётных числа? \p два числа, делящиеся на $13$?

\z В комнате с незеркальными стенами расставляют перегородки, одна
сторона которых зеркальная, а другая~--- нет. Докажите, что всегда
найдётся комната, в которой нет ни одного зеркала.

\z В некоторой стране каждые два города соединены либо автомобильной,
либо железной дорогой. Докажите, что либо из любого города в любой
другой можно добраться на автомобиле, либо из любого города в любой
другой можно добраться на поезде.

\z Докажите, что для любого натурального $n$ найдётся $n$-значное
число, делящееся на $2^n$, и в десятичной записи которого есть только
единицы и двойки.

\z (Ханойские башни) Имеется три стержня и несколько колец разного
размера. Вначале все кольца нанизаны по порядку на один стержень 
(внизу~--- самое большое кольцо). За один ход можно
переложить кольцо с одного стержня на другой, но так, чтобы кольцо
большего размера не лежало на меньшем. \p Докажите, что можно
перенести все кольца с одного стержня на другой. \pp За какое
наименьшее число ходов это можно сделать?

\end{document}
