Число сторон многоугольника A₁...A_n нечётно. Докажите, что:
  а) если этот многоугольник вписанный и все его углы равны, то он правильный;
  б) если этот многоугольник описанный и все его стороны равны, то он правильный.

   Решение

Назовём лабиринтом шахматную доску 8×8, на которой между некоторыми полями поставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа находится край доски или перегородка, остаётся на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Программист пишет программу – конечную последовательность указанных команд, и даёт её пользователю, после чего пользователь выбирает лабиринт и помещает в него ладью на любое поле. Верно ли, что программист может написать такую программу, что ладья обойдёт все доступные поля в лабиринте при любом выборе пользователя?

   Решение

Тема:    [ Вспомогательная раскраска (прочее) ]

Сложность: 6 Классы: 8,9

Прислать комментарий

Условие

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

Решение

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

Источники и прецеденты использования