Question

Задача. Сколько вариантов пройти таблицу 8х5 клеток, чтобы ...?

войти слева вверху, а выйти слева внизу. Ходить можно только по прямой т.е. вверх, вниз, влево, вправо, наступать на каждую клетку один раз

Когда мне рассказали эту задачу, то сказали, что на тот момент в мире было найдено 5 вариантов решений, я нашел Свое Решение, а сколько вариантов найдете Вы?

Answer 1

Я думаю кто хотел ответить уже ответили. Поэтому приведу свое решение, точнее доказательство того, что решений нет и как здесь некоторые уже говорили, утверждение, что в мире найдено 5 вариантов решений это бред. Приведу одно доказательство и одно упрощение, позволяющее однозначно сделать вывод о решаемости.

Начну с упрощения. В таких задачах можно без ущерба решабельности сокращать части таблицы, которые образуют замкнутый круг, при этом не отсекают другие части и не оставляют частей шириной меньше 2. Доказательства у меня нет, но это не мешает работать такому упрощению. В результате его применения для приведенной задачи у нас остается таблица 2х3, которая имеет всего несколько вариантов движения (т.е. решение после такого упрощения достигается элементарным перебором всех вариантов) и все они неудовлетворительные.

А теперь решение, при чем очень простое. Раскрашиваем все клетки в шахматном порядке. В результате из 40 клеток таблицы получаем равное количество светлых и темных клеток, т.е. по 20 клеток. При этом, как видим из картинки, клетки входа и выхода будут иметь один цвет. А чтобы обойти все клетки надо войти с одного цвета, а выйти с другого, следовательно раз вход и выход одноцветные, то задача не имеет решений, так как мы проходим 20 пусть светлых и 19 темных, или имеет решение при условии, что одна клетка другого цвета по отношению к увету клетки входа-выходы не будет пройдена.

Answer 2

Рассмотрим ситуацию для задач такого типа в общих чертах. Если мы примем перемещение по таблице с лева на право и с верху вниз со знаком "+", а противоположное со знаком "-" , то для таблицы имеющей решение сумма всех горизонтальных перемещений будет равна нулю, а вертикальных m (число столбцов n, строк m). Отсюда очевидно что рассматривать варианты решений со сложной траекторией не имеет смысла. Если нет решения при простом проходе его не будет при любом "маршруте". Рассмотрим таблицу с четным количеством строк (рис.1)

Не требуются доказательства что решения будут иметь место для любого количества столбцов. При нечетном m могут возникнуть сложности (рис.2), которые разрешатся только при не четном n (рис.3). Отсюда простой вывод - имеет значение не размер таблицы, а сочетания четности и не четности сторон таблицы (n и m), поэтому задачу легче рассматривать на таблицах в несколько клеток.

Проведя анализ таких таблиц можно сформулировать правила для решения:

Во первых решения будут для всех таблиц где n + m является четным числом.

Во вторых если m четное решения будут для всей плоскости вариантов.

В третьих исключение составит таблица nх1 (рис.4) не имеющая решений кроме 1х1

Решаем данную задачу n + m = 13 при этом m не четное - решений быть не должно, а их и нет.

Данную задачу можно расширить, когда вход и выход находятся на противоположных сторонах таблицы по диагонали.

Если это кого то заинтересует, интересно было бы увидеть правила для этого варианта.

Answer 3

Эта задача не имеет ни одного решения, если не выходить за грани очерченного поля и выполнять условия, перечисленные вами. Тут дело заключается в четности и нечетности клеток по высоте и по ширине поля. Говорить, что задачу можно решить- это то же самое, что говорить, что нашел решение головоломки "Пятнашки".

Answer 4

Есть известная игра в пятнашки. 15 фишек на поле 4*4. Они расставлены в произвольном порядке.

Требуется сложить их строго по порядку

_1 _2 _3 _4

_5 _6 _7 _8

_9 10 11 12

13 14 15

Фокус в том, что любое начальное расположение можно перевести в два разных: одно правильное,

а во втором фишки 14 и 15 поменяны местами

13 15 14.

И из одного в другое перейти невозможно.

В конце 19 века американский мастер головоломок Сэм Лойд, который и изобрел эту игру, предложил премию 100 000 долларов тому, кто сумеет перевести положение

_1 _2 _3 _4

_5 _6 _7 _8

_9 10 11 12

13 15 14

в правильное положение

_1 _2 _3 _4

_5 _6 _7 _8

_9 10 11 12

13 14 15

Заранее зная, что это невозможно.

Точно также невозможно решить исходную задачу с путем по всем квадратикам, если длина поля четна, а ширина нечетна.

Ваши слова про 5 найденных решений - полный бред.

Answer 5

Хм...долго я сидел и пробовал разные варианты, но пока что у меня ничего не получилось. Всегда остается клетка, которую я не могу захватить. Представить себе не могу каким образом надо проводить эту линию. В прямоугольнике со сторонами 5/8, впрочем, как и в любом, где одна сторона четная, а другая нечетная, нельзя провести линию. Хотелось бы увидеть ваш вариант

**

**

Answer 6

1. Решение возможно для любого прямоугольника, имеющего нечетное количество столбцов.
2. Решение возможно для любого прямоугольника, имеющего четное количество строк.
3. Данный прямоугольник не удовлетворяет 1 или 2, значит решений нет.

Answer 7

У меня примерно такие рассуждения.

Для доказательства невозможности решения задачи раскрасим доску в шахматном порядке. При этом клетка входа и клетка выхода будут черными. Наш первый ход будет, соответственно на черной клетке. Каждый последующий ход будет менять цвет клетки, куда бы мы не пошли. Значит, второй, четвертый и каждый последующий четный ход будет на белой клетке. Всего клеток и соответственно ходов у нас 5 * 8 = 40 - четное число. Т.е. сороковой ход должен быть на белой клетке. Но клетка выхода у нас черная. Значит задача решения не имеет. Что и требовалось доказать.

Answer 8

Невозможно обойти все клетки и выйти слева в нижнем углу, при том что нужно войти слева внизу. Как минимум одну клеточку не удается захватить, как бы я не пробовала. А ваши 5 способов это только не всю таблицу пройти, что в принципе если подумать не противоречит условиям задачи.