Сколькими способами можно замостить прямоугольника

Сколькими способами можно замостить прямоугольника

Можно ли замостить доску 2003×2003 доминошками 1×2, которые разрешается располагать только горизонтально, и прямоугольниками 1×3, которые разрешается располагать только вертикально? (Две стороны доски условно считаются горизонтальными, а две другие – вертикальными.)

Решение 1

Запишем во все клетки нечётных столбцов цифру 1, а во все клетки чётных столбцов – цифру 2. Сумма цифр в каждом прямоугольнике 1×2 или 3×1 кратна 3. Но сумма цифр на всей доске не кратна 3. Поэтому разбить её на такие прямоугольники нельзя.

Решение 2

Пусть замощение возможно. Поскольку доска содержит нечётное число клеток, в нём участвует нечётное число прямоугольников 3×1. Окрасим в чёрный цвет 1-ю, 4-ю, 7-ю, . 2002-ю горизонтали доски (через две) – всего 668 горизонталей. Количество чёрных клеток чётно. Но каждый прямоугольник 1×2 содержит чётное число чёрных клеток (0 или 2), а каждый прямоугольник 3×1 – ровно одну чёрную клетку, то есть общее число чёрных клеток нечётно. Противоречие.

Ответ

Замечания

1. Аналогично можно придти к противоречию, закрасив вертикали через одну.

2. Уменьшив все горизонтальные размеры вдвое, а вертикальные – втрое, мы придём к частному случаю задачи 58262.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	2002/2003
Номер	24
вариант
Вариант	весенний тур, тренировочный вариант, 8-9 класс
Задача
Номер	5

Проект осуществляется при поддержке и .

Источник

дискретная-математика — Сколькими способами можно замостить прямоугольник высоты 1 и длины n.

Сколькими способами можно замостить прямоугольник высоты 1 и длины n, используя плитки высоты 1 следующих видов:

a)

б)

задан 22 Янв ’19 16:17

Rocknrolla
472 ● 3 ● 19
95&#037 принятых

1 ответ

а) Обозначим через $%a_n$% искомую величину, и пусть $%b_n$% — число способов замощения прямоугольника того же размера со срезанным слева «уголком» (сверху или снизу — не важно). Выведем рекуррентные формулы.

Прежде всего, слева находится вторая или четвёртая по счёту фигура, откуда $%a_n=2b_n$%. Для выражения $%b_n$%, будем считать, что «уголок» срезан сверху. Далее можно или приставить к нему первую фигуру, получая $%a_$% способ дальнейшего замощения при $%n\ge1$%, либо пятую (параллелограмм) при $%n\ge3$%, где оставшаяся часть покрывается $%b_$% способами. Итого $%b_n=a_+b_$% при $%n\ge3$%.

Таким образом, $%a_n-a_=2(b_n-b_)=2a_$% при $%n\ge3$%. Начальные значения: $%a_0=1$%, $%a_1=2$%, $%a_2=4$%. Рекуррентное соотношение решаем при помощи характеристического уравнения $%\lambda^2-2\lambda-1=0$%. При $%n\ge1$% с учётом начальных значений это даёт $%a_n=\frac<(1+\sqrt2)^n-(1-\sqrt2)^n><\sqrt2>$%.

б) Это пункт решается аналогично, с тем отличием что там получается $%b_n=a_+b_$% при $%n\ge2$%. Это приводит к ответу $%a_n=2\cdot3^$% при $%n\ge1$%.

Источник

Количество способов замостить прямоугольник M*N прямоугольниками M*1 и 1*M

Добрый день! Подскажите пожалуйста, как решить данную задачу:

Дан прямоугольник M*N. Нужно узнать сколькими способами его можно заполнить прямоугольниками размером 1*M (или М*1).

(Пример: при M = 4, N = 6, ответ равен 4)

Ламинат или Количество способов замостить прямоугольник M*N прямоугольниками M*1 и 1*M
Ламинат Требуется замостить пол комнаты шириной N и длиной M с помощью N полос ламината размером.

Подсчитать количество способов замостить шахматную доску доминошками
На шахматной доске,размером N*N клеток(2 7

Решение

Ночная гениальная догадка. Но . как и все гениальное — оно оказалось не верным.
Формула все же немного другая.
Вот как можно рассуждать. Способов без горизонтальных полос ровно один (зато всегда есть).
Нетрудно сообразить, что число укладок, имеющих ровно i участков, замощенных горизонтальными полосками, равно
C_^.
»/>
Эта задача равносильна перечислению числа представлений числа N-iM в виде суммы i+1 неотрицательных целых чисел. Подумайте почему.
Отсюда получается следующее утверждение.
Если N=qM+r, 0

Теперь, если я и ошибся, то не сильно.

Добавлено через 13 часов 48 минут
Мне так понравилась эта моя формула, что захотелось ее усовершенствовать и переписать так (квадратные скобки означают целую часть)
\bigsum_^C_^i,\ q=\left[\frac\right].
»/>

Источник

Замощение доминошками

Одна из первых действительно интересных задач по математике, с которыми я столкнулся формулируется так: «из шахматной доски вырезали две противоположные по диагонали угловые клетки, можно ли оставшуюся часть разрезать на «доминошки» — фигурки из двух клеток, у которых одна сторона общая?». У нее очень простая формулировка, в отличие от великой теоремы Ферма она имет простое, элегантное, но неочевидное решение (если вы знаете решение задачи, то попробуйте применить его к фигуре справа).

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

Nota bene! Материал этой статьи — это усеченный вариант вот этого jupyter-notebook, все картинки и анимации, которые вы увидите в статье, сгенерированы кодом из этого ноутбука (правда анимаций не будет в github предпросмотре). К слову, картинки из заголовка также сгенерированы с помощью python/matplotlib

Сделать это невозможно, и этому есть красивое и простое объяснение:

• На оставшейся части доски 30 черных и 32 белых клетки
• Каждая доминошка состоит из одной черной и одной белой клетки
• Как бы мы не разрезали фигуру на доминошки, в итоге на доминошках будет равное число белых и черных клеток

Динамическое программирование по профилю

Про динамического программирования есть статья на хабре, которая даже содержит пример с покрытием доминошками, я немного расширю этот пример.

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

Аналогично можно вычислить число «сочетаний» , воспользовавшись одним из следующих рекуррентных соотношений

Для задачи «можно ли замостить доминошками прямоугольник ?» к сожалению подобных простых соотношений не существует. Тем не менее, если мы рассмотрим более широкий класс фигурок, то такие соотношения уже станут возможными, главное чтобы это не были слишком маленькие классы и динамическое программирование не превратилось в банальный перебор.

Посмотрим на следующий класс фигурок: у нас есть прямоугольник , на строке присутствуют первые клеток, остальные задаются профилем, на строке первые клеток задаются профилем, остальные не участвуют. Профиль — это последовательность нулей и единичек длины : если на -ой позиции профиля единичка, это значит что в этой фигуре есть соответствующая клетка, всего профилей (красные клетки — единички, синие — нули).

Профиль однозначно задается числом (его бинарное представление вплоть до разрядов является последовательностей нулей и единичек).

Прямоугольник соответствует фигуре с , и нулевым профилем. На фигурках такого типа мы можем считать две основные функции

• Максимальное возможное число покрытых доминошками клеток в этой фигуре
• Количество способов полностью покрыть доминошками эту фигуру

Давайте обозначим за количество способов замостить такую фигурку, тогда и при этом выражается через сумму нескольких , по большому счету переход от к — это перебор трех случаев: поставить вертикальную доминошку, если это возможно

горизонтальную доминошку, если это возможно

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

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

Сверяемся с википедией, пока все в порядке. Давайте еще на всякий случай проверим, количество способов замостить полоску — должно получиться число Фибоначчи.

Что ж, поехали дальше, проверим на доске с вырезанными углами

Супер. Допустим вычислять количество мы научились, может найдем хотя бы одно конкретное замощение для наглядности?

Слишком просто, давайте вырежем несколько клеток

Попробуем теперь сделать тоже самое для замощения максимальной возможной части фигуры

И попробуем фигурку из заголовка

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

Замощение с помощью решения задачи о максимальном паросочетании

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

Здесь даже получается проанимировать процесс

Суть алгоритма Куна (да и любого другого алгоритм для нахождения максимального паросочетания) заключается в нахождении «аугментирующих путей». В терминах доминошек это цепочка из доминошек, у которой рядом с доминошками на концах есть по свободной клетке, такие цепочки можно заменить на цепочки большей длины, охватывающие те же клетки и заполняя две свободные клетки рядом с концами цепочки. Более того, основное утверждение, на котором работают все алгоритмы нахождения максимального паросочетания, заключается в том, что если такой цепочки не удается найти, то значит большего замощения нам не получить.

UPD. Для последнего примера простое обоснование на основе черно-белой раскраски не работает. Насколько мне известно, есть два общих критерия для существования полного замощения:

• Теорема Холла (теорема о свадьбах)
  Проверка условий этой теоремы вычислительно сложнее, чем построить максимальное паросочетание.
• Условие высоты Тёрстона про это я мало что знаю

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

Бонус! Раскраска планарного графа в 5 цветов.

Для визуализации замощения я использовал отдельный цвет для каждой доминошки. К сожалению некоторые цвета не очень хорошо смотрятся, а некоторые плохо контрастируют друг с другом. В этом случае подобрать цвета для хорошего контраста не так уж просто, особенно если доминошек много. Зато можно использовать меньше цветов: доминошки, которые не находятся рядом друг с другом можно раскрасить в одинаковый цвет, тогда визуально все еще будет понятно, как именно выглядит покрытие. В общем то это классическая задача о раскраске вершин планарного графа. Любой планарный граф можно покрасить в 4 цвета, правда хорошего алгоритма для такой покраски нет. Зато есть довольно простой алгоритм для покраски в 5 цветов, когда правда все еще много, и я его мало тестировал (если необходим 5ый цвет, то возможны баги)

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

Ну и наконец попробуем один из примеров, который был чуть раньше

Источник