7 В каждой клетке квадрата 8 х 8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагона- лей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть а) больше 15? б) больше 20?

Ответ: а) да, может; б) нет, не может.

Решение:

• а) Может ли количество этих частей быть больше 15?

  Да, может. Рассмотрим случай, когда во всех клетках проведены диагонали одного направления (например, все из левого верхнего угла в правый нижний). Тогда все диагонали образуют одну связную часть. Если в каждой клетке провести диагонали противоположного направления, то получим 64 отдельные связные части. Варьируя направления диагоналей, можно получить любое количество связных частей от 1 до 64, включая число больше 15.

• б) Может ли количество этих частей быть больше 20?

  Нет, не может. Максимальное количество связных частей достигается, когда каждая диагональ проведена отдельно, и они не соединяются друг с другом. В квадрате 8x8 всего 64 клетки, следовательно, и 64 диагонали. Таким образом, максимальное количество связных частей равно 64. Число связных частей не может быть больше 20, так как максимальное количество частей 64, а это число конечно.

Ответ: а) да, может; б) нет, не может.