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

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

Руководители Сергей Александрович Дориченко и Степан Львович Кузнецов
2009/2010 учебный год

Занятие 17

1.
Могут ли и сумма, и произведение нескольких натуральных чисел быть равными 99?
2.
Что больше: 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 или 2048?
3.
Докажите, что любое число рублей, большее семи, можно разменять купюрами в 3 и 5 рублей.

Индукция

4.
Из доски размером а) 4×4; б) 16×16; в) 2n×2n вырезана одна произвольная клетка. Как разрезать оставшуюся доску на «уголки» из трёх клеток?
5.
На плоскости нарисовано несколько попарно пересекающихся окружностей (каждая окружность пересекается с любой другой). Докажите, что эту картинку можно обвести „одним росчерком”, то есть не проходя по одной дуге два раза и не отрывая карандаша от бумаги, и при этом вернуться в начальную точку.
6.
Ханойские башни. Имеются три стержня, на один из них надета пирамидка из а) двух; б) трёх; в) пяти; г) n колец различного диаметра (меньшее кольцо лежит на большем), два других — пустые. Разрешается перекладывать кольца с одного стержня на другой по одному, так чтобы большее кольцо никогда не лежало на меньшем. Как переместить всю пирамидку с исходного стержня на один из пустых?
7.
У бородатого многоугольника во внешнюю сторону растет щетина. Его пересекает несколько прямых, на каждой из которых с одной из сторон тоже растет щетина. В результате многоугольник оказался разбитым на некоторое число частей. Докажите, что хотя бы у одной из частей вся борода окажется снаружи.
8.
Докажите, что если плоскость разбита на части прямыми и окружностями, то получившуюся карту можно раскрасить в два цвета так, что части, граничащие по дуге или отрезку, будут разного цвета.

Дополнительные задачи

9.
Какое наименьшее количество перекладываний потребуется, чтобы переложить пирамидку с одного стержня на другой в задаче 6?
10.
В прямоугольнике 3×n стоят фишки трёх цветов, по n штук каждого цвета. Докажите, что можно переставить фишки в каждой строке так, чтобы в любом столбце были фишки всех трёх цветов.
11.
На какое наибольшее количество частей могут разбить плоскость n прямых?