МАЛЫЙ МЕХМАТ МГУ

Можно ли квадрат 4×4 с вырезанной угловой клеткой разрезать на уголки из трёх клеток? А квадрат 8×8 с вырезанной угловой клеткой? А 16×16? Сформулируйте и докажите общее утверждение.
 

На плоскости проведены несколько прямых, которые разбивают плоскость на области. Докажите, что эти области можно так раскрасить в два цвета, чтобы соседние области были разноцветными (соседними называются области, имеющие общий отрезок границы).
 

Докажите, что при любом натуральном n число 15ⁿ + 6 делится на 7.
 

Докажите, что при любом натуральном n число 7ⁿ + 12n + 17 кратно 18.
 

Докажите, что 4ⁿ > 7n – 5 при всех натуральных n.
 

Докажите равенство (1 – 1/4)(1 – 1/9)...(1 – 1/n²) = (n + 1)/(2n).
 

(Ханойская башня.) Есть три стержня, на один из которых надеты n колец разного радиуса (снизу — самое большое кольцо, потом — поменьше, и т. д., верхнее — самое маленькое). Разрешается снимать по одному кольцу и перекладывать на другой стрежень, при этом большее кольцо нельзя класть на меньшее.
а) Докажите, что такими операциями можно всю пирамиду перенести на другой стержень.
б) Докажите, что это можно сделать за 2ⁿ – 1 перекладываний.
в) Докажите, что меньшим числом перекладываний обойтись невозможно. (В частности, если пирамидка состоит из 20 колец, то потребуется 2²⁰ – 1 перекладываний, что чуть больше миллиона; и, если совершать по одному перекладыванию в секунду, то с задачей можно справиться чуть больше, чем за 12 суток (если работать не переставая). Если же пирамидка состоит из 30 колец, то на ее перемещение потребуется уже 34 года (при ежесекундом перемещении колец без сна и обеда).
 

Найдите ошибку в следующем рассуждении.

Теорема. Любые 100 точек лежат на одной прямой.

Доказательство. Докажем более сильное утверждение, а именно: любые n точек лежат на одной прямой, где n - произвольное натуральное число. Будем рассуждать по индукции. Очевидно, любая одна точка лежит на некоторой прямой. Индуктивный переход: предположим, доказано, что всякие k точек лежат на одной прямой, и докажем, что тогда и всякие k + 1 точек лежат на одной прямой. Возьмем произвольные k + 1 точек A₁, A₂, ..., A_k, A_{k + 1}. По индуктивному предположению точки A₁, A₂,..., A_k лежат на одной прямой l₁ (ведь их k штук), и точки A₂, ..., A_{k + 1} тоже лежат на одной прямой l₂ (их тоже k). Остаётся лишь заметить, что прямые l₁ и l₂ совпадают, поскольку точки A₂, ..., A_k лежат на каждой из них. Теорема доказана.