Решение задачи 394
Никита ЖуковскийУсловие:
Какое наибольшее количество диагоналей клеток шахматной доски можно провести так, чтобы никакие две из них не имели ни одной общей точки?
Решение:
Оценка:
Раскрасим узлы шахматной доски в черный и белый цвета в шахматном порядке как показано на рисунке.
![](/file/9d81fb69e8b9c4f16641f.png)
Нетрудно видеть, что любая диагональ соединяет вершины одного цвета. Назовем диагональ черной, если она соединяет вершины черного цвета и белой иначе. Белых вершин 40, черных 41, отсюда следует, что белых диагоналей не более 20 и черных диагоналей не более 20, то есть всего диагоналей не более 40. Покажем, что черных диагоналей на самом деле меньше.
Рассмотрим квадрат 2×2 с покрашенными в шахматном порядке вершинами:
![](/file/a0eabd3f7fd21e2ea1022.png)
Нетрудно видеть, что в нем можно провести максимум одну черную диагональ (сохраняя условие задачи). Исходный большой квадрат состоит из 16 маленьких квадратиков 2×2. Отсюда следует, что в исходном квадрате 8×8 можно провести максимум 16 черных диагоналей. Значит всего диагоналей максимум 36.
Пример:
![](/file/ded7d91b2573cd542c744.png)
Ответ: 36.
![](/file/b033ce9ebe27d42c6fa07.png)