|
|
 |
Условие
В каждой клетке квадрата 8×8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть больше
а) 15;
б) 20?
в) Может ли в аналогичной задаче про квадрат n×n клеток получиться больше чем n²/4 частей (для n > 8)?
Решение
б) См. рисунок к задаче 98192.
в) Для квадрата n×n клеток аналогично можно составить многосвязную компоненту, разбитую на прямоугольники d×2d, где d – длина диагонали клетки (сторона клетки считается равной 1), так, что непокрытая ею площадь квадрата – бордюр – будет составлена из равнобедренных прямоугольных треугольников с гипотенузами 4 или с катетами 4, 3 или 2, лежащими на сторонах квадрата (см. рис.).
В прямоугольнике d×2d площади 4 и треугольнике с гипотенузой 4 и той же площади размещается по одной компоненте; в угловых треугольниках площади S = 8 – 3 компоненты, площади S = 4,5 – 2 компоненты, площади S = 2 – одна компонента. Так как отношение S к числу компонент для каждого случая меньше 4, то (даже если не считать "многосвязную" компоненту) общее число компонент не меньше четверти площади квадрата, то есть не меньше n²/4.
Замечания
Эта задача дает любопытный пример ситуации, которую физики назвали бы "нарушением симметрии": в оптимальном расположении, наши "частицы" – диагонали – оказываются исполняющими разные роли: одни объединяются в одну большую общую компоненту, а другие живут поодиночке.
