Олимпиада имени Леонарда Эйлера2011-2012 учебный год, II тур дистанционного этапа

Квадрат $15 \times 15$ разбит на квадратики $1 \times 1$. Из этих квадратиков выбрали несколько, и в каждом из выбранных провели одну или две диагонали. Оказалось, что никакие две проведенные диагонали не имеют общего конца. Какое наибольшее число диагоналей может быть проведено? (В решении приведите ответ, способ проведения диагоналей и доказательство того, что это число диагоналей действительно наибольшее возможное.)

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 128.
Решение. Занумеруем по порядку строки и столбцы квадрата числами от 1 до 15 и проведем по две диагонали в клетках, стоящих на пересечении нечетных строк с нечетными столбцами. Таких клеток 64, то есть диагоналей будет проведено 128. С другой стороны, у диагоналей не должно быть общих концов, а вершин клеток в квадрате $15 \times 15$ у нас всего $16 \times 16 = 256$. Поэтому диагоналей можно провести не больше, чем $256:2 = 128$.