Есть квадрат $%5\times 5$%. В любой единичный квадратик (клеточку $%1\times 1$%) можно вписать только одну диагональку, при условии, что эта диагональка не будет касаться других вписанных ранее диагоналек в другие единичные квадраты. Сколько всего можно вписать таких диагоналек?

[под словами "Сколько всего можно вписать таких диагоналек" подразумевается максимальное количество?]

задан 9 Апр '15 16:53

10|600 символов нужно символов осталось
2

Пример с 15 линиями строится очень легко. Я длительное время пытался доказать, что это число и есть максимальное, пока не обнаружил, что есть пример и с 16 линиями.

Здесь проще всего было бы нарисовать картинку, но у меня нет такой возможности, поэтому придётся описать пример словами. Линии в этом примере переходят в себя при повороте на 90 градусов вокруг центра. В каждой из угловых клеток проводится диагональ так, что угловая вершина оказывается "отрезанной". Расположений линий можно дать следующей символической схемой, где $%+$% означает диагональ, параллельную прямой $%y=x$%, а $%-$% означает диагональ, параллельную $%y=-x$%. Там, где диагональ не проводится, указываем $%0$%.

$%+++\,0-$%

$%0\,0\,+0\,-$%

$%--\,0--$%

$%-\,0+0\,0$%

$%-\,0+++$%

Тот факт, что нельзя провести более 16 линий, обосновывается так. Всего имеется 36 узлов на клетчатой решётке в пределах квадрата $%5\times5$%. Если линий 17, то свободны всего 2 узла. Заметим, что узлов на границе 20, и они соединены либо с узлами следующего "слоя", которых всего имеется 12, либо между собой -- в последнем случае угловая клетка "срезается". Таких "срезанных" угловых клеток не более двух, так как угловой узел становится свободным. Остаётся 14 граничных узлов, не вовлечённых в этот процесс. Ввиду того, что каждый из них может быть соединён только с одним из 12, получается ещё два свободных узла.

ссылка

отвечен 13 Апр '15 12:33

1

Здесь приведена картинка и два других доказательства невозможности проведения $%17$% диагоналек.

Для квадрата $%7\times7$% провести более $%4\cdot7=28$% диагоналек мне не удалось, хотя пример с квадратом $%5\times5$% позволяет в квадрате $%9\times9$% провести $%5\cdot9+1=46$% диагоналек.

(13 Апр '15 15:46) EdwardTurJ
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×28

задан
9 Апр '15 16:53

показан
463 раза

обновлен
13 Апр '15 15:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru