ВЫЧИСЛЕНИЯ

Разные аспекты получения нового знания на основе некоторого набора входных данных: вычисления и их свойства

Шахматная доска и прямая линия

Шестая задача вступительной контрольной работы на отделение математики на 2011/2012 год (открытый лицей “Всероссийская заочная многопредметная школа” при МГУ им.  М. В. Ломоносова) .

ДАНО:

Имеется шахматная доска 8×8 и длинная линейка.  Линейку кладут на доску. Какое максимальное количество клеток она может пересечь.

РЕШЕНИЕ:

Будем считать, что пересечение клетки доски линейкой (длинной стороной линейки) имеет место, если точек пересечения две и они лежат на разных сторонах квадрата, связанного с клеткой. Вот примеры пересечений:
Для упрощения рассмотрения изобразим доску размером 3×3 и произвольную прямую:

Легко видеть, что доска образована пересечением двух наборов параллельных прямых – 4 горизонтальных и 4 вертикальных, расположенных на одинаковом расстоянии друг от друга. При этом, очевидно, что стороны квадрата любой из клеток на доске лежат на этих двух наборах параллельных прямых.  Таким образом, чем больше линейка пересекает прямых из двух наборов параллельных прямых, тем больше она пересекает клеток. При этом точки пересечения линейки с прямыми не должны совпадать с точками пересечениями прямых из указанных двух наборов между собой, так как в этом случае мы не сможем говорить о пересечении линейкой некоторых клеток.
Для того чтобы линейка пересекала больше вертикальных прямых (в пределах доски) необходимо, чтобы она пересекала левую и правую сторону доски (В этом случае будет выполнено пересечение всех 4-х вертикальных прямых). При таких ограничениях максимум пересечений с горизонтальными прямыми будет достигнут, если линейка будет начинаться в левом нижнем углу доски и заканчиваться в правом верхнем. При этом останутся не пересеченными лишь две прямые. Линейка пересечет в этом случае 5 клеток:
Легко заметить, что для произвольного n максимальное число пересечений равно 2n-1. Для доски 8×8 максимальное число пересечений равно 16-1=15.

Оставьте комментарий