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

Кружок 8 класса

Листок 5. Раз дощечка, два дощечка — будет лесенка

1.

Имеются три стержня, на один из них надета пирамидка из нескольких колец различного диаметра (меньшее кольцо лежит на большем), два других — пустые. Разрешается перекладывать кольца с одного стержня на другой по одному, так чтобы большее кольцо никогда не лежало на меньшем. Докажите, что можно переместить всю пирамидку с исходного стержня на один из пустых, если в пирамидке:

a) 2 кольца; b) 3 кольца; c) 5 колец; d) n колец.

2.

Рассмотрим уголок . Он получается вырезанием из квадрата 2× 2 одной клетки. Можно ли разрезать на такие уголки квадрат следующих размеров без одной клетки (вырезана может быть любая клетка квадрата, даже откуда-то из середины)?

a) 4×4 b) 8×8 c) 128×128 d) 2n×2n.

3.

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

4.

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

5.

Докажите, что для любого натурального n справедливы неравенства:
a) 2ⁿ > n;
b) 1 + 2 + … + n ≤ n².

6.

Докажите, что для произвольного натурального n верно равенство: 1 + 3 + … + (2n−1) = n².

7.

В пробирке живут амёбы. Каждую минуту происходит следующее: каждая амёба делится пополам, после чего в пробирку добавляют еще одну такую же амёбу. В начальный момент времени там была всего одна амёба. Докажите, что через n минут в пробирке будет (2ⁿ⁺¹−1) амёба.

8*.

Какое минимальное количество перекладываний нужно, чтобы переложить пирамидку с одного стержня на другой в задаче 1?