Доска nxn разделена по клеткам на квадраты 2х2 и 5х5 клеток. При каких n это возможно?

задан 27 Мар '14 23:17

изменен 28 Июл '15 0:35

EdwardTurJ's gravatar image


501294191

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

У меня первоначально была идея нахождения чисто геометрического решения, но её не удалось довести до конца. Поэтому вот решение с использованием идей из теории групп. Я его "адаптировал" таким образом, чтобы оно не использовало каких-то сложных конструкций.

Прежде всего, ясно, что при чётных $%n$%, а также при $%n$%, делящихся на $%5$%, замощение возможно. Докажем, что верно обратное, то есть при нечётном $%n$%, не кратном $%5$%, замостить доску требуемым образом нельзя.

Предположим противное и рассмотрим какое-то замощение для этого случая. Разметим все линии, соединяющие соседние узлы квадратной сетки, таким образом: нарисуем на них стрелки, идущие слева направо и снизу вверх. Каждой горизонтальной стрелке сопоставим букву $%a$%, и каждой вертикальной -- букву $%b$%. Границу каждого квадрата со стороной 2 будем интерпретировать как "равенство" вида $%a^2b^2=b^2a^2$%, а для каждого квадрата со стороной 5 это будет "равенство" $%a^5b^5=b^5a^5$%. Наша задача состоит в том, чтобы проинтерпретировать $%a$% и $%b$% в качестве каких-то "действий", где "произведением" считается результат последовательного выполнения этих действий. При этом нужно, чтобы каждое из двух указанных выше равенств выполнялось.

Для этой цели мы рассмотрим две перестановки (подстановки) на множестве из пяти элементов. Каждая из перестановок есть функция, отображающая множество $%\{1;2;3;4;5\}$% на себя. Мы полагаем $$a=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 1 & 3 & 4 & 5 \end{pmatrix}\qquad\qquad b=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 3 & 4 & 5 & 1 \end{pmatrix}$$ Смысл этих записей таков: преобразование $%a$% переводит символ 1 в символ 2, написанный под ним, и так далее.

Перестановки можно перемножать, понимая под этим последовательное выполнение преобразований (это не что иное как композиция двух функций). Выполняя сначала действие $%a$%, а потом действие $%b$%, мы получаем перестановку $$ab=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\3 & 2 & 4 & 5 & 1 \end{pmatrix}$$ Здесь 1 сначала перешло в 2 под действием $%a$%, и затем 2 последовательно перешло в 3 под действием $%b$%, поэтому считается, что под действием $%ab$% символ 1 перешёл в 3, и мы записали одно под другим. Аналогично, $$ba=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\1 & 3 & 4 & 5 & 1 \end{pmatrix}$$ Отметим, что $%ab\ne ba$% -- это нам далее понадобится.

Подстановки $%a$% и $%b$% были подобраны так, что если действие $%a$% выполнить дважды, то получится тождественное преобразование: каждый символ перейдёт сам в себя. То же касается преобразования $%b$%, выполненного пять раз подряд. Эти наблюдения можно выразить формулами $%a^2=I$% и $%b^5=I$%, где под $%I$% понимается тождественная подстановка. Она, очевидно, обладает тем же свойством, что и единица при умножении. Отсюда следует, что каждое из равенств $%a^2b^2=b^2a^2$% и $%a^5b^5=b^5a^5$% будет очевидным образом справедливо. Действительно, первое из них превращается в $%b^2=b^2$%, а второе в $%a^5=a^5$%.

Теперь, если у нас есть замощение доски $%n\times n$%, можно сравнить между собой значения двух подстановок: $%a^nb^n$% и $%b^na^n$%. Им соответствуют два пути: один идёт по границе доски вправо, а затем вверх (из левого нижнего угла в правый верхний). Второй путь идёт сначала снизу вверх, а потом слева направо. Принципиальный факт состоит в том, что обе подстановки должны быть равны, то есть $%a^nb^n=b^na^n$%. Следует этого из того, что от первого пути можно последовательно перейти ко второму, обходя все квадраты замощения с другой стороны. Этому соответствует использование одного из равенств $%a^2b^2=b^2a^2$% или $%a^5b^5=b^5a^5$%, справедливость каждого из которых уже установлена.

Таким образом, равенство $%a^nb^n=b^na^n$% будет верно. Поскольку $%n$% нечётно, $%a^n$% равно $%a$%. Далее, $%n$% не делится на $%5$%, то есть оно имеет вид $%n=5k+r$%, где $%k$% целое, а $%r\in\{1;2;3;4\}$% -- ненулевой остаток. Из этого следует, что $%b^n=b^r$%, а потому $%ab^r=b^ra$% для некоторого $%r$% из указанного списка.

Мы уже знаем, что $%ab\ne ba$%, то есть $%r$% не может принимать значение 1. Чтобы показать, что других значений $%r$% также принимать не может, проще всего заметить, что ввиду равенства $%b^5=I$%, подстановку $%b$% можно записать как степень каждой из трёх подстановок вида $%b^r$%. А именно, $%b=(b^2)^3$%; $%b=(b^3)^2$%; $%b=(b^4)^4$%. Поэтому, если выполнено равенство $%ab^r=b^ra$%, то $%a$% перестановочна с $%b^r$%, и тогда $%a$% перестановочна с любой степенью подстановки $%b^r$%. В частности, она перестановочна с $%b$%, но это противоречит условию $%ab\ne ba$%. Тем самым, замощение доски при нечётных $%n$%, не делящихся на 5, невозможно.

ссылка

отвечен 28 Мар '14 19:30

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

12х12, далее, в зависимости от того как хотите увеличивать, только n должно представлять собой сумму целого числа 5 и 2 клеток.

ссылка

отвечен 27 Мар '14 23:27

@pda: это условие не является достаточным. В частности, квадрат $%13\times13$% замостить таким способом нельзя, хотя 13 представимо в виде суммы двоек и пятёрок.

(28 Мар '14 18:35) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×14

задан
27 Мар '14 23:17

показан
1179 раз

обновлен
28 Июл '15 0:35

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

по почте:

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

по RSS:

Ответы

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

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