Задача 1: Из квадрата клетчатой бумаги размером 2ⁿ × 2ⁿ вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на «уголки» из трёх клеток ().

Задача 2: Докажите, что любую сумму, начиная с 8 тугриков, можно выплатить купюрами по 3 тугрика и 5 тугриков.

Задача 3: Приведите пример натурального числа, которое равно сумме а) трёх своих различных делителей; б) ста своих различных делителей.

Задача 4: Докажите, что при каждом натуральном n, начиная с 3, существует выпуклый n-угольник, имеющий ровно три острых угла.

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

Задача 6: [Игра «Ханойская башня»] Имеется пирамида с n кольцами возрастающих размеров (внизу – самое большое) и еще два пустых стержня той же высоты. Разрешается перекладывать верхнее кольцо с одного стержня на другой, но при этом запрещается класть большее кольцо на меньшее. Докажите, что

а) можно переложить все кольца с первого стержня на один из пустых стержней;

б) это можно сделать не более, чем за 2ⁿ – 1 перекладываний.

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

Задача 8: В прямоугольнике 3 × n (3 строки, n столбцов) расставлены фишки трёх цветов по n штук каждого цвета. Докажите, что переставляя фишки в строчках, можно сделать так, чтобы в каждом столбце были фишки всех трёх цветов.

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