Задача 1: Можно ли раскрасить клетки квадратной доски 5 × 5 в 5 цветов так, чтобы в каждой строке и в каждом столбце были клетки всех пяти цветов, а поля каждого цвета можно было обойти ходом шахматного коня, не заходя дважды ни на какую клетку?

Решение: Нельзя. Небольшой перебор показывает, что любой путь шахматного коня, имеющий длину 5 и проходящий через центральную клетку, не удовлетворяет условиям задачи.

Задача 2: Укажите хотя бы одно натуральное N, при котором число N⁴ + (N + 1)⁴ составное.

Решение: При N=18 данное число делится на 17.

Задача 3: Дан граф с 2k вершинами нечетной степени (и каким-то количеством вершин четной степени), все ребра которого равны по длине 1, и набор из k «нитей", суммарна длина которых равна сумме длин всех ребер графа. Обязательно ли из этих «нитей" можно сложить данный граф?

Решение: Не обязательно. Контрпример состоит из трех равносторонних треугольников, пристроенных к хвостам буквы Т. Сумма длин ребер равна 12. Вершин нечетной степени – 4. Две нити длины 10 и 2 не могут покрыть граф, т.к. длинная нить не может проходить по всем трем треугольникам.

Задача 4: Из 11 шаров 2 радиоактивны. Про любой набор шаров за одну проверку можно узнать, имеется ли в нем хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Можно ли за 7 проверок найти оба радиоактивных шара?

Решение: Можно. Разобьем шары на 5 групп по 2 шара и еще один шар. Проверим эти 5 групп. Если две из них радиоактивные, то из каждой радиоактивный шар выделяется за одну проверку. Если радиоактивна только одна группа, проверяем оба шара в ней.