Диагональ правильного 2006-угольника P называется хорошей, если её концы делят границу P на две части, каждая из которых содержит нечётное число сторон. Стороны P также называются хорошими. Пусть P разбивается на треугольники 2003 диагоналями, никакие две из которых не имеют общих точек внутри P. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?

   Решение

Темы:    [ Эйлерова характеристика ] [ Шахматная раскраска ]

Сложность: 2+ Классы: 6,7

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

Условие

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

Решение

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

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