Дана бесконечная вправо полоска-решетка (бесконечно много квадратов канкатенированы до бесконечности вправо). Дано множество квадратов с окрашенными сторонами и в нем есть выделенный квадрат. Рассмотрим задачу разрешимости: замостить полоску, начиная с выделенного квадрата. Надо доказать, что эта задача разрешима.

То есть для каждого множества квадратов с окрашенными сторонами и с выделенным квадратом, надо придумать алгоритм, который скажет, можно ли замостить полоску этими квадратами, начиная с выделенного, или нет (за конечное число шагов).

Я вижу только бесконечный алгоритм:

Рассмотрим выделенный квадрат. Если среди данного множества нет квадратов, левая сторона которого окрашена в тот же цвет, что и правая сторона выделенного квадрата, то замостить полоску нельзя. Если описанный квадрат есть, то смотрим на цвет его правой стороны и смотрим, есть ли в нашем множестве квадрат, левая сторона которого окрашена в тот же цвет, и т.д.

задан 30 Авг '19 4:21

Ой, я забыл, что множество, которым замощается полоска, предполагается конечным. Тогда мой алгоритм конечный? Это единственный возможный алгоритм?

(30 Авг '19 4:39) logic
10|600 символов нужно символов осталось
2

Классический алгоритм должен удовлетворять трём условиям: массовость, детерминированность, результативность. Первое означает, что на вход алгоритма можно подать любую систему клеток (обязательно конечную -- это существенно), а последнее означает, что ответ должен быть получен за конечное время. Поэтому в постановке задачи должен быть другой порядок слов. Не "для любой системы ... существует алгоритм ..." (так как при этом пропадает условие массовости -- для каждой отдельной системы ответ либо "можно", либо "нельзя", а такой "алгоритм", печатающий одно из этих слов имеется всегда), а наоборот -- существует алгоритм, который по любой конечной системе, поданной на его вход, выдаёт за конечное время верный ответ на вопрос о возможности замощении бесконечной полоски.

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

Пусть N -- число цветов, используемых в системе квадратов. Докажем простую лемму: если можно правильно замостить полоску 1xN, то можно правильно замостить и бесконечную. Обратное утверждение очевидно. Такого факта достаточно, так как мы проверяем возможность замощения 1xN, и на основании этого делаем итоговый вывод.

Итак, пусть полоска 1xN правильно замощена. Рассмотрим её вертикальные рёбра. Их N+1, поэтому по принципу Дирихле, среди них найдутся две, окрашенные в один цвет. Тогда расположенный между ними прямоугольник можно приставлять далее справа друг за другом, что даёт один из способов правильного замещения бесконечной полоски.

Таким образом, при полном переборе случаев достаточно отследить первый момент, когда при замощении полосок конечной длины у нас повторятся цвета вертикальных рёбер. Если этого не произойдёт, то мы обнаружим полоску конечной длины, которую не замостить.

ссылка

отвечен 30 Авг '19 18:55

А мое "решение", получается, не является решением задачи (в исправленной Вами формулировке), а дает ответ для каждого конкретного набора квадратов?

Я тут не вижу четкой грани между моим "решением" и Вашим решением. Если мой алгоритм неверен, почему он не обладает условием массовости? Он ведь "принимает" каждый конечный набор и производит с ним некоторые действия, тестирующие, возможно ли замощение.

(30 Авг '19 21:39) logic

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

Тестирование должно заканчиваться ответом "да" или "нет" за конечное время. Если мы всё время имеем успех, и можем продолжить полоску, то процесс длится бесконечно долго, и не даёт ответа "да". То есть это по определению уже не алгоритм.

(30 Авг '19 21:55) falcao

Т.е. алгоритм работает так? Он принимает конечное множество квадратов. Находит количество цветов. За конечное число шагов сначала проверяет, можно ли замостить полоску размера 1x(кол-во цветов). Если нельзя, то он выдает финальный ответ нет. Если можно, то он выдает финальный ответ да.

(31 Авг '19 21:39) logic

@logic: да, конечно. Я именно это и описал. Тут важна только лемма, что если можно покрыть 1xN, то можно и 1xinfty, и это легко вытекает из принципа Дирихле.

(31 Авг '19 22:52) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,462

задан
30 Авг '19 4:21

показан
210 раз

обновлен
31 Авг '19 22:52

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

по почте:

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

по RSS:

Ответы

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

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