Смужки з доміно • Хайдар Нурлігареев • Науково-популярні завдання на "Елементи" • Математика

Смужки з доміно

завдання

Мал. 1.

а) скількома способами можна замостити смугу 2 × 10 Доміношки 2 × 1? Замощення, що виходять один з одного обертанням смуги, вважаються різними; наприклад, на малюнку 1 зображено два різних замощення смужки 2 × 3.
б) Те ж питання для смуги 3 × 30.


Підказка 1

а) Спробуйте шукати відповідь на поставлене запитання як окремий випадок більш загальної задачі: скількома способами можна замостити Доміношки смугу 2 ×n для довільного натурального числа n? Позначимо число замощення такої смуги через an – це дасть послідовність чисел. Як пов'язаний черговий елемент цієї послідовності з попередніми?

б) Чи можна скористатися тими ж міркуваннями, що і в пункті а)?


Підказка 2

б) Діяти зовсім аналогічно пункту а) не вийде: замостити Доміношки фігуру, що складається з непарного числа клітин, неможливо. Тому потрібно розглядати тільки смуги парної довжини. нехай bn – число замощення смуги 3 × 2n Доміношки. Як пов'язаний черговий елемент цієї послідовності з попередніми?


Рішення

Мал. 2.

а) Для початку зауважимо, що a1 = 1, a2 = 2 – відповідні замощення зображені на рис. 2.Далі, припустимо, що для деякого натурального n всі значення від a1 до an нам вже відомі. Як знайти an+1? Для цього розглянемо ліву верхню клітинку смуги 2 × (n + 1). У кожному замощення вона покрита деякою фігуркою доміно, вертикальної або горизонтальної (рис. 3). У першому випадку ми можемо відрізати цю Доміношки, так що залишилася фігура буде являти собою смугу 2 ×n. Останнє означає, що кількість замощення смуги 2 × (n + 1), у яких ліва верхня клітина покрита вертикальної фігуркою доміно, збігається з числом замощення смуги 2 ×n і так само an. Що ж стосується другого випадку, то в ньому з усією визначеністю ліва нижня клітина також буде покрита горизонтальної фігуркою доміно, а разом ці доміношки утворюють квадрат 2 × 2, відрізавши який, ми отримаємо смугу 2 × (n – 1). Отже, кількість замощення смуги 2 × (n + 1), у яких ліва верхня клітина покрита горизонтальної фігуркою доміно, збігається з числом замощення смуги 2 × (n – 1) і одно an−1.

Мал. 3.

Підсумовуючи отримані результати, ми отримуємо наступне рекурентне співвідношення: an+1 = an + an−1. У цьому місці читач, знайомий з числами Фібоначчі, відразу скаже відповідь.Але і не володіючи подібним знанням, послідовним обчисленням неважко знайти, що a3 = 3, a4 = 5, a5 = 8, a6 = 13, a7 = 21, a8 = 34, a9 = 55, a10 = 89.

Відзначимо, що отримане нами співвідношення справедливо також для n = 1, якщо вважати, що a0 = 1: в цьому випадку рівність an+1 = an + an−1 перетворюється в 2 = 1 + 1. Зазначене міркування буде справедливо і для пункту б), Що найближчим часом послужить нам добру службу.

б) До смузі 3 × 30 застосовно аналогічне, хоча і дещо більш хитре міркування. Для початку можна помітити, що b0 = a0 = 1, b1 = a3 = 3. Далі, припустимо, що для деякого натурального n всі значення від b0 до bn вже відомі, і спробуємо висловити через них bn+1. Для цього розглянемо Доміношки, якої накрита ліва середня клітина, – є три можливих варіанти її розташування. В одному з них розглянута доміношка горизонтальна, і легко бачити, що кількість таких замощення смуги 3 × 2 (n + 1) збігається з числом замощення смуги 3 × 2n, Що дорівнює bn. В останніх двох варіантах доміношка вертикальна, а кожен з цих варіантів природним чином розбивається на два випадки: в одному з них кількість замощення одно bn, А в іншому знову можливо подразбіеніе на два види доданків, і т. Д.(Рис. 4).

Мал. 4.

Продовжуючи міркування зазначеним чином, приходимо до висновку, що послідовність bn повинна задовольняти наступному співвідношенню:

\ [B_ {n + 1} = b_n + (b_n + b_ {n-1} + \ ldots + b_1 + b_0) + (b_n + b_ {n-1} + \ ldots + b_1 + b_0). \]

Складаючи разом подібні доданки, ми приходимо до більш компактною версією:

\ [B_ {n + 1} = 3b_n + 2 (b_ {n-1} + \ ldots + b_1 + b_0). \]

В принципі, отримане співвідношення вже цілком придатне для того, щоб обчислити b15, Особливо якщо для цієї мети використовувати комп'ютер. Але якщо хочеться порахувати шукане значення вручну, зручніше спочатку спростити отриманий вираз. Для цього достатньо відняти від обох частин останньої формули той же співвідношення, але виписане не для bn+1, а для bn. Зробивши це, отримаємо

\ [B_ {n + 1} -b_n = (3b_n + 2b_ {n-1} + \ ldots + 2b_0) – (3b_ {n-1} + 2b_ {n-2} + \ ldots + 2b_0), \]

або, після очевидних перетворень:

\ [B_ {n + 1} = 4b_n-b_ {n-1}. \]

Останній вираз дозволяє отримати відповідь досить швидко навіть вручну: b2 = 11, b3 = 41, b4 = 153, b5 = 571, b6 = 2131, b7 = 7953, b8 = 29 681, b9 = 110 771, b10 = 413 401, b11 = 1 542 841, b12 = 5 757 961, b13 = 21 489 003, b14 = 80 198 051, b15 = 299 303 201.


Післямова

В підказках до задачі пропонувалося подумати над більш загальним питанням: скількома способами можна замостити фігурками доміно смужки 2 ×n і 3 × 2n? Цілком можливо, що читач резонно поцікавиться, як йде справа з відповіддю на нього. Виявляється, якщо послідовність задовольняє лінійному рекурентному співвідношенню, то існує формула для її n-го елемента, яку можна знайти, скориставшись методом виробляють функцій. Зокрема, для чисел Фібоначчі an справедлива формула Біне:

\ [A_n = \ dfrac % {\ sqrt %} \ cdot \ left (\ left (\ dfrac {1+ \ sqrt %} % \ right) ^ {n + 1} – \ left (\ dfrac {1 \ sqrt %} % \ right) ^ {n + 1} \ right), \]

а елементи bn задовольняють співвідношенню

\ [B_n = \ dfrac {(2 + \ sqrt3) ^ n} {3- \ sqrt3} + \ dfrac {(2 \ sqrt3) ^ n} {3+ \ sqrt3}. \]

Продемонструємо на прикладі послідовності bn, Як працює метод виробляють функцій. Для початку визначимо виробляє функцію цієї послідовності – нескінченну формальну суму виду \ (B (x) = b_0 + b_1x + b_2x ^ 2 + b_3x ^ 3 + \ ldots \). Зауважимо, що якщо помножити її на \ ((1-4x + x ^ 2) \) і розкрити дужки, то за рахунок того, що для всіх натуральних n виконується співвідношення \ (b_ {n + 1} = 4b_n-b_ {n-1} \), майже всі скоротиться:

\ [\ Hspace {-50mm} (1-4x + x ^ 2) B (x) \, = \, b_0 + \, b_1x \, + \, b_2x ^ 2 \, + \, b_3x ^ 3 \, + \ , \ ldots \ \ hspace % -4b_0x-4b_1x ^ 2-4b_2x ^ 3 \ ldots \ \ hspace % + \, \, b_0x ^ 2 \, \, + \, \, b_1x ^ 3 \, + \, \ ldots = b_0 + (b_1-4b_0) x. \]

Таким чином, розділивши на \ ((1-4x + x ^ 2) \), з урахуванням рівності b0 = 1 і b1 = 3 отримаємо вираз для B(x):

\ [B (x) = \ dfrac {b_0 + (b_1-4b_0) x} {1-4x + x ^ 2} = \ dfrac {1-x} {1-4x + x ^ 2}. \]

оскільки

\ (1-4x + x ^ 2 = (1- (2 + \ sqrt3) x) (1- (2- \ sqrt3) x) \),

ми можемо розкласти цю дріб на суму найпростіших:

\ [B (x) = \ dfrac % {3- \ sqrt3} \ cdot \ dfrac % {1- (2 + \ sqrt3) x} + \ dfrac % {3+ \ sqrt3} \ cdot \ dfrac % {1- (2- \ sqrt3) x}. \]

Після чого, двічі скориставшись формулою для суми геометричної прогресії,

\ [\ Dfrac % {1- (2 + \ sqrt3) x} = \ sum \ limits_ {n = 0} ^ {\ infty} (2 + \ sqrt3) ^ nx ^ n \ quad \ mbox {і} \ quad \ dfrac % {1- (2- \ sqrt3) x} = \ sum \ limits_ {n = 0} ^ {\ infty} (2 \ sqrt3) ^ nx ^ n, \]

переконуємося, що виробляє функція B(x) Приймає шуканий вид:

\ [B (x) = \ sum \ limits_ {n = 0} ^ {\ infty} b_nx ^ n = \ sum \ limits_ {n = 0} ^ {\ infty} \ left (\ dfrac {(2 + \ sqrt3 ) ^ n} {3- \ sqrt3} + \ dfrac {(2 \ sqrt3) ^ n} {3+ \ sqrt3} \ right) x ^ n. \]

Мал. 5.

Можна не обмежуватися замощення смуг і спробувати перейти до ще більш загальних питань. Розглянемо якусь зв'язкову область Γ на картатій папері. Природно поцікавитися, по-перше, чи можна в принципі замостити Γ Доміношки, а по-друге, якщо це можливо, то скількома способами. Перше, що спадає на думку – розфарбувати картату папір в чорний і білий кольори, як це роблять з шахівницею, і порахувати, скільки клітин якого кольору входить в область Γ. Так як кожна фігурка доміно покриває дві клітини різних кольорів, отримуємо необхідну умову: якщо замощення області Γ Доміношки існує, то число чорних і білих клітин всередині Γ збігається. Однак достатнім зазначена умова не є; переконатися в цьому допомагає приклад, який ви бачите на рис. 5.

Проте, існують методи, які не тільки відповідають на поставлені питання, але і роблять це за поліноміальний час (це означає, що кількість необхідних для відповіді на питання операцій залежить від розміру вхідних даних – розміру області Γ в даному випадку – як многочлен) , тобто досить швидко. Опишемо підхід, висхідний до голландського фізику Пітеру Кастелейну (Pieter Kasteleyn).Нехай область Γ складається з n чорних і n білих клітин. Пронумеруємо їх від 1 до 2n таким чином, щоб спочатку йшли чорні клітини, а потім – білі, після чого можна порівняти області Γ матрицю K = (Kuv) Розміру 2n×2n згідно наступним правилом (тут \ (i = \ sqrt {-1} \) – уявна одиниця):

\ [K_ % = \ left \ {\ begin % % 1, & \ mbox {якщо $ u $ і $ v $ – сусідні по горизонталі клітини}, \ i, & \ mbox {якщо $ u $ і $ v $ – сусідні по вертикалі клітини}, \ 0, & \ mbox {інакше}. \ \ end % \ right. \]

Тоді виявляється справедливою теорема Кастелейна, Яка стверджує, що кількість замощення області Γ Доміношки одно \ (\ sqrt {| \ det {K} |} \) (det – це визначник матриці). З огляду на, що сусідніми клітинами можуть бути тільки клітини різних кольорів, легко бачити, що матриця K насправді має блоковий вид

\ [K = \ begin % 0 & A \ A ^ {T} & 0 \ end %, \]

Мал. 6.

де A – матриця розміром n×n, а AT її транспонована матриця. Тому число замощення одно \ (\ sqrt {| \ det {A} ^ 2 |} \). Наприклад, якщо Γ – прямокутник 2 × 3, зображений на рис. 6, то матриця A має вигляд

\ [A = \ begin % 1 & i & 0 \ i & 1 & i \ 0 & i & 1 \ end %, \]

а число замощення одно \ (\ sqrt {| \ det {A} ^ 2 |} = \ det {A} = 3 \).

Замощення Доміношки областей на картатій папері можна інтерпретувати як окремий випадок ще більш загальної задачі. Саме, розглянемо довільний граф H. зроблене паросполучення (або димерной упаковкою) графа H називається будь-який набір його ребер, в якому кожна вершина графа зустрічається рівно один раз. Ясно, що якщо вершини графа H суть центри клітин деякої області Γ на картатій папері, а ребрами з'єднані ті з них, для яких відповідні клітини є сусідніми, то питання про кількість скоєних паросочетание графа H перетворюється в точності в питання про кількість замощення області Γ фігурками доміно. Наприклад, на рис. 7 зображені граф, що відповідає області Γ з рис. 6, а також його вчинені паросполучення.

Мал. 7.

Вчинені паросполучення тісним чином пов'язані з кістяк. Нагадаємо, що деревом називається будь-який зв'язний граф без циклів. Якщо ж даний зв'язний граф G, То його кістяк – це дерево, вершини якого збігаються з вершинами графа G, А кожне ребро є ребром графа G. З'ясуємо, як кожному кістяк графа G зіставити зроблене паросполучення деякого графа H. Для цього зробимо додаткове припущення, що граф G – плоский, тобто що його можна розташувати на площині так, щоб його ребра не перетиналися ніде, крім вершин. Тоді площину виявиться розбита ребрами графа G на області, звані гранями, Серед яких буде необмежена за розміром зовнішня грань. Будемо позначати безлічі вершин, ребер і граней графа G буквами V, E і F відповідно.

Побудуємо на основі графа G новий, розширений граф H. Для цього зазначимо вершини, середини ребер і центри граней ( "центром" межі можна вважати будь-яку точку всередині цієї межі) вихідного графа – це будуть вершини нового графа, а ребрами з'єднаємо такі пари вершин, для яких відповідні об'єкти в вихідному графі інцидентні (рис. 8)

Мал. 8. Відповідність між остовне деревом графа G і паросочетание графа H. вершини графа G відзначені чорними точками, Середини його ребер – білими, А центри граней – сірими. Зверніть увагу, що для зручності зовнішня грань графа G відзначена не крапкою, а зовнішнім контуром

Зауважимо, що в графі H є тільки два типи ребер: \ ((\ bar %, \ bar %) \) і \ ((\ bar %, \ bar %) \), де \ (v \ in {V } \), \ (e \ in {E} \), \ (f \ in {F} \), а рискою ми позначаємо відповідну вершину графа H. З одного боку, це означає, що зроблене паросполучення граф H не володіє, оскільки знаменита формула Ейлера для плоских графів говорить, що \ (| V | – | E | + | F | = 2 \). З іншого боку, ми бачимо, що це легко виправити: досить видалити з H дві вершини виду \ (\ bar % \) і \ (\ bar % \) разом з вихідними з них ребрами. Наприклад, видаливши вершину, відповідну зовнішньої межі, а також одну з вершин виду \ (\ bar % \), ми отримаємо граф H ', Який вже володіє паросочетание. Тепер, щоб на основі даного паросполучення графа H ' побудувати кістяк графа G, Досить взяти всі вхідні в паросочетание ребра виду \ ((\ bar %, \ bar %) \) і провести відповідні їм ребра e. Відзначимо, що вказане зіставлення завжди буде взаємно однозначним, якщо для отримання графа H ' ми будемо видаляти з H вершини, прилягають один до одного з точки зору графа G.

Як і для числа замощення Доміношки, для числа остовних дерев зв'язного графа без петель існує формула, що оперує визначником матриці. Саме, нехай xuv позначає кількість ребер, що з'єднують між собою вершини u і v графа G, А \ (\ deg % \) – ступінь вершини v, Тобто загальна кількість вихідних з неї ребер. Визначимо матрицю Δ наступним співвідношенням:

\ [\ Delta_ % = \ left \ {\ begin % % -x_ %, & \ mbox {якщо} \; \; u \ ne %, \ \ deg %, & \ mbox {якщо} \; \; u = v. \ \ end % \ right. \]

Очевидно, що сума чисел у кожному рядку матриці Δ дорівнює нулю, а значить, \ (\ det \ Delta = 0 \). Однак виявляється, що для досягнення мети досить викреслити з матриці рядок і стовпець,причому неважливо, які. Саме, якщо ми викреслимо рядок і стовпець, що відповідають вершинам u і v відповідно, а вийшла матрицю назвемо \ (\ Delta ^ {(u, v)} \), то число остовних дерев графа G одно \ (| \ det \ Delta ^ {(u, v)} | \). (Більш точно, кількість остовних дерев одно будь-якого алгебраїчного доповнення матриці Δ). Наприклад, якщо граф G складається з п'яти вершин, з'єднаних між собою ребрами так, як ми це бачили на рис. 8, то йому відповідає матриця

\ [\ Delta = \ begin % 2 & -1 & -1 & 0 & 0 \ -1 & 3 & -1 & -1 & 0 \ -1 & -1 & 3 & 0 & -1 \ \ 0 & -1 & 0 & 2 & -1 \ 0 & 0 & -1 & -1 & 2 \ end %, \]

і, згідно з описаною вище формулою, число остовних дерев одно, скажімо, \ (| \ det \ Delta ^ {(3,2)} | \):

\ [| \ Det \ Delta ^ {(3,2)} | = – \ det \ begin % 2 & -1 & 0 & 0 \ -1 & -1 & -1 & 0 \ 0 & 0 & 2 & -1 \ 0 & -1 & -1 & 2 \ end % = 11. \]

В даному випадку, число остовних дерев графа G легко обчислити безпосередньо. Справді, цей граф складається з двох циклів довжини три і чотири відповідно. Щоб отримати кістяк, необхідно видалити по одному ребру з кожного циклу, проте видаляються ребра повинні бути різними. Тому кількість остовних дерев є 3 · 4 – 1 = 11.

Цікаво, що спочатку цей результат, який оперує математичними поняттями графів і остовних дерев, був отриманий німецьким фізиком Густавом Кірхгофа для електричних ланцюгів.І правда, електричний ланцюг можна розглядати як граф, вершинами якого будуть вузли ланцюга, а ребрами – її гілки. Тепер якщо ребру, що з'єднує вершини u і v, Приписати опір відповідної гілки Ruv і розглянути матрицю T = (Tuv), Задану співвідношенням

\ [T_ % = \ left \ {\ begin % % – \ dfrac % {R_ %}, & \ mbox {якщо} \; \; u \ ne %, \ \ sum \ limits_ {w \ ne %} \ dfrac % {R_ %}, & \ mbox {якщо} \; \; u = v, \ \ end % \ right. \]

то із законів Кірхгофа можна вивести, що опір між вузлами k і l одно \ (\ dfrac {\ det {T _ {(k, l)}}} {\ det {T _ {(l)}}} \), де T(k, l) – матриця, що виходить викреслюванням рядків і стовпців, відповідних вузлів k і l, а T(l) – матриця, що виходить з T викреслюванням рядка і стовпця, відповідних вузлу l.

Наостанок зазначимо два класичних результату, що стосуються замощення Доміношки різних областей. По-перше, потрібно сказати про безпосередньо пов'язаної з нашим завданням формулою, яка виражає кількість способів замостити прямокутник розміру m×n:

\ [\ Prod \ limits_ {j = 1} ^ {[\ frac % %]} \ prod \ limits_ {k = 1} ^ {[\ frac % %]} \ left (4 \ cos ^ 2 \ frac {\ pi %} {m + 1} +4 \ cos ^ 2 \ frac {\ pi %} {n + 1} \ right). \]

Мал. 9.

Зверніть увагу, що якщо обидва числа m і n є непарними, виходить коректну відповідь – нуль. Найбільш типове доказ цієї формули базується на згаданій вище теоремі Кастелейна, але, звичайно, нею не обмежується.А по-друге, не можна не відзначити завдання про ацтекської діамант. Ацтекських діамантом розміру n називається фігура на площині, що складається з клітин, центри яких задовольняють нерівності \ (| x | + | y ​​| \ leqslant % \) (так, на рис. 9 зображений Ацтекський діамант розміру 4). Виявляється, загальна кількість замощення Доміношки Ацтекського діаманта розміру n одно \ (2 ^ {1 + 2 + \ ldots + n} = 2 ^ {n (n + 1) / 2} \). Цікаво поведінка типового замощення при великих n: теорема про полярному колі стверджує, що всередині вписаного в Ацтекський діамант окружності воно є хаотичним. А ось майже всі доміношки, що знаходяться поза цього кола – в кутах діаманта, будуть "заморожені": в нижньому і верхньому кутах вони майже завжди будуть горизонтальними, а в лівому і правому – вертикальними.


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: