Дополнительное образование
Может ли ладья обойти все клетки доски 8х8, сделав 64 хода на соседнюю клетку, и вернуться в исходную клетку так, чтобы
...количество ходов по горизонтали и вертикали было одинаковым (то есть по 32)?
Татьяна Завгородняя
96 935
Не может. В ответ не влезает даже план доказательства, план раскидаю по ответу и комментариям. Любой пункт из плана при желании распишу подробнее.... Если хватит сил))
Доску 8x8 можно последовательно составить из пронумерованных блоков 2x2 так, чтоб каждый блок (кроме первого) имел с объединением предыдущих либо ровно одну, либо ровно две (причем, соседние по углу) общие стороны.
Получим конечную последовательность фигур
S1 = первый блок, S2 = объединение первого блока + второго, ..S16 = вся доска 8x8
Пусть M - какая-то из фигур S1, ..S16
Будем рассматривать покрытие M семейством замкнутых путей, для которого:
- пути не выходят за пределы M;
- через каждую клетку M проходит ровно один путь;
- пути не имеет самопересечений (т. е. для каждого пути кол-во шагов в нем равно количеству клеток, через которые он проходит).
Пусть n = кол-во путей в покрытии, d - дефект (кол-во горизонтальных шагов минус кол-во вертикальных по всем путям покрытия).
Наша цель - показать, что величина f(M) = 4n + d mod 8 не зависит от выбранного покрытия фигуры M при условии,
что пути длиной 2 (т. е. короткие пути "туда-обратно") не пересекают границы 2x2 блоков.
Причем, для фигур S1, S2, ..величины f(S_i)) чередуются - то четверка, то нолик.
Тогда задача решится автоматически - доску 8x8 можно покрыть 16-ю квадратными путями 2x2 с дефектоом ноль каждый, значит,
одним путем с дефектом ноль ее покрыть нельзя.
(продолжение в комментариях).
Доску 8x8 можно последовательно составить из пронумерованных блоков 2x2 так, чтоб каждый блок (кроме первого) имел с объединением предыдущих либо ровно одну, либо ровно две (причем, соседние по углу) общие стороны.
Получим конечную последовательность фигур
S1 = первый блок, S2 = объединение первого блока + второго, ..S16 = вся доска 8x8
Пусть M - какая-то из фигур S1, ..S16
Будем рассматривать покрытие M семейством замкнутых путей, для которого:
- пути не выходят за пределы M;
- через каждую клетку M проходит ровно один путь;
- пути не имеет самопересечений (т. е. для каждого пути кол-во шагов в нем равно количеству клеток, через которые он проходит).
Пусть n = кол-во путей в покрытии, d - дефект (кол-во горизонтальных шагов минус кол-во вертикальных по всем путям покрытия).
Наша цель - показать, что величина f(M) = 4n + d mod 8 не зависит от выбранного покрытия фигуры M при условии,
что пути длиной 2 (т. е. короткие пути "туда-обратно") не пересекают границы 2x2 блоков.
Причем, для фигур S1, S2, ..величины f(S_i)) чередуются - то четверка, то нолик.
Тогда задача решится автоматически - доску 8x8 можно покрыть 16-ю квадратными путями 2x2 с дефектоом ноль каждый, значит,
одним путем с дефектом ноль ее покрыть нельзя.
(продолжение в комментариях).
Тадасана - дурак. Зачем отрезать блоки 2 на 2?
Отрезал бы от доски горизонтальными доминошками, слева направо, сверху вниз, как при чтении.
У него есть замкнутый путь длины 2, способный покрыть доминошку. И при отрезании доминошки такой путь может появиться только на ней и непосредственно под ней.
Отрезал бы от доски горизонтальными доминошками, слева направо, сверху вниз, как при чтении.
У него есть замкнутый путь длины 2, способный покрыть доминошку. И при отрезании доминошки такой путь может появиться только на ней и непосредственно под ней.
By Cherry
739
Татьяна Завгородняя
Еще один тролль... Может, лучше решение напишете? Я совершенно вас не понял. Какой может быть замкнутый путь длины 2?
Оля Черебедова
Я Shkozo почти не пользуюсь сейчас. Там подписчиков многовато, еще и кто-то из почитателей ему баллы накрутил. Но иногда захожу под ним.
именно за 64 хода и сможет. Не меньше
Татьяна Завгородняя
Да что вы говорите!..
Похожие вопросы
- Какое наименьшее число клеток нужно закрасить в квадрате 7 на 7 чтобы каждая или была закрашенной или граничила с закра
- В синтезе АТФ не участвует такая структура клетки, как.
- Дайте полное название каждому из перечисленных : ДНК,РНК, и-РНК, т-РНК, р-РНК и назовите функции этих веществ в клетке
- как клетки защищаются от действия ферментов-протеаз?
- химический состав клетки.
- Роль воды и неорганических веществ в жизнедеятельности в клетке.
- киньте фотку клетки инфузории туфельки
- какова единица измерения клетки у высших растений?
- перечислите функции неорганических веществ, входящих в состав клетки
- На доске написано более 40, но менее 48 целых чисел. Среднее арифметическое этих чисел равно -3, среднее арифметическое
Предположим, что мы покрыли фигурку S_(n+1) покрытием из n ориентированных путей.
Будем откусывать от фигуры S_(n+1) последний 2x2 блок B и редактировать покрытие фигуры S_(n+1) путями так, чтобы пути покрывали S(n+1) и не пересекали общую границу S(n) и B.
Случаи могут быть такие, в порядке возрастания интереса:
0) редактирование не требуется
1) В блоке B есть один вход и один выход, причем, они находятся с одной стороны (тут понятно, как редактируем);
2) В блоке B c каждой из двух сторон есть пара вход + выход;
Кол-во путей aka компонент связности (точнее, его четность) удобно подсчитывать через повороты влево-вправо.
4) В блоке B с одной стороны один вход, а с другой - один выход (клетки входа/выхода в блоке 2x2 являются соседними, иное невозомжно)
Это самый неудобный случай.
Тут придется рассматривать замкнутые пути длиной 2. Для корректного подсчета четности кол-ва путей через повороты
разумно полагать, что в замкнутом пути длиной два есть два двойных поворота в общую сторону (например, оба по часовой стрелке).
По случаю 4) нарисовал маленькую картинку, чтоб объяснить, как устроено редактирование.
Блок 2x2 в левом верхнем углу. Вход и выход обозначены стрелками.
Тут возможны 2 подслучая:
- красная палка является частью некоторого пути
- отрезки B5: B6 и C5:C6 являются частями пути/путей. Второй подслучай простой, нарисую, как редактируем пути в первом.
Чернопольную часть красной палки поворачиваем (вокруг центра клетки) в строну входа A6, белопольную часть - в сторону выхода C7.
Вот здесь и возможно возникновение пути длиной 2: если в нерадктированном пути мы по красной палке ко входу подходим, то при редактирования появится путь, состоящий из двух клеток A6-B6