Математикадан Эйлер олимпиадасы, 2011-2012 оқу жылы, Дистанциялық кезеңнің 2-ші туры

$15 \times 15$ квадраты $1 \times 1$ шаршыларына бөлінген. Осы шаршылардан бірнешеуін таңдап алып, әрқайсысында бір немесе екі диагоналін жүргізген. Жүргізілген диагональдар арасында ешқандай екеуінің ортақ соңы жоқ екені белгілі. Ең көп дегенде қанша диагональ жүргізілуі мүмкін? (Есепті шешу барысында жауабын, диагональдарды жүргізу әдісін және осы диагональдар саны ең көп екенін дәлелде.)

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

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