Олимпиадная задача Изместьева: периметры многоугольников на шахматной доске
Из бесконечной шахматной доски вырезали многоугольник со сторонами, идущими по сторонам клеток. Отрезок периметра многоугольника называется черным, если примыкающая к нему изнутри многоугольника клетка – черная, соответственно белым, если клетка белая. Пусть A – количество черных отрезков на периметре, B – количество белых, и пусть многоугольник состоит из a черных и b белых клеток. Докажите, что A-B=4(a-b).
Разобрать решение
Посчитаем стороны всех клеток, составляющих многоугольник,
следующим образом: из количества сторон черных клеток вычтем
количество сторон белых клеток. Эта величина равна4(a-b),
так как у каждой клетки четыре стороны, в то же время каждый
отрезок, лежащий внутри многоугольника, был посчитан один
раз со знаком + и один раз – со знаком - .
То есть полученная величина равна сумме отрезков периметра
с соответствующими знаками: + для черных и - для белых, откуда и получаем требуемое равенство.
Задачу можно решать по индукции, при доказательстве индуктивного
перехода отбрасывая от многоугольника одну граничную клетку.
При этом многоугольник может развалиться на несколько, и
удобнее доказывать формулу не для одного многоугольника,
а для совокупности. Число вариантов расположения отбрасываемой
клетки может быть доведено до двух:
,
(с тремя сторонами, выходящими на периметр, и с двумя).
Обсуждение
0Комментариев пока нет.