Решение задачи 394

Условие:

Какое наибольшее количество диагоналей клеток шахматной доски можно провести так, чтобы никакие две из них не имели ни одной общей точки?

Решение:

Оценка:
Раскрасим узлы шахматной доски в черный и белый цвета в шахматном порядке как показано на рисунке.

Нетрудно видеть, что любая диагональ соединяет вершины одного цвета. Назовем диагональ черной, если она соединяет вершины черного цвета и белой иначе. Белых вершин 40, черных 41, отсюда следует, что белых диагоналей не более 20 и черных диагоналей не более 20, то есть всего диагоналей не более 40. Покажем, что черных диагоналей на самом деле меньше.

Рассмотрим квадрат 2×2 с покрашенными в шахматном порядке вершинами:

Нетрудно видеть, что в нем можно провести максимум одну черную диагональ (сохраняя условие задачи). Исходный большой квадрат состоит из 16 маленьких квадратиков 2×2. Отсюда следует, что в исходном квадрате 8×8 можно провести максимум 16 черных диагоналей. Значит всего диагоналей максимум 36.

Пример:

Ответ: 36.