математика — Количество способов разрезать прямоугольник
Сколько существует способов разрезать горизонтальный прямоугольник $%2 \bullet 11$% на прямоугольники $%1 \bullet 2$% (горизонтальные и вертикальные) и $%1 \bullet 3$% (горизонтальные, так как вертикальные не помещаются)?
задан 28 Ноя ’17 1:51
serg55
8.4k ● 1 ● 50 ● 234
95% принятых
@serg55: сегодня была похожая задача про замощения плитками 1×1 и 1×2. Можете посмотреть решение и применить к этому случаю, получая две рекуррентные формулы. Техника, в принципе, та же самая.
@falcao: Насколько я понял решение той задачи на которую Вы ссылаетесь , то в моём случае, т. к. второй прямоугольник $%1 \bullet 3$%, а не $%1 \bullet 1$%, то в формуле $%a_n=2a_
@serg55: формулы там слегка усложняются, но получаются они по тем же принципам. Сейчас напишу подробнее. В ответе у меня вышло 1030.
1 ответ
Вводим величины a(n) и b(n) для числа замощений 2xn, а также для 2xn с удалённой левой верхней клеткой. Вручную проверяем, что a(0)=1 (это соглашение), a(1)=1, a(2)=2, a(3)=4; b(1)=b(2)=0, b(3)=1. Для n>=4 выводим рекуррентные формулы.
Для a(n) рассматриваем такие случаи: слева вертикально лежит 2×1; слева горизонтально лежат 1×2 друг под другом; слева горизонтально лежат 1×3 друг под другом; слева горизонтально лежат 1×2 и 1×3 друг под другом в том или другом порядке. Это исчерпывает все варианты и ведёт к формуле a(n)=a(n-1)+a(n-2)+a(n-3)+2b(n-2).
Для b(n) левый нижний угол может быть занят плиткой 1×2, и тогда продолжений будет b(n-1). Или там лежит 1×3, и тогда выше неё имеются две пустых клетки. Там лежит или 1×2, что даёт a(n-3) продолжений, или 1×3, где продолжений будет b(n-3). Отсюда b(n)=b(n-1)+a(n-3)+b(n-3).
По этим формулам можно вручную рассчитать a(11)=1030. Можно также выразить b(n) из одного уравнения, подставляя в другое, получая соотношение a(n)=2a(n-1)+a(n-3)-2a(n-4)+a(n-5)-a(n-6) при n>=6, где a(4)=7, a[5]=15.
Эта последовательность также имеется в oeis. Она растёт примерно как 2,03^n.
отвечен 30 Ноя ’17 21:17
falcao
268k ● 6 ● 37 ● 51
@falcao: Извините пожалуйста, но у меня к Вам небольшой вопрос. У Вас записано, что $% a_ <5>=15$%, а если считать по формуле, то получается, что $%a_<5>= a_<4>+ a_ <3>+ a_ <2>+2\cdot b_<2>=7+4+2+2\cdot0=13$%, т.к. в начале решения у Вас записано, что $% b_<1>= b_ <2>=0$%. Наверное $% b_<2>=1$%. Или я опять что-то не понял. Заранее благодарен. С уважением.
@serg55: я здесь многократно всё проверял, но в одно место всё-таки вкралась опечатка. Насчёт b(2)=0 всё верно, а вот в рекуррентной формуле для a(n) в конце должно быть 2b(n-2). Там ведь когда лежат горизонтально 1×2 и 1×3, то пропадают две линии, а не три. Я сейчас исправлю формулу.
@falcao: Я хотел бы попытаться разобраться с этим типом задач подробнее, если это возможно. Я нашёл ещё одну подобную задачу. Её условие: Сколько существует способов разрезать горизонтальный прямоугольник 2х11 на прямоугольники 1х2 (горизонтальные и вертикальные) и 1х4 (горизонтальные, так как вертикальные не помещаются)? Я попытался решить её используя Ваш алгоритм решения предыдущей задачи, но столкнулся с вопросом, ведь когда мы рассматриваем случай: слева горизонтально лежат 1×2 и 1×4 друг под другом в том или другом порядке. Продолжение в следующем комментарии, здесь нет места.
@serg55: здесь надо другие вспомогательные величины вводить. Пусть a(n) — число замощений 2xn. Через b(n) надо обозначить число замощений такого прямоугольника (n>=2), из которого слева сверху удалена одна горизонтальная доминошка. И тут уже рекуррентные равенства выписывются. В более сложных случаях может быть более двух вспомогательных последовательностей. Они привлекаются по необходимости.
@falcao: Продолжение предыдущего комментария. Но под плиткой 1х4 может находиться целиком плитка 1х2 и тогда мне кажется количество продолжений будет другое, а не 2b(n-2). Теперь насколько я понял относительно b(n). Для b(n) когда левый нижний угол может быть занят плиткой 1×2, и тогда продолжений будет b(n-1). Или там лежит 1×4, и тогда выше неё имеются 3 пустые клетки. Там лежит или 1×2, что даёт a(n-3) продолжений, или 1×4, где продолжений будет b(n-4). Или я опять ничего не понял? Тогда извините за бестолковость. Заранее благодарен. С уважением.
@serg55: здесь вместо предыдущего b(n), когда изымали одну клетку в углу, надо брать другую величину вместо неё. Я описал, какую именно — без доминошки слева сверху. Тогда всё легко выписывается. А один угол удалять незачем, так как останется нечётная площадь.
@falcao: К сожалению я почти ничего не понял в этих замещениях и в подсчёте количества продолжений. Наверное, это для меня очень сложно и непонятно. Огромное спасибо за попытки объяснить, что-то я туплю. С уважением.
@serg55: да там нет ничего сложного. Попробуйте рассмотреть случай для 2xn с замощением 1×2 и 1×4, и двумя величинами: a(n) как общее число, и b(n) как число замощений этого же прямоугольника с двумя удалёнными клетками. Там вариантов не так много.
@falcao: У меня получилось следующее: Для a(n) рассматриваем такие случаи: слева вертикально лежит 2×1 и тогда имеется а(n-1) продолжений; слева горизонтально лежат 1×2 друг под другом, тогда — а(n-2) продолжения; слева горизонтально лежат 1×4 друг под другом, тогда а(n-4) продолжения; слева горизонтально лежат 1×2 и 1×4 друг под другом в том или другом порядке, это даст 2b(n-2) продолжения. Это исчерпывает все варианты и ведёт к формуле a(n)=a(n-1)+a(n-2)+a(n-4)+2b(n-2). Это хоть верно? Или опять туплю? Заранее благодарен. С уважением. Для b(n)рассуждения приведены в следующем комментарии.
@falcao: Продолжение предыдущего комментария. Для b(n) левый нижний угол может быть занят плиткой 1×2, и тогда продолжений будет b(n-1). Или там лежит 1×4, и тогда выше неё имеются две пустых клетки. Там лежит или 1×2, что даёт a(n-4) продолжений, или 1×4, где продолжений будет b(n-4). Отсюда b(n)=b(n-1)+a(n-4)+b(n-4). Но тогда при подсчёте получается надо знать b(0). Похоже я всё равно до конца не понял, к сожалению, но очень хочется разобраться и понять.
@serg55: для a(n) рекуррентная формула правильная.
Для b(n), если в углу лежит 1×2, то получается прямоугольник. Способов его покрыть будет a(n-2). Если угол занимает 1×4, то остаётся 2x(n-2) с двумя изъятыми клетками. Отсюда b(n)=a(n-2)+b(n-2) при n>=4.
Начальные значения b(n) при n=0,1 не определены; b(2)=1, b(3)=1.
@falcao: Наконец-то я посчитал. У меня получилось следующее: Формулы по которым считал: a(n)=a(n-1)+a(n-2)+a(n-4)+2b(n-2); b(n)=a(n-2)+b(n-2). Начальные условия: а(0)=а(1)=1; а(2)=2; а(3)=4; b(2)=1, b(3)=1. Таким образом получается а(11)= 870. Всё правильно я понял из Вашего объяснения? Или опять где-то ошибся? Заранее благодарен. С уважением.
@serg55: там на самом деле должно быть 868, то есть где-то Вы немного обсчитались. Помимо этого, a(3)=3 в начальных условиях.
Источник
Разрезания
статья по алгебре по теме
Разрезания
Исходная задача. Сколькими способами можно вырезать из квадрата 9´9 квадрат 3´3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2´3? (Способы вырезания, получаемые друг из друга симметрией или поворотом, будем считать различными.)
Общая постановка задачи.
1. Для каких натуральных чисел п из квадрата п´п можно вырезать квадрат 3´3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2´3?
2. Для каких натуральных чисел т и п из прямоугольника т´п можно вырезать квадрат 3´3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2´3?
3. Рассмотрите обобщения этой задачи в следующих двух направлениях:
а) Для каких натуральных чисел т и п из прямоугольника т´п можно вырезать квадрат р´р (р – заданное натуральное число) так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2´3?
б) Для каких натуральных чисел т и п из прямоугольника т´п можно вырезать квадрат 3´3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники s´t, где s и t – заданные натуральные числа? (Рассмотрите хотя бы некоторые случаи значений s и t.)
4. Аналогично исходной задаче во всех пунктах 1 – 3 попробуйте указать или хотя бы оценить количество способов соответствующих вырезаний.
5. Предложите свои обобщения этой задачи и исследуйте их.
Скачать:
| Вложение | Размер |
|---|---|
| m-4.doc | 95 КБ |
Предварительный просмотр:
Исходная задача . Сколькими способами можно вырезать из квадрата 9 × 9 квадрат 3 × 3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2 × 3? (Способы вырезания, получаемые друг из друга симметрией или поворотом, будем считать различными.)
Общая постановка задачи .
1. Для каких натуральных чисел п из квадрата п × п можно вырезать квадрат 3 × 3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2 × 3?
2. Для каких натуральных чисел т и п из прямоугольника т × п можно вырезать квадрат 3 × 3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2 × 3?
3. Рассмотрите обобщения этой задачи в следующих двух направлениях:
а) Для каких натуральных чисел т и п из прямоугольника т × п можно вырезать квадрат р × р ( р – заданное натуральное число) так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2 × 3?
б) Для каких натуральных чисел т и п из прямоугольника т × п можно вырезать квадрат 3 × 3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники s × t , где s и t – заданные натуральные числа? (Рассмотрите хотя бы некоторые случаи значений s и t. )
4. Аналогично исходной задаче во всех пунктах 1 – 3 попробуйте указать или хотя бы оценить количество способов соответствующих вырезаний.
5. Предложите свои обобщения этой задачи и исследуйте их.
Исходная задача. Рассмотрим все возможные клетки квадрата 9 × 9, в которых может находиться левая верхняя (угловая) клетка вырезанного квадрата 3 × 3. Очевидно, что эта угловая клетка не может находиться в восьмом или девятом столбце, а также в восьмой или девятой строке, так как тогда вырезанный квадрат 3 × 3 выйдет за пределы большого квадрата. Значит позиций для этой клетки не более чем 7 × 7=49 клеток большого квадрата. Но не все они подходят. Для того, чтобы более точно оценить количество решений, раскрасим клетки фигуры в черный и белый цвета в шахматном порядке как показано на рисунке. Также на рисунке серым отмечены клетки восьмого и девятого столбца, восьмой и девятой строки, где точно не может находиться левый верхний угол квадрата 3 × 3.
Легко заметить, что черных клеток 41, белых 40, то есть их разное количество. А любой прямоугольник 2 × 3 занимает ровно 3 белых и 3 черных клетки. Значит, в вырезанном квадрате 3 × 3 количество черных клеток должно быть на одну больше, чем белых, чтобы в оставшейся части белых и черных клеток было поровну и её можно было разделить на прямоугольники 2 × 3. Таким образом, из 49 возможных клеток остается 25 черных. Но и они не все подходят.
Очевидно, что если квадрат 3 × 3 при вырезании оставляет полосу шириной в одну клетку, то разрезать её на прямоугольники 2 × 3 невозможно. Значит, таких полос быть не должно и из 25 черных клеток выпадают еще 8, помеченных на рисунке крестиком. Они расположены по периметру квадрата 7 × 7, получаемого удалением из исходного восьмого и девятого столбца, восьмой и девятой строки, и на расстоянии 1 клетки от его стороны.
Окончательно получаем 25 – 8 = 17 способов вырезать из квадрата 9 × 9 квадрат 3 × 3. В каждом из этих случаев нетрудно убедиться, что оставшуюся часть можно разрезать на прямоугольники 2 × 3. Для этого из тех трех строк, в котором вырезали квадрат 3 × 3, вырежем три прямоугольника, расположенных вертикально. Остальные строки разбиваются на пары строк, состоящих из трех горизонтально расположенных прямоугольников. Итак, ответом является 17 способов.
- Площадь нужного квадрата равна п 2 . Чтобы фигуру, полученную после вырезания квадрата 3 × 3, можно было замостить прямоугольниками 2 × 3, её площадь должна делиться на 6, т.е. п 2 – 9 кратно 6. Чтобы число делилось на 6, оно должно делиться на 2 и на 3 одновременно. Следовательно, п 2 должен делиться на 3 и быть нечетным. Значит, п кратное 3 нечетное число. Это числа вида n = 6 d – 3, где d любое натуральное число. Они образуют арифметическую прогрессию с разностью 6.
Заметим, что для указанного выше n , если квадрат 3 × 3 вырезать из квадрата п × п так, что их левые верхние углы совпадают, то оставшуюся часть нетрудно разрезать на прямоугольники 2 × 3. Первые три строки содержат теперь по 6 d – 6 клеток, то есть могут быть разрезаны на 3 d – 3 вертикальных прямоугольника. Оставшиеся 6 d – 6 строк разобьем на пары рядом расположенных строк по 6 d – 3 клеток. А каждую такую пару строк, очевидно, можно разрезать на 2 d – 1 горизонтально расположенных прямоугольников.
Таким образом, для п = 6 d – 3 из квадрата п × п можно вырезать квадрат 3 × 3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2 × 3.
- Аналогично с пунктом 1, m × n нечетное число, которое делится на 3. То есть, m и n нечетные числа и хотя бы одно из них делится на 3. Заметим также, что эти числа должны быть не меньше 3. Получаем формулы: m = 2 x + 1, n = 6 y – 3 или n = 2 x + 1, m = 6 y – 3. Здесь x и y произвольные натуральные числа.
Как и в пункте 1 будем вырезать квадрат 3 × 3 так, чтобы его верхний левый угол совпал с верхним левым углом всего прямоугольника. Пусть для начала у прямоугольника m = 2 x + 1 строк и n = 6 y – 3 столбцов. Тогда, как и выше, первые три строки содержат теперь по 6 y – 6 клеток, то есть могут быть разрезаны на 3 y – 3 вертикальных прямоугольника. Оставшиеся 2 x – 2 строки можно разбить на пары рядом расположенных строк по 6 x – 3 клеток. А каждую такую пару строк, очевидно, можно разрезать на 2 x – 1 горизонтально расположенных прямоугольников. Случай m = 6 y – 3 строк и n = 2 x + 1 столбцов рассматривается аналогично. Только первые три столбца разрезаются на 3 y – 3 горизонтальных прямоугольника, а оставшиеся x – 1 пара рядом расположенных столбцов разрезается каждая на 2 x – 1 вертикальных прямоугольников.
Таким образом, если m = 2 x + 1, n = 6 y – 3 или n = 2 x + 1, m = 6 y – 3, где x и y произвольные натуральные числа, то из прямоугольника т × п можно вырезать квадрат 3 × 3 так, чтобы оставшуюся часть можно было разрезать на прямоугольники 2 × 3.
- а) Рассуждая аналогично пунктам 1 и 2, получаем, что m × n – p 2 кратно 6. При этом m и n не меньше p и не могут, очевидно, равняться p + 1. Рассмотрим, какие остатки может давать число p при делении на 6.
Пусть p делится на 6. Тогда среди чисел m и n по крайней мере одно четное и по крайней мере одно делится на 3. Возможны следующие варианты: 1) m = p + 6 x – 6, n = p + y – 1; 2) m = p + 2 x – 2, n = p + 3 y – 3; 3) m = p + 3 x – 3, n = p + 2 y – 2; 4) m = p + x – 1, n = p + 6 y – 6. Здесь x и y произвольные натуральные числа.
Пусть p дает 1 в остатке при делении на 6. Тогда p 2 – 1 кратно 6, числа m и n нечетны и их произведение при делении на 3 дает в остатке 1. То есть, при делении на 3 оба дают в остатке 1 или оба дают в остатке 2. Возможны следующие варианты: 1) m = p + 6 x – 6, n = p + 6 y – 6; 2) m = p + 6 x – 2, n = p + 6 y – 2. Здесь x и y произвольные натуральные числа.
Пусть p дает 5 в остатке при делении на 6. Тогда p 2 – 1 кратно 6, числа m и n нечетны и их произведение при делении на 3 дает в остатке 1. То есть, при делении на 3 оба дают в остатке 1 или оба дают в остатке 2. Возможны следующие варианты: 1) m = p + 6 x – 6, n = p + 6 y – 6; 2) m = p + 6 x – 4, n = p + 6 y – 4. Здесь x и y произвольные натуральные числа.
Пусть p дает 2 в остатке при делении на 6. Тогда p 2 – 4 кратно 6, среди чисел m и n хотя бы одно четное и их произведение при делении на 3 дает в остатке 1. То есть, при делении на 3 оба дают в остатке 1 или оба дают в остатке 2. Возможны следующие варианты: 1) m = p + 6 x – 6, n = p + 3 y – 3; 2) m = p + 3 x – 3, n = p + 6 y – 6; 3) m = p + 3 x – 1, n = p + 6 y – 4; 4) m = p + 6 x – 4, n = p + 3 y – 1. Здесь x и y произвольные натуральные числа.
Пусть p дает 4 в остатке при делении на 6. Тогда p 2 – 4 кратно 6, среди чисел m и n хотя бы одно четное и их произведение при делении на 3 дает в остатке 1. То есть, при делении на 3 оба дают в остатке 1 или оба дают в остатке 2. Возможны следующие варианты: 1) m = p + 6 x – 6, n = p + 3 y – 3; 2) m = p + 3 x – 3, n = p + 6 y – 6; 3) m = p + 3 x + 1, n = p + 6 y – 2; 4) m = p + 6 x – 2, n = p + 3 y + 1. Здесь x и y произвольные натуральные числа.
Пусть p дает 3 в остатке при делении на 6. Тогда p 2 – 3 кратно 6, числа m и n нечетны и их произведение кратно 3. То есть, по крайней мере одно из этих чисел делится на 3. Возможны следующие варианты: 1) m = p + 6 x – 6, n = p + 2 y – 2; 2) m = p + 2 x – 2, n = p + 6 y – 6. Здесь x и y произвольные натуральные числа.
Заметим, что в каждом из этих случаев можно по аналогии с пунктами 1 и 2 показать, что оставшуюся часть можно было разрезать на прямоугольники 2 × 3.
- б) По аналогии с рассуждениями выше, для того, чтобы из прямоугольника т × п можно было вырезать квадрат 3 × 3 так, чтобы оставшуюся часть можно разрезать на прямоугольники s × t , где s и t – заданные натуральные числа, необходимо, чтобы число т × п – 9 делилось на число s × t . Рассмотрим небольшие значения s и t и ответим для них на вопрос задачи.
1) s = t = 1. Очевидно, m и n любые натуральные числа, не меньшие 3.
2) s = 1, t = 2 или s = 2, t = 1. В этом случае число т × п – 9 является четным, то есть числа m и n любые нечетные натуральные числа, не меньшие 3. Идея разрезания оставшейся части очень проста: вырежем квадрат 3 × 3 из левого верхнего угла прямоугольника, первые три строки содержат теперь четное число клеток (по 3 клетки из них вырезали), значит их можно разрезать на горизонтально расположенные прямоугольники 1 × 2, оставшиеся строки разбиваем на пары рядом расположенных строк и разрезаем каждую пару на нечетное число вертикально расположенных прямоугольников 1 × 2. Запишем ответ в виде m = 2 x +1, n = 2 y + 1, где x и y произвольные натуральные числа.
3) s = 1, t = 3 или s = 3, t = 1. В этом случае число т × п – 9 делится на 3, то есть по крайней мере одно из чисел m или n делится на 3. Чтобы разрезать оставшуюся часть, разрежем сначала весь прямоугольник на прямоугольники 1 × 3, расположенные параллельно той стороне, длина которой делится на 3. Выбрав 3 таких прямоугольника, расположенных рядом и образующих квадрат, в качестве вырезанного прямоугольника, получим разрезание оставшейся части. Таким образом, m = 3 x , n = 3 + y или m = 3 + x , n = 3 y , где x и y произвольные натуральные числа.
4) s = 2, t = 3 или s = 3, t = 2. Этот случай рассмотрен в пункте 2.
5) s = 1, t = 4 или s = 4, t = 1. В этом случае число т × п – 9 делится на 4, то есть т × п – 9 = 4 t для некоторого целого неотрицательного t . Тогда т × п = 4( t + 2) + 1 и произведение чисел m и n при делении на 4 дает в остатке 1. То есть, при делении на 4 оба дают в остатке 1 или оба дают в остатке 3. Следовательно, m = 4 x + 1, n = 4 y + 1 или n = 4 x + 3, m = 4 y + 3, где x и y произвольные натуральные числа. Чтобы разрезать оставшуюся часть в первом случае, выделим в левом верхнем углу прямоугольника квадрат размера 5 × 5. Остальная часть легко разрезается на прямоугольники 1 × 4, так как оставшиеся части сторон кратны 4. Вырежем в центре квадрата 5 × 5 квадрат 3 × 3. Полученная рамочка разрезается на 4 прямоугольника. Во втором случае все еще проще, квадрат 3 × 3 вырезаем в верхнем левом углу, а затем оставшуюся часть то, что справа разрезаем на горизонтальные прямоугольники, а снизу на вертикальные. Оставшийся прямоугольник имеет стороны, кратные 4. Таким образом, m = 4 x + 1, n = 4 y + 1 или m = 4 x + 3, n = 4 y + 3, где x и y произвольные натуральные числа.
- Будем решать исходную задачу для условия, соответствующего пункту 3 а). При этом будем сразу считать, что оставшуюся часть прямоугольника т × п после вырезания квадрата р × р можно хотя бы в каком-то случае разрезать на прямоугольники 2 × 3. Как и в исходной задаче, разместить левую верхнюю клетку квадрата p × p можно в ( m – p + 1)( n – p + 1) клетке. Далее рассмотрим два случая:
Пусть p нечетное число, тогда используя шахматную раскраску, как и исходной задаче, уменьшим число вероятных решений до . Также необходимо выбросить из рассмотрения клетки, находящиеся на расстоянии одной клетки от границы (по аналогии с исходной задачей). Этих клеток всего внутри урезанного прямоугольника и только черных:
. Таким образом, получаем ответ
Отметим, что в исходной задаче было получено .
Пусть p четное число, тогда, как и выше, необходимо выбросить из рассмотрения клетки, находящиеся на расстоянии одной клетки от границы. Их ( m – p – 1) ⋅ 2+( n – p – 1) ⋅ 2 – 4, то есть 2 ⋅ ( m + n – 2 p – 4). В итоге в ответ пойдет
Заметим, что для пункта 1 получаем m = n и p = 3. Тогда количество способов .
Для пункта 2 получаем .
Замечание. В пункте 4 была получена оценка сверху количества способов вырезания квадрата. Хотя и не доказано строго, можно предполагать, что это и нижняя оценка. Надо только указать способ разрезания оставшейся части на прямоугольники 2 × 3.
Источник
