Задачі на упакування

 Задачі  для  юних математиків.

Задача 1. (7-8 клас). 1)Скільки способів укладки ящиків у фургон, що має форму прямокутного паралелепіпеда розміром 4х4х2,  якщо ящики двох видів: 1х1х1 та  2х2х2?  Звертаємо увагу на те, що у кожному способі укладки сума об’ємів усіх ящиків двох видів  рівна об’єму фургона.

(5-6 класи). 2)Скільки способів є укладки дитячої площадки прямокутної форми, розміром 4х4,  за допомогою квадратних плиток двох видів: 1х1   та 2х2? Звертаємо увагу на те, що у кожному способі укладки сума площ усіх плиток двох видів  рівна площі дитячої площадки.

Розв’язання: Для задач 1 та 2 запропонуємо одну схему  розв’язування.

Достатньо зафіксувати в основу прямокутного паралелепіпеда, тобто прямокутник 4х4, і  одну його вершину, щоб  перерахувати всі способи такої укладки. Наводимо усі способи укладки ящиків(плиток)  за допомогою малюнків.

1					2					3					4					5
6					7					8					9					10
11					12					13					14					15
16					17					18					19					20
21					22					23					24					25

26					27				28					29				30
31					32				33					34				35

Відповідь: 35 способів.

Задача 2.( 7-9 клас) У середині білого паперу у клітинку, розміром   8х8, суцільно замалювали  декілька сусідніх клітинок у помаранчевий колір так, що утворилася одна замкнена клітинкова область, яка не містить замальовані клітинки на краях паперу. (Будь-які дві клітинки назвемо сусідні, якщо вони мають одну спільну сторону.) Потім перефарбували усі білі межові з помаранчевими клітинки у зелений колір. (Будь-які дві клітинки назвемо межові, якщо вони мають хоча б одну спільну точку). Яка найменша непарна кількість найкоротших ламаних, може бути проведена на такому папері,  якщо будь-яка ламана має один кінець у середині однієї помаранчевої клітинки, а другий кінець ламаної  -  у  середині  зеленої клітинки, при цьому  кожна зелена клітинка містить лише один  кінець  ламаної.

Розв’язання:

1. Якщо помаранчева клітинка є межовою до восьми зелених клітинок, то найменша кількість найкоротших  ламаних рівна кількості межових кліток, отже, у цьому випадку m=8 ламаних.

2. Якщо дві помаранчеві клітинки є межовими до десяти зелених клітинок, то найменша кількість найкоротших ламаних рівна кількості межових кліток, отже, у цьому випадку m=10 ламаних.

3. Якщо три помаранчеві клітинки є межовими до дванадцяти зелених клітинок, то маємо два способи виділення помаранчевої області. А найменша кількість найкоротших ламаних в обох випадках рівна кількості межових кліток, отже, у цьому випадку m=12 ламаних.

4. Якщо чотири помаранчеві клітинки, то для випадків, межовими є  чотирнадцять зелених клітинок, то найменша кількість найкоротших ламаних рівна кількості межових кліток. Отже, у цьому випадку m=14 ламаних. У випадку, коли помаранчева область є квадратом 2х2(див. Мал. 8), то найменша кількість найкоротших ламаних рівна 12.

 Мал.1

5. Якщо п’ять помаранчевих клітинок, то у випадку, що зображено на малюнку 1 маємо

15 межових клітинок зеленого кольору. Ці 15 клітинок визначають 15 кінців  найкоротших ламаних, що відповідають умові задачі.

Зрозуміло, що при збільшенні кількості клітинок, які суцільно фарбуються в помаранчевий колір, отримаємо більшу, ніж 15 межових клітинок. Зазначимо, що у випадку, коли зафарбовано К помаранчевих клітинок, а межових клітинок зеленого кольору N, то найменша  кількість найкоротших ламаних рівна сумі усіх межових зелених клітинок  і усіх помаранчевих клітинок, які сусідні тільки з помаранчевими клітинками.

Відповідь: 15 ламаних.

Задача на виведення рекурсивних формул.

Задача 3. (9-11 клас). У проектувальників блочного будинку є можливість на одному поверсі закласти у проект різні квартири. В планшеті ці квартири мають форму квадрата, розмір за масштабом проекту якого 1х1 та форму прямокутника з розміром 1х2. Скількома способами можна викласти проект першого поверху блочного будинку, якщо цей поверх  має форму прямокутника 2х5 за масштабом проекту? Блок квартири, що на планшеті позначений розміром 1х2, на заводі виготовляють так, що його можна  поставити лише довгою панеллю вздовж  довгої панелі будинку.

Розв’язання.

 Побудуємо  рекурсивні співвідношення для знаходження кількості способів викладення поверху у випадку, якщо він має форму прямокутника 2 х N, де N – довільне натуральне число.

Розглянемо праву нижню кутову клітинку. Ця клітинка може бути покрита або блоком 1´1, або 1´2. Таким чином, всі покриття поверху можна розбити на дві  підмножини – з блоком 1´1 в правому нижньому куті та з блоком 1´2. Позначимо через  шукану кількість покриттів поверху 2´n. Тоді можна записати , де  - кількість покриттів з блоком 1´1 в правому нижньому куті (тобто з вирізаною кутовою клітинкою),  - з блоком 1´2 (див. мал.10).

                       

                      Мал. 10

Розглянемо праву верхню клітинку покриття з блоком 1´1 в нижньому куті. Ця клітинка також може бути покрита або блоком 1´1, або блоком 1´2. В першому випадку отримаємо покриття 2´(n-1) без вирізаної кутової клітинки, а в другому – покриття 2´(n-1) з вирізаною кутовою клітинкою. Маємо (див. мал.11).

                       

                                       Мал. 11

Розглянемо праву верхню клітинку покриття з блоком 1´2 в нижньому куті. Ця клітинка також може бути покрита або блоком 1´1, або блоком 1´2. В першому випадку отримаємо покриття 2´(n-1) з вирізаною кутовою клітинкою, а в другому випадку – покриття 2´(n-2) без вирізаної кутової клітинки. Маємо  (див.мал.13).

                                  Мал. 13.

Таким чином, отримали систему таких  рекурентних співвідношень:

               (1)

Зрозуміло, що можна з системи (1) вилучити змінну h(n), якщо підставити третє рівняння в перше. Отримаємо нову систему рекурентних співвідношень:

                 (2)

За рекурентними співвідношеннями (2)   можна знайти  розв’язання задачі у випадку, якщо поверх має форму прямокутника 2 х N, де N – довільне натуральне число.

Але ще необхідно знайти .

Зрозуміло, що легко перевірити для  (див. мал.14).

Мал. 14. Всі покриття поверху розміром 2´2.

Створимо таблицю, в яку запишемо знайдені значення (для кожного n=1,2,...,10, обчислюємо спочатку g, потім f).

n	1	2	3	4	5	6	7	8	9	10
f(n)	1	4	9	25	64	169	441	1156	3025	7921
g(n)	1	2	6	15	40	104	273	714	1870	4895

Відповідь: 64 способи.