9.2: П'ять кроків у порожнечу
- Page ID
- 64892
У цьому розділі ми поговоримо про ще одне підтвердження книги також завдяки Джону Конвею. Цей доказ служить введенням в дійсно потужну загальну техніку — ідею інваріанта. Інваріант - це якась величина, яку можна обчислити, що сама по собі не змінюється, оскільки змінюються інші речі. Звичайно, різні ситуації мають різні інваріантні величини.
Налаштування тут проста і відносно інтуїтивно зрозуміла. У нас є купа шашок на шаховій дошці — насправді у нас нескінченна кількість шашок, але не заповнюючи всю дошку, вони повністю заповнюють нескінченну півплощину, яку ми могли б взяти за набір.
\[ S = \{(x, y) x ∈ \mathbb{Z} ∧ y ∈ \mathbb{Z} ∧ y ≤ 0\}. \]
Див\(9.2.1\). Малюнок.
Подумайте про ці шашки як про армію, а верхній напівплан - «ворожа територія». Наша мета полягає в тому, щоб перемістити одного з наших солдатів на ворожу територію якнайдалі. Проблема в тому, що наші «солдати» рухаються так, як роблять шашки, перестрибуючи через іншого чоловіка (якого потім знімають з дошки). Зрозуміло, що ми можемо завести когось на ворожу територію — просто візьміть когось у другому ряду і стрибайте хлопця в першому ряду. Також досить легко помітити, що можна завести людину двома кроками на ворожу територію — ми могли б принести двох сусідніх людей на один крок на ворожу територію, один з них перестрибнув інший, а потім людина з переднього рангу може перестрибнути через нього.
Щойно викладена стратегія використовує\(4\) чоловіків (у тому сенсі, що вони видаляються з дошки -\(5\) якщо порахувати того, хто закінчує два кроки на ворожу територію, а також). Знайдіть стратегію переміщення когось на два кроки на ворожу територію, яка є більш ефективною — тобто передбачає меншу кількість стрибків.
Визначте найбільш ефективний спосіб отримати людині три кроки на ворожу територію. Справжня шашка дошка і шматки (або деякі монети, або скелі) може стати в нагоді.
Ми порахуємо людину, яка закінчує деяку кількість кроків вище\(x\) -осі, а також всі фігури, які стрибають і видаляються з дошки, як міра ефективності стратегії. Якщо ви виконали останню вправу правильно, ви повинні були виявити, що вісім чоловіків є мінімальним необхідним для отримання\(3\) кроків на ворожу територію. Поки що кількість людей, необхідних для отримання заданої відстані на ворожу територію, здається, завжди є силою\(2\).
| Кількість кроків | Кількість чоловіків |
| \(1\) | \(2\) |
| \(2\) | \(4\) |
| \(3\) | \(8\) |
Оскільки картинка іноді буквально варта тисячі слів, ми включаємо сюди\(3\) цифри, що ілюструють ходи, необхідні для того, щоб поставити\(1\) розвідника,\(2\) і\(3\) кроки в порожнечу.
Для того, щоб показати, що\(8\) чоловіків достатньо для того, щоб розвідник\(3\) заходив на ворожу територію, ми показуємо, що можна відтворити конфігурацію, яка може розмістити людину на два кроки — зрушена вгору на одну одиницю.
Ви можете бути здивовані, дізнавшись, що модель\(8\) чоловіків, які потрібні для того, щоб хтось три кроки в порожнечу, може бути заново створений - зміщений вгору на одну одиницю - використовуючи лише\(12\) чоловіків. Це означає, що ми можемо отримати людину\(4\) кроками на ворожу територію за допомогою\(12 + 8 = 20\) чоловіків. Ви очікували,\(16\) чи не так? (Я знаю, що я був!)
Справжнім сюрпризом є те, що отримати людині п'ять кроків на ворожу територію просто неможливо. Таким чином, послідовність, яку ми дивилися на насправді йде
\( 2, 4, 8, 20, \infty . \)
Доказ цього дивовижного результату працює за допомогою досить простої, але розумної стратегії. Ми присвоюємо числове значення набору чоловіків, які залежать від їхніх позицій - тоді ми показуємо, що це значення ніколи не збільшується, коли ми робимо «стрибки шашки» - нарешті, ми зауважимо, що значення, призначене чоловікові в положенні,\((0,5)\) дорівнює значенню всього вихідного набору чоловіків (що є, при цьому всі позиції в нижній півплощині зайняті). Це досить хороша стратегія, але як саме ми збираємося призначити ці числові значення?
Значення людини пов'язане з його віддаленістю від точки\((0,5)\) в тому, що часто називають «метрикою таксі». Ми не використовуємо пряму відстань, а скоріше визначаємо кількість блоків, які нам доведеться їхати у напрямку північ-південь та у напрямку схід-захід та скласти їх разом. Значення набору чоловіків - це сума їх індивідуальних цінностей. Оскільки нам потрібно мати справу зі значенням набору чоловіків, які повністю заповнюють нижню півплощину, ми повинні мати більшість цих значень бути досить крихітними! Сказати це більш зрілим і гідним чином: нескінченна сума цінностей людей у нашій армії повинна бути зближеним.
Раніше ми бачили геометричні ряди, які мають збіжні суми. Нагадаємо, формула для такої суми є
\[ \sum_{k=0}^{\infty} ar^k = \dfrac{a}{1-r}, \]
де\(a\) - початковий термін суми і\(r\) є загальним співвідношенням між долями.
Велике розуміння Конвея полягало в тому, щоб пов'язати повноваження деякого числа\(r\) з позиціями на дошці -\(r^k\) йде на квадратах, які знаходяться на відстані\(k\) від цільового місця. Якщо у нас є людина, яка насправді знаходиться в цільовому місці, він буде коштувати\(r^0\) або\(1\). Нам потрібно домовитися про дві речі: сума всіх повноважень\(r\) у початковій установці дошки повинна бути менше або дорівнює\(1\), а шашка-стрибки ходи повинні привести до того, що загальна вартість набору чоловіків спускається вниз або (в гіршому випадку) залишається незмінним. Ці цілі штовхають нас у різні боки: для того, щоб початкова сума була меншою\(1\), ми хотіли б вибрати,\(r\) щоб бути досить маленькою. Для того, щоб рухатися в шашку, нам потрібно вибрати,\(r\) щоб бути (відносно) більше. Чи є значення\(r\) того, що робить трюк? Чи можемо ми знайти баланс між цими конкуруючими бажаннями?
Подумайте про зміну значення нашого інваріанта, як хід стрибка шашки робиться. Див\(9.2.6\). Малюнок.
Якщо ми виберемо\(r\) так, що\(r^{k+2} + r^{k+1} \; \leq \; r^k\) тоді хід, що стрибає в шашку, в гіршому випадку залишить загальну суму фіксованою. Зверніть увагу, що\(r<1\) до тих пір, поки шашка-стрибок хід, який відводить нас від цільової позиції, безумовно, зменшить загальну суму.
Як це часто буває, ми проаналізуємо нерівність, дивлячись замість цього на відповідну рівність. Яке значення\(r\) робить\(r^{k+2} + r^{k+1} = r^k\)? Відповідь полягає в тому, що\(r\) повинен бути корінь квадратного рівняння\(x^2+x-1\).
Виконайте алгебру, щоб перевірити попереднє твердження.
Знайдіть значення,\(r\) яке вирішує вищевказане рівняння.
Сподіваємось, ви використовували квадратичну формулу для вирішення попередньої вправи. Ви, звичайно, повинні були знайти два рішення,\(-1.618033989\ldots\) і\(.618033989\ldots\), ці десяткові наближення насправді\(-\phi\) і\(\dfrac{1}{\phi}\), де\(\displaystyle \phi = \frac{1+\sqrt{5}}{2}\) знаменитий «золотий перетин». Якщо ми сподіваємося на суму над усіма займаними позиціями,\(r^k\) щоб бути збіжними, нам потрібно\(|r|<1\), тому негативне рішення є стороннім і тому\(r^{k+2} + r^{k+1} \; \leq \; r^k\) нерівність вірна в інтервалі\([\dfrac{1}{\phi}, 1)\).
Далі ми хочемо подивитися на значення цього інваріанту, коли «чоловіки» займають всі позиції с\(y\leq0\). Дивлячись на малюнок,\(9.2.5\) ви можете побачити, що є один квадрат зі значенням\(r^5\), є\(3\) квадрати зі значенням\(r^6\), є 5 квадратів зі значенням\(r^7\), і так далі. Сума\(S\), значень всіх спочатку займаних позицій дорівнює
\[ S = r^5 \sum_{k=0}^{\infty} (2k+1) r^k. \]
Ми раніше бачили, як вирішувати для значення нескінченну суму за участю повноважень\(r\). У виразі вище ми маємо повноваження,\(r\) але також помножені на непарні числа. Чи можемо ми вирішити щось подібне?
Давайте спробуємо той же трюк, який працює для геометричної суми. Нехай
\[ T = \sum_{k=0}^{\infty} (2k+1) r^k = 1 + 3r + 5r^2 + 7r^3 + ... \]
Зауважте, що
\[ rT = \sum_{k=0}^{\infty} (2k+1) r^{k+1} = r + 3r^2 + 5r^3 + 7r^4 + ... \]
і з цього випливає, що
\[ T - rT = 1 + 2 \sum_{k=1}^{\infty} r^{k} = 1 + 2r + 2r^2 + 2r^3 + 2r^4 + ... \]
Трохи більше алгебри (і формула для суми геометричного ряду) призводить нас до
\[ T = \dfrac{1}{1-r} \left(1 + \dfrac{2r}{1-r} \right), \]
що спрощує
\[ T = \dfrac{1+r}{1-r^2}. \]
Наостанок нагадаємо, що нас дійсно цікавить\(S = r^5 \cdot T\), або
\[ S = \dfrac{r^5 + r^6}{(1 − r)^2} . \]
Цікаво виходити з цього виразу для того, щоб\(S\), використовуючи той факт, що\(r\) задовольняє\(x^2 = 1 - x\), отримати дещо дивовижний факт, що\(S=1\).
Справа в тому, що\(S=1\) має надзвичайний наслідок. Для того, щоб отримати одну шашку на позицію,\((0,5)\) нам потрібно буде використовувати всіх!
Для набору, що складається всього лише з однієї шашки, розташованої\((0,5)\) за значенням нашого інваріанта є\(1\). З іншого боку, набір, що складається з усієї армії, що вишикувалася на і нижче\(x\) -осі, також дає a\(1\). Кожен хід шашки або не змінює значення інваріанта, або зменшує його. Найкраще, на що ми могли б сподіватися, це те, що не буде необхідності в таких рухах, які зменшують інваріант - проте ми все ще не могли змусити людину\((0,5)\) за кінцеву кількість ходів.
Вправи:
Зробіть алгебру (і покажіть всю свою роботу!) довести, що інваріант, визначений у цьому розділі, насправді має значення\(1\) для множини всіх чоловіків, що займають\(x\) -вісь і нижню півплощину.
«Втеча клонів» - симпатична головоломка, спочатку запропонована Максимом Концевичем. Гра ведеться на нескінченній шаховій дошці, обмеженій першим квадрантом - тобто квадрати можуть бути ідентифіковані точками, що мають цілочисельні координати\((x, y)\) з\(x > 0\) і\(y > 0\). «Клони» - це маркери (шашки, монети, дрібні камені, що завгодно), які можуть рухатися лише одним способом — якщо квадрати безпосередньо над і праворуч від клону порожні, то він може зробити «хід клону». Клон переміщається на один пробіл вгору, а копія розміщується в комірці праворуч. Ми починаємо з трьох клонів\((1, 1)\), які займають клітини,\((2, 1)\) і\((1, 2)\) - ми будемо називати ці три шахові квадрати «в'язницею». Питання полягає в наступному: чи можуть ці три клони втекти з в'язниці?
Ви повинні або продемонструвати послідовність ходів, яка звільняє всі три клони, або надати аргумент, що завдання неможливе.