Зворотні задачі

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне агентство з освіти
Державна освітня установа вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Зворотні задачі
Виконала:
студентка V курсу математичного факультету
Ковязіна Юлія Миколаївна
Науковий керівник:
кандидат фізико-математичних наук, доцент кафедри алгебри та геометрії І. А. Семенова
Рецензент:
ст. викладач кафедри алгебри і геометрії
А. М. Семенов
Допущена до захисту в державної атестаційної комісії
«___» __________2005 Р. Зав. Кафедрою Є.М. Вечтомов
«___»___________ 2005 Декан факультету В.І. Варанкіна
Кіров 2005
Зміст
Введення ................................................. .................................................. 3
Глава 1 ................................................ .................................................. ... 6
1.1 Задача про ханойської вежі ............................................. ............ 6
1.2 Задача про розрізуванні піци ............................................. ........... 7
1.3 Завдання Йосипа Флавія .............................................. ............... 10
Глава 2. Рішення задач ................................................ ......................... 19
Висновок ................................................. ........................................... 41
Бібліографічний список ................................................ ................... 42
Введення
Дискретна математика в даний час грає велику роль у розробці принципів роботи комп'ютера, тому що робота комп'ютера являє собою виконання послідовності дискретних кроків, які призводять до вирішення поставленої перед комп'ютером завдання.
Розглянута мною тема «Поворотні завдання» є невеликою частиною дискретної математики, тому дана тема на сьогоднішній момент є не менш актуальною.
Мета моєї роботи - вивчити наявний теоретичний і практичний матеріал по даній темі і застосувати його до вирішення завдань.
Дана робота складається з вступу, двох розділів і висновку. У вступі наводяться приклади рекурентних співвідношень, з допомогою яких можна задати деякі послідовності, а так само рекурентні співвідношення, що можуть використовуватися при вирішенні завдань. У першому розділі описуються три завдання: задача про ханойської вежі, задача про розрізуванні піци і завдання Йосипа Флавія, а також доводяться деякі факти, які в літературі пропонуються для самостійного докази. Другий розділ присвячено вирішенню завдань на дану тему. У висновку робляться висновки про виконану роботу і вказуються подальші перспективи.
В основі рішення зворотних задач лежить ідея повернення (або рекурентності), згідно з якою рішення всієї задачі залежить від рішення того ж самого завдання менших розмірів.
Тема «Поворотні послідовності» не є ізольованою, ніде не використовуваної теорією. Навпаки, поворотні послідовності близькі до шкільного курсу математики (арифметична і геометрична прогресії, послідовності квадратів і кубів натуральних чисел і т.д.), використовуються найвищою алгебри, геометрії, математичному аналізі та інших математичних дисциплінах. Теорія зворотних послідовностей складає особливу главу математичної дисципліни, званої обчисленням кінцевих різниць; є приватну главу про послідовностях.
Таким чином, поворотні послідовності є справжньою маленькою теорією, закінченою, простий, ясною.
Визначення: Нехай є послідовність {u n}:
u 1, u 2, u 3, ..., u n, ... (1)
Якщо існує натуральне число k і числа a 1, a 2, a 3, ..., a k ​​(справжні чи уявні) такі що, починаючи з деякого номера n і для всіх наступних номерів
u n + k = a 1 ∙ u n + k-1 + a 2 ∙ u n + k-2 + ... + a k ∙ u n при n ≥ 1 (2)
то послідовність (1) називається поворотної послідовністю порядку k, а співвідношення (2) - зворотним (рекурентним) рівнянням порядку k.
Таким чином, знаючи k перших членів послідовності можна визначити всю послідовність, тобто обчислити будь-який наперед заданий член послідовності.
За допомогою рекурентних співвідношень можна задати наступні послідовності:
1). Геометрична прогресія
u n +1 = q ∙ u n
2). Арифметична прогресія
u n +1 = u n + d
інший вид u n +2 = 2 ∙ u n +1 - u n
3). Послідовність чисел Фіббоначі
u n +2 = u n +1 + u n
4). Послідовність квадратів натуральних чисел
u n +1 = u n + 2 ∙ n + 1
інший вид u n +3 = 3 ∙ u n +2 - 3 ∙ u n +1 + u n
5). Послідовність кубів натуральних чисел
u n +4 = 4 ∙ u n +3 - 6 ∙ u n +2 +4 ∙ u n +1 - u n
6). Всі періодичні послідовності: u 1, u 2, ..., u k +1, ...
u n + k = u n.
Також рекурентні співвідношення можуть використовуватися при вирішенні задач (зокрема, при доказі рівностей):
7). Інтегрування найпростіших раціональних дробів IV типу

Позначимо I m = , Де t = x +
I m = ∙ I m-1
8). Інтеграл I n =
I n = ∙ I n-2
9). Формула довжини сторони при подвоєнні числа сторін правильного вписаного багатокутника
a n = , При n ≥ 2
R - радіус описаного кола
Якщо сторона a 1 вихідного правильного вписаного багатокутника задана, то a n є сторона багатокутника, отриманого з вихідного (n-1) кратним подвоєнням числа сторін.
10). Диференціальні рівняння вищих порядків
y (n) = f (x, y, y ', y », ..., y (n -1))
11). Визначник Вандермонда
Δ n = Δ (x 1, x 2, ..., x n) =
Δ (x 1, x 2, ..., x n) = (x n -X 1) (x n -1-x 1) ... (x 2-x 1) ∙ Δ (x 2, x 3, ..., x n).
Глава 1
1.1. Задача про ханойської вежі
Розглянемо спочатку маленьку витончену головоломку під назвою ханойська вежа, яку придумав французький математик Едуард Люка в 1883 р. Вежа являє собою вісім дисків, нанизаних в порядку зменшення розмірів на один з трьох кілочків. Завдання полягає в тому, щоб перемістити всю вежу на один з інших кілочків, переносячи щоразу лише один диск, і не поміщаючи більший диск на менший.
Будемо вирішувати цю задачу в загальному вигляді, тобто подивимося, що буде у випадку n дисків.
Будемо говорити, що T n є мінімальне число перекладань, необхідних для переміщення n дисків з одного кілочка на інший за правилами Люка.
Розглянемо крайні випадки: Т 0 = 0, T 1 = 1, T 2 = 3, T 3 = 7. Експеримент з трьома дисками дає ключ до загальним правилом переміщення n дисків: спочатку ми переміщаємо (n-1) менших дисків на будь-який з кілочків (що вимагає Т n -1 перекладань), потім перекладаємо найбільший диск (одне перекладання) і, нарешті, поміщаємо (n-1) менших дисків назад на самий великий диск (ще Т n -1 перекладань). Таким чином, n дисків (при n> 0) можна перемістити найбільше за 2T n -1 +1 перекладань (тобто досить перекладань): T n ≤ 2T n -1 +1.
Зараз покажемо, що необхідно 2T n -1 +1 перекладань. На деякому етапі ми зобов'язані перемістити найбільший диск. Коли ми це робимо, (n-1) менших дисків повинні перебувати на одному кілочку, а для того щоб зібрати їх разом, буде потрібно щонайменше Т n -1 перекладань. Найбільший диск можна перекладати й більше одного разу. Але після переміщення найбільшого диска в останній раз ми зобов'язані помістити (n-1) менших дисків (які знову повинні перебувати на одному кілочку) назад на найбільший диск, що також вимагає Т n -1 перекладань. Отже, T n ≥ 2T n -1 +1.
Ці два нерівності разом з тривіальним рішенням при n = 0 дають рекурентне співвідношення:
(1)
Т 0 = 0
T n = 2T n -1 +1 при n> 0
При досить великому n для обчислення Т n потрібно занадто багато часу, тому отримаємо Т n в простій, компактною, «замкнутої формі», що дозволить обчислити Т n швидко.
Перший спосіб вирішення (вгадування правильного рішення з наступним доказом, що наша здогадка вірна).
Обчислимо: Т 3 = 2 ∙ 3 +1 = 7; Т 4 = 2 ∙ 7 +1; Т 5 = 2 ∙ 15 +1; Т 6 = 2 ∙ 31 +1 = 63. Тепер можна зробити припущення, що
Т n = 2 n - 1 при n ≥ 0. (2)
Доведемо методом математичної індукції по числу n:
1) База: n = 0, Т 0 = 2 0 -1 = 1-1 = 0 (вірно);
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n-1). Доведемо для t = n: Т n = 2T n -1 +1 2 (2 n -1 -1) +1 = 2 ∙ 2 n -1 -2 +1 = 2 n - 1
З пунктів 1 і 2 слід: при n ≥ 0 Т n = 2 n - 1
Другий спосіб вирішення.
До обох частин співвідношення (1) додамо 1:
Т 0 +1 = 1,
Т n +1 = 2T n -1 +2 при n> 0.
Позначимо U n = T n +1, тоді отримаємо
U 0 = 1
U n = 2U n -1 при n> 0.
Рішенням цієї рекурсії є U n = 2 n, отже Т n = 2 n -1.
1 .2. Задача про розрізуванні піци
Формулювання завдання: скільки шматків піци можна отримати, роблячи n прямолінійних розрізів ножем? Або, Яке максимальне число L n областей, на які площину ділиться n прямими?
1
Знову почнемо з розгляду крайніх випадків. SHAPE \ * MERGEFORMAT
2
L 1 = 2
2
1
3
4
L 2 = 4
1
L 0 = 1

Експеримент з трьома прямими показує, що додана третя пряма може розсікати найбільше три старих області незалежно від того, як розташовані перші дві прямі:

1b
2
4a
4b
3a
3b
Таким чином, L 3 = 4 +3 = 7 - найбільше, що можна зробити.
Узагальнюючи, приходимо до наступного висновку: нова n-я пряма (при n> 0) збільшує число областей на k ó коли розсікає k старих областей ó коли перетинає колишні прямі в (k-1) різних місцях. Дві прямі можуть перетинатися не більше ніж в одній точці. Тому нова пряма може перетинати (n-1) старих прямих не більше ніж в (n-1) різних точках, і ми повинні мати k ≤ n. Встановлена ​​верхня межа:
L n ≤ L n -1 + n при n> 0
У цій формулі можна досягти рівності наступним чином: проводимо n-у пряму так, щоб вона не була паралельна ніякої іншої прямої (отже, вона перетинає кожну з них) і так, щоб вона не проходила через жодну з наявних точок перетину (отже, вона перетинає кожну з прямих у різних місцях). Тому рекурентне співвідношення має вигляд:
L 0 = 1
L n = L n -1 + n при n> 0
Тепер отримаємо рішення в замкненій формі.
L n = L n -1 + n = L n -2 + (n-1) + n = L n -3 + (n-2) + (n-1) + n = ... = L 0 + 1 + 2 + + ... + (n-2) + (n-1) + n = 1 +
L n = + 1 при n ≥ 0 (3)
Доведемо отримане рівність методом математичної індукції.
1) База: n = 0, L 0 = = 1 (вірно);
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n-1). Доведемо для t = n:
L n = L n -1 + n = =
З пунктів 1 і 2 слід: при n ≥ 0 L n = + 1
3
А тепер невелика варіація на тему прямих на площині: припустимо, що замість прямих ліній ми використовуємо ламані лінії, кожна з яких представлена ​​одним «зігом». Яке максимальне число Z n областей, на які площину ділиться n такими ламаними лініями?
2
Окремі випадки:
2
1
1
4
6
5
7
Z 1 = 2
Z 2 = 7


Ламана лінія подібна двом прямим з тією лише відмінністю, що області зливаються, якщо «дві» прямі не продовжувати після їх перетину:
1
4
3
2
Області 2, 3 і 4, які були б розділені за наявності двох прямих, перетворюються в єдину область у випадку однієї ламаної лінії, тобто ми втрачаємо дві області. І якщо привести все в належний порядок, то точка зламу повинна лежати «по той бік» перетинів з іншими лініями, і ми втрачаємо тільки дві області на одну лінію. Таким чином,
Z n = L 2 n - 2n = = 2n 2-n +1 при n ≥ 0 (4)
Порівнюючи рішення в замкненій формі (3) і (4), ми приходимо до висновку, що при великому n,
L n ~ ,
Z n ~ 2n 2,
так що ламані лінії дають приблизно в чотири рази більше областей, ніж прямі.
1.3. Завдання Йосипа Флавія
Формулювання завдання: в коло вибудувано n людина, пронумерованих числами від 1 до n, і виключається кожен другий з залишилися до тих пір, поки не вціліє тільки одна людина. Визначити номер вцілілого, J (n).
1
2
3
4
5
6
7
8
9
100000
Наприклад, при n = 10 порядок виключення - 2, 4, 6, 8, 10, 3, 7, 1, 9, так що залишається номер 5, тобто J (10) = 5. При n = 2 номер вцілілого J (2) = 1. Можна було б припустити, що J (n) = при парному n. Однак це не так - припущення порушується при n = 4 і n = 6.
N
1
2
3
4
5
6
J (n)
1
1
3
1
3
5
J (n) завжди буде непарній, тому що перший обхід по колу виключає всі парні номери. До того ж, якщо саме n парне, ми приходимо до ситуації, подібної до тієї, з якої почали, за винятком того, що залишається вдвічі менше людей, і їх номери змінюються.
Отже, вирішимо поставлену задачу.
Припустимо, що спочатку є 2n людей. Після першого обходу ми залишаємося з номерами:
1
33
5
7
....
2n-3
2n-1
Наступний обхід буде починатися з номеру 3. Це теж саме, якби ми починали з n людей, за винятком того, що номер кожного вцілілого подвоюється і зменшується на 1. Тим самим
J (2n) = 2 ∙ J (n) - 1 при n ≥ 1 (5)
Тепер можна швидко просуватися до великих n. Наприклад, нам відомо, що J (10) = 5, тому J (20) = 2 ∙ J (10) - 1 = 2 ∙ 5 - 1 = 9, аналогічно J (40) = 2 ∙ J (20) - 1 = 17, і взагалі можна вивести, що
J (5 ∙ 2 m) = 2 m +1 +1.
J (5 ∙ 2 m) = J (2 ∙ 2 m -1 ∙ 5) = 2 ∙ J (2 m -1 ∙ 5) - 1 = 2 ∙ J (2 ∙ 2 m -2 ∙ 5) - 1 = 2 лютого ∙ J (2 m -2 ∙ 5) - 2 1 - 1 = = 2 березня ∙ J (2 m -3 ∙ 5) - 2 2 - 2 1 - 1 = 2 квітня ∙ J (2 m -4 ∙ 5) - 2 3 - 2 2 - 2 1 - 1 = ... = 2 m ∙ J (5) - (2 m -1 +2 m -2 +      + ... +2 3 +2 2 +2 1 +1) = 2 m ∙ J (5) - = 2 m ∙ 3 - 2 m + 1 = 2 m +1 +1.
Тепер подивимося, що буде у випадку, коли є 2n +1 людей. Після першого обходу жертва з номером 1 знищується відразу після жертви з номером 2n, і ми залишаємося з номерами:
3
5
7
9
....
2n-1
2n +1
Отримали майже первісну ситуацію з n людьми, але на цей раз номери уцілілих подвоюються і збільшуються на 1. Таким чином,
J (2n +1) = 2 ∙ J (n) + 1 при n ≥ 1 (6)
Об'єднання рівнянь (5) і (6) з рівнянням J (1) = 1 дає рекурентне співвідношення, яке визначає J у всіх випадках:
J (1) = 1
J (2n) = 2 ∙ J (n) - 1 при n ≥ 1 (7)
J (2n +1) = 2 ∙ J (n) + 1 при n ≥ 1
Вирішимо дане рекурентне співвідношення. Складемо таблицю перших значень J (n):
n
1
2 Березня
4 5 6 7
8 9 10 11 12 13 14 15
16
J (n)
1
3 січня
1 3 5 7
1 3 5 7 9 11 13 15
1
Якщо згрупувати значення n за ступенями двійки (у таблиці ці групи відокремлені вертикальними лініями), то в кожній групі J (n) завжди буде починатися з 1, а потім збільшуватися на 2. Отже, якщо записати n у вигляді n = 2 m + k, де 2 m - найбільша ступінь 2, не перевершує n, а k - те, що залишається, то рішення рекурентного співвідношення повинне мати вигляд:
J (2 m + k) = 2k +1 при m ≥ 0 і 0 ≤ k <2 m (8)
(Якщо 2 m ≤ n <2 m +1, то залишок k = n-2 m задовольняє нерівності 2 m ≤ k +2 m <2 m +1, тобто 0 ≤ k <2 m)
Доведемо (8) методом математичної індукції по m.
1) База: m = 0 => k = 0
J (2 0 +0) = J (1) = 2 ∙ 0 + 1 = 1 (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (m - 1). Доведемо для t = m:
a) якщо m> 0 і 2 m + k = 2n, то k - парне і J (2 m + k) = J (2 (2 m -1 + )) = 2 ∙ J (2 m -1 + ) - 1 2 (2 ∙ + 1) -1 = 2 k + 1
b) якщо m> 0 і 2 m + k = 2n +1, то k - непарне (тобто k = 2t +1) і J (2 m + k) = = J (2 m + (2t +1 )) = J (2 (2 m -1 + t) +1) 2 ∙ J (2 m -1 + t) + 1 2 (2t +1) + 1 = 2 k + 1
Інший спосіб докази, коли k - непарне:
Можна помітити, що J (2n +1) - J (2n) = 2, тоді J (2 m + k) = 2 + J (2 m + (K--1)) J (2 m + k) = 2 + 2 (k -1) + 1 => J (2 m + k) = 2k +1.
З пунктів 1 і 2 слід: при m ≥ 0 і 0 ≤ k <2 m J (2 m + k) = 2k +1.
Рішення будь-якої задачі може бути узагальнене так, що його можна застосувати до більш широкого кола завдань. Тому вивчимо рішення (8) і досліджуємо деякі узагальнення рекурентного співвідношення (7).
Звернемося до двійковим уявленням величин n і J (n) (тому що ступеня 2 відігравали важливу роль у нашому пошуку рішення).
n = (b m b m-1 ... b 1 b 0) 2;
тобто n = b m 2 m + b m -1 2 m -1 + ... + b 1 2 + b 0
де кожне b i дорівнює 0 або 1, причому старший біт b m дорівнює 1. Згадуючи, що n = 2 m + k, послідовно отримуємо:
n = (1 b m-1 ... b 1 b 0) 2
k = (0 b m-1 ... b 1 b 0) 2
(Тому що k = n-2 m = 2 m + b m-1 2 m-1 + ... + b 1 2 + b 0 - 2 m = 0 ∙ 2 m + b m-1 2 m-1 + ... + b 1 2 + b 0)
2k = (b m-1 ... b 1 b 0 0) 2
(Тому що 2 k = 2 (b m -1 2 m -1 + b m -2 2 m -2 ... + b 1 2 + b 0) = b m -1 2 m + b m -2 2 m -1 + ... + b 1 2 2 + b 0 2 +0)
2k +1 = (b m-1 ... b 1 b 0 1) 2
J (n) = (b m-1 ... b 1 b 0 b m) 2
(Тому J (n) = 2k +1 і b m = 1)
Таким чином, ми отримали, що
J ((b m b m-1 ... b 1 b 0) 2) = (b m-1 ... b 1 b 0 b m) 2 (9)
тобто J (n) виходить шляхом циклічного зсуву двійкового подання n вліво на один зсув.
Розглянемо властивості функції J (n).
Якщо ми почнемо з n і ітеріруем J-функцію m +1 раз, то тим самим здійснюємо циклічний зсув на m +1 бітів, а тому n є (m +1)-бітовим числом, то ми могли б розраховувати в результаті знову отримати n. Але це не зовсім так. Наприклад, якщо n = 27, то J (11011) = ((10111) 2), але потім J (10111) = ((1111) 2), і процес обривається: коли 0 стає старшим бітом - він пропадає (т. к. прийнято, що коефіцієнт при старшого ступеня не дорівнює 0). У дійсності J (n) завжди повинно бути ≤ n за визначенням, тому що J (n) є номер вцілілого; і якщо J (n) <n, ми ніколи не зможемо отримати знову n в наступних ітераціях.
Багаторазове застосування J породжує послідовність відбувають значень, що сягають, врешті-решт «нерухомої точки» n, такий, що J (n) = n. Доведемо, що J породжує послідовність відбувають значень, тобто покажемо, що 2 n > 2 n -1 + 2 n -2 + ... +2 1 + 1 при n ≥ 1.
Доведемо методом математичної індукції по n:
1) База: n = 1, 2 1> 2 0 (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1), тобто виконується нерівність 2 t -1> 2 t -2 + 2 t -3 + ... +2 1 + 1. Доведемо для t = n:
(2 n -1> 2 n -2 + 2 n -3 + ... +2 1 + 1) помножимо на 2, отримаємо 2 n > 2 n -1 + 2 n -2 + ... +2 2 + 2 1. Ліва та права частини нерівності парні числа, тоді між ними є хоча б одне непарне число, отже, додаток 1 до правої частини нерівності (парне число +1 = непарне число) нерівність не змінить. Т.ч. отримуємо потрібне нам нерівність: 2 n > 2 n -1 + 2 n -2 + ... +2 1 + 1 при n ≥ 1.
Властивість циклічного зсуву дозволяє з'ясувати, чим буде «нерухома точка»: ітерірованіе функції m і більше разів завжди буде породжувати набір з одних одиниць зі значенням , Де ν (n) - ​​число рівних 1 бітів у двійковому поданні n (це випливає з того, що маємо послідовність 2 0, 2 1, 2 2, ..., 2 n -1, 2 n, і за формулою суми геометричної прогресії отримуємо ). Так, наприклад: ν (27) = ν (11011) = 4, тоді J (J (... J (27) ...)) = 2 4 -1 = 15
2 і більше


Тепер давайте повернемося до нашого початкового припущенням, що J (n) = при парному n. Взагалі-то це невірно, але ми з'ясуємо, коли це вірно: J (n) = , Тоді 2k +1 = => K = . Якщо число k = = ціле, то n = 2 m + k буде рішенням, тому що k <2 m. Неважко переконатися, що (2 m - 2) кратно 3, коли m непарне, але не коли m парне. Дійсно, якщо m - непарне, то 2 m - 2 = 2 лютого k +1 - 2 = 2 (4 k - 1). Доведемо методом математичної індукції, що (4 k - 1) ділиться на три (де ):
1) База: k = 1, 4-1 = 3, три ділиться на три (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (k-1), тобто (4 t -1) ділиться на три. Доведемо для t = k:
4 k - 1 = 4 (4 k -1 - 1) + 3 (4 k -1 - 1) ділиться на три, і 3 ділиться на три => (4 до -1) ділиться на три.
Таким чином, показали, що для m - непарного (2 m - 2) ділиться на 3.
Тепер покажемо, що при m - парному (2 m - 2) не ділиться на 3. Припустимо гидке: нехай (2 m - 2) поділяється на 3 при парному m, тоді , Числа 2 і 3 взаімнопростие, отже, ( ) Повинно ділиться на 3, тобто = 3q , Але , A , Тобто отримали, що , А це не вірно. Отже, наше припущення не вірне і 2 m - 2 не ділиться на 3 при парній m.
Таким чином, маємо нескінченно багато рішень рівняння J (n) = , І перші такі:
m
k
N = 2 m + k
J (n) = 2k +1 =
n (двійкове)
1
0
2
1
10
3
2
10
5
1010
5
10
42
21
101010
7
42
170
85
10101010
Правий крайній стовпець містить двійкові числа, циклічний зсув яких на одне позицію вліво дає той же самий результат, що і звичайний зрушення на одну позицію вправо (розподіл навпіл).
Далі узагальнимо J - функцію, тобто розглянемо рекурентність схожу з (7), але з іншими константами: α, β і γ; знайдемо рішення в замкненій формі.
f (1) = α,
f (2n) = 2f (n) + β при n ≥ 1, (10)
f (2n + 1) = 2f (n) + γ при n ≥ 1.
Складемо таблицю для малих значень n:
n
f (n)
1
α
2
3
2α + β
2α + γ
4
5
6
7
4α + 3β
4α + 2β + γ
4α + β +2 γ
4α +3 γ
8
9
8α + 7β
8α + 6β + γ
Підпис: n f (n) 1 α 2 Березня 2α + β 2α + γ 4 5 6 7 4α + 3β 4α + 2β + γ 4α + β +2 γ 4α +3 γ 9 серпня 8α + 7β 8α + 6β + γ Аналізуючи таблицю можна зробити припущення, що коефіцієнти при α рівні найбільшим ступенями 2, не переважаючим n; між послідовностями 2 коефіцієнти при β зменшуються на 1 аж до 0, а при γ збільшуються на 1, починаючи з 0. Якщо виразити f (n) у вигляді:
f (n) = A (n) ∙ α + B (n) ∙ β + C (n) ∙ γ (11)
то, мабуть,
A (n) = 2 m ,
B (n) = 2 m -1-k, (12)
С (n) = k.
Тут n = 2 m + K і 0 ≤ k <2 m             при n ≥ 1.
Доведемо співвідношення (11) і (12).
Доведемо (11) методом математичної індукції по числу n і при цьому будемо вважати, що (12) виконується.
1) База: n = 1 = 2 0 +0 (m = k = 0), f (1) = A (1) ∙ α + B (1) ∙ β + C (1) ∙ γ = = 2 0 ∙ α + (2 0 -1-0) ∙ β +0 ∙ γ = α (Вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1), тобто виконується рівність f (t) = A (t) ∙ α + B (t) ∙ β + C (t) ∙ γ. Доведемо для t = n:
a) якщо n - парне, тоді k теж парне, тобто k = 2t, і f (n) = f (2 m +2 t) = = f (2 (2 m -1 + t)) 2 ∙ f (2 m -1 + t) + β 2 ∙ (A (2 m -1 + t) ∙ α + B (2 m -1 + t) ∙ β + C (2 m -1 + + t) ∙ γ) + β 2 (2 m -1 ∙ α + (2 m -1-1-t) ∙ β + t ∙ γ) + β = 2 m ∙ α + (2 m-1-2t) ∙ β + 2t ∙ γ = 2 m ∙ α + + (2 m-1-k) ∙ β + k ∙ γ = A (n) ∙ α + B (n) ∙ β + C (n) ∙ γ;
b) якщо n - непарне, тоді k теж непарній, тобто k = 2t +1, і f (n) = = f (2 m +2 t +1) = f (2 (2 m-1 + t) +1) 2 ∙ f (2 m-1 + t) + γ 2 ∙ (A (2 m-1 + t) ∙ α + B (2 m-1 + + t) ∙ β + C (2 m-1 + t) ∙ γ) + γ 2 (2 m-1 ∙ α + (2 m-1-1-t) ∙ β + t ∙ γ) + γ = 2 m ∙ α + + (2 m -1 - (2t +1)) ∙ β + (2t +1) ∙ γ = 2 m ∙ α + + (2 m-1-k) ∙ β + k ∙ γ = A (n) ∙ α + B (n) ∙ β + C (n) ∙ γ.
З пунктів 1 і 2 слід: для n ≥ 1 f (n) = A (n) ∙ α + B (n) ∙ β + C (n) ∙ γ.
Тепер доведемо (12) у припущенні, що (11) виконується.
Якщо n - парне, тоді по співвідношенню (10) f (2n) = 2f (n) + β. Підставляючи в це рівність співвідношення (11) отримаємо:
A (2n) ∙ α + B (2n) ∙ β + C (2n) ∙ γ = 2 (A (n) ∙ α + B (n) ∙ β + C (n) ∙ γ) + β
(A (2n) - 2A (n)) ∙ α + (B (2n) - 2B (n) -1) ∙ β + (C (2n) - 2C (n)) ∙ γ = 0
Тепер підставимо співвідношення (12) в даний рівність і подивимося, чи буде воно виконуватися: тому n = 2 m + K => 2n = 2 m +1 +2 k, тоді A (2n) = 2 m +1 , B (2n) = 2 m +1-1-2k, С (n) = 2k. Підставляємо: (2 m +1 -2 ∙ 2 m) ∙ α + + (2 m +1-1-2k-2 (2 m-1-k) -1) ∙ β + (2k-2k) ∙ γ = 0 0 ∙ α + 0 ∙ β + 0 ∙ γ = 0, отримали 0 = 0 (вірно);
Якщо n - непарне, тоді по співвідношенню (10) f (2n +1) = 2f (n) + γ. Знову підставляючи в це рівність співвідношення (11) отримаємо:
A (2n +1) ∙ α + B (2n +1) ∙ β + C (2n +1) ∙ γ = 2 (A (n) ∙ α + B (n) ∙ β + C (n) ∙ γ) + γ
(A (2n +1) - 2A (n)) ∙ α + (B (2n +1) - 2B (n)) ∙ β + (C (2n +1) - 2C (n) -1) ∙ γ = 0
Тепер підставимо співвідношення (12) в даний рівність і подивимося, чи буде воно виконуватися: n = 2 m + K => 2n +1 = 2 m +1 +2 k +1, тоді A (2n +1) = 2 m +1 , B (2n +1) = 2 m +1 -1 - (2k +1), С (n +1) = 2k +1. Підставляємо: (2 m +1 -2 ∙ 2 m) ∙ α + + (2 m +1-2-2k-2 (2 m-1-k)) ∙ β + (2k +1-2k-1) ∙ γ = 0 0 ∙ α + 0 ∙ β + 0 ∙ γ = 0, отримали 0 = 0 (вірно).
Таким чином, ми показали, що співвідношення (11) і (12) вірні.
Вище було показано, що J - рекурентність має рішення в двійковій запису: J ((b m b m -1 ... b 1 b 0) 2) = (b m -1 ... b 1 b 0 b m) 2, де b m = 1. Можна показати, що й узагальнена рекурентність (10) має схоже рішення.
Запишемо співвідношення (10) наступним чином:
(15)
f (1) = α,
f (2n + j) = 2f (n) + β j при j = 0, 1 і n ≥ 1,
якщо покласти β 0 = β і β 1 = γ. Тоді:
f ((b m b m -1 ... b 1 b 0) 2) = 2f ((b m b m -1 ... b 1) 2) + β b = 4f ((b m b m -1 ... b 2) 2) +2 β b + Β b = = ... = 2 m f ((b m) 2) +2 m -1 β b + ... + 2β b + Β b = 2 m α + 2 m -1 β b + ... + 2β b + Β b .
Якщо ми розширимо систему числення з основою 2 таким чином, що в ній допустимі довільні числа, а не тільки 0 і 1, тоді попередній висновок означає, що
f ((b m b m -1 ... b 1 b 0) 2) = (α β b β b ...   β b β b ) 2 (16)
Отже, зміна системи числення привело нас до компактного рішенням (16) узагальненої рекурентності (15).
Глава 2
Рішення задач
Завдання 1. Те, що всі коні однієї масті, можна довести індукцією за кількістю коней в певному табуні. Ось так:
«Якщо існує тільки один кінь, то вона своєї масті, так що база індукції тривіальна. Для індуктивного переходу припустимо, що існує n коней (з номерами від 1 до n). За індуктивному припущенню коні з номерами від 1 до n -1 однакової масті, і, аналогічно, коні з номерами від 2 до n мають однакову масть. Але коні посередині з номерами від 2 до n -1 не можуть змінювати колір у залежності від того, як вони згруповані, - це коні, а не хамелеони. Тому в силу транзитивності коні з номерами від 1 до n також повинні бути однакової масті. Таким чином, всі n коней однакової масті. Що й треба було довести ».
Чи є помилка в наведеному міркуванні і, яка саме?
Рішення. Помилка в даному міркуванні є, і вона полягає в доказі по індуктивному припущенню. Для доказу того, що n коней мають однакову масть, використовується перетин двох множин від 1 до n-1 і від 2 до n, але для n = 2 цього перетину немає. Тому, якщо є два коні, що мають різну масть, то твердження невірно. Якщо ж будь-які два коні мають однакову масть, то доказ буде вірним для будь-якого n.
Завдання 2. Знайдіть найкоротшу послідовність перекладань, які переміщують башту з n дисків з лівого кілочка А на правий кілочок B, якщо прямий обмін між А і B заборонений. (Кожне перекладання повинне здійснюватися через середній кілочок. Як звичайно, більший диск не можна класти на менший.)
C
B
A
Рішення.


Нехай F n - мінімальне число перекладань, необхідних для переміщення n дисків з одного кілочка на іншій через кілочок С.
Розглянемо крайні випадки: F 0 = 0, F 1 = 2, F 2 = 8, F 3 = 26. Експеримент з трьома дисками дає ключ до загальним правилом переміщення n дисків: спочатку ми переміщаємо (n-1) менших дисків на кілочок B (що вимагає F n -1 перекладань), потім перекладаємо найбільший диск на кілочок С (одне перекладання), потім поміщаємо (n-1) менших дисків на кілочок А (ще F n -1 перекладань), потім перекладаємо найбільший диск на кілочок B (одне перекладання), і, нарешті, поміщаємо (n-1) менших дисків на кілочок B (ще F n -1 перекладань). Таким чином, n дисків (при n> 0) можна перемістити найбільше за 3F n -1 +2 перекладань (тобто досить перекладань): F n ≤ 3F n -1 +2.
Зараз покажемо, що необхідно 3F n -1 +2 перекладань. На двох етапах ми зобов'язані перемістити найбільший диск. Коли ми це робимо, (n-1) менших дисків повинні перебувати на одному кілочку (А або B), а для того щоб зібрати їх разом, буде потрібно, щонайменше, F n -1 перекладань. Найбільший диск можна перекладати й більше одного разу. Отже, F n ≥ 3F n -1 +2.
Ці два нерівності разом з тривіальним рішенням при n = 0 дають рекурентне співвідношення:
F 0 = 0
F n = 3F n -1 +2 при n> 0
Вирішимо дане співвідношення.
Перший спосіб вирішення (вгадування правильного рішення з наступним доказом, що наша здогадка вірна). Обчислимо: F 1 = 2 = 3 1 -1, F 2 = 3 2 -1, F 3 = 3 3 -1. З цього можна зробити припущення, що
F n = 3 n -1 При n ≥ 0.
Доведемо методом математичної індукції по числу n:
1) База: n = 0, F 0 = 3 0 -1 = 1-1 = 0 (вірно);
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n-1). Доведемо для t = n: F n = 3F n -1 +2 3 (3 n -1 -1) + 2 = 3 n - 1.
З пунктів 1 і 2 слід: при n ≥ 0 F n = 3 n - 1.
Другий спосіб вирішення.
До обох частин співвідношення (1) додамо 1:
F 0 +1 = 1,
F n +1 = 3F n -1 +3 при n> 0.
Позначимо U n = F n +1, тоді отримаємо: U 0 = 1, U n = 3U n -1 при n> 0.
Рішенням цієї рекурсії є U n = ; Отже, F n = -1.
У подальшому ми не будемо показувати достатня і необхідна умова у вирішенні подібних завдань, а відразу будемо описувати отримання потрібного рівності. Це пов'язано, по-перше, з тим, що достатня і необхідна умова показується аналогічно тому, як це зроблено в даній задачі, а по-друге, на увазі обмеженості обсягу дипломної роботи.
Завдання 3. Покажіть, що в процесі переміщення башти при обмеженнях з попередньої вправи нам зустрінуться всі допустимі варіанти розміщення n дисків на трьох кілочках.
2
1
Рішення. Занумеруем диски
n-2
n-1


SHAPE \ * MERGEFORMAT
n

Існує (відповідно до умов задачі) тільки три можливих розташування кожного диска на одному з кілочків: або на першому кілочку (А), або на другому кілочку (B), або на третьому кілочку (С). Це будуть перестановки довжини n з трьох елементів. Наприклад, .
Число перестановок довжини k з n елементів: . Отже, для нашого випадку , Тобто - Це всі можливі різні розташування n дисків на трьох кілочках.
У попередній задачі було показано, що найменше число перекладань з кілочка А на кілочок B через кілочок З одно -1. Таким чином, кожен раз перекладаючи диск з одного кілочка на інший, ми отримуємо всі допустимі розташування n дисків на трьох кілочках (тому що ми не перекладаємо один диск з одного кілочка на інший по кілька разів)
Завдання 4. Чи є які-небудь початкова та кінцева конфігурації з n дисків на трьох кілочках, які вимагають більш ніж -1 Перекладань, щоб отримати одну з інший по вихідним правилами Люка?
Рішення. Доведемо методом математичної індукції, що будь-яка початкова та кінцева конфігурації з n дисків на трьох кілочках вимагають не більше ніж -1 Перекладань, щоб отримати одну з інший по вихідним правилами Люка.
1) База: якщо n = 1, то потрібно одне перекладання, тоді 1 ≤ 2 0 -1 (вірно);
2) Індуктивний перехід: нехай для будь-якої початкової та кінцевої конфігурації з n-1 дисків на трьох кілочках потрібно не більше ніж -1 Перекладань. Доведемо для n дисків:
· Якщо початкова та кінцева конфігурації не припускають перекладання самого великого нижнього диска, тоді ми перекладаємо лише n-1 верхніх дисків, а по індуктивному припущенню для цього буде потрібно не більше ніж -1 Перекладань;
· Якщо початкова та кінцева конфігурації припускають перекладання самого великого нижнього диска, тоді ми перекладаємо n-1 верхніх дисків, а по індуктивному припущенню для цього буде достатньо -1 Перекладань (тобто n-1 верхніх дисків розмістили на одному кілочку), потім перекладаємо найбільший диск (одне перекладання), і знову перекладаємо n-1 верхніх дисків, як вимагає кінцева конфігурація (досить -1 Перекладань). Таким чином, отримали, що буде потрібно не більше ніж -1 + 1 + -1 = перекладань.
З усього цього випливає, що не існує початкової та кінцевої конфігурації з n дисків на трьох кілочках вимагає більш ніж -1 Перекладань, щоб отримати одну з інший по вихідним правилами Люка.
Завдання 5. Так звана «діаграма Венна» з трьома пересічними колами часто наводиться для ілюстрації восьми можливих підмножин, пов'язаних із трьома заданими множинами:
А
B
C
Чи можна проілюструвати чотирма пересічними колами шістнадцять можливостей, які виникають у зв'язку з чотирма заданими множинами?
А
B
C
Рішення. Так як три пересічні окружності ілюструють вісім різних підмножин, то для того щоб отримати шістнадцять можливих підмножин треба, щоб четверта окружність перетинала всі вісім множин. Але такого бути не може. Дві довільні кола можуть мати не більше двох точок перетину, тому, проводячи четверту окружність, ми зможемо отримати максимум шість додаткових підмножин. Так як можливо тільки два розташування четвертої окружності щодо трьох даних кіл: 1) четверта окружність перетинає зовнішнє підмножина (рис. 1), 2) четверта окружність лежить усередині трьох пересічних кіл (рис.2).
А
B
C
мал.1 мал.2


Якщо додана окружність перетинає зовнішнє безліч, то вона не зможе перетнути як мінімум два внутрішніх безлічі (залежить від радіусу кола).
Якщо додана окружність лежить усередині трьох пересічних кіл, то вона не перетинає зовнішнє безліч і як мінімум одне внутрішнє безліч.
Таким чином, отримали, що чотирма колами можна проілюструвати максимум 14 (8 +6 = 14) можливих підмножин.
Завдання 6. Деякі з областей, окреслює n прямими на площині, нескінченні, в той час як інші кінцеві. Яке максимально можливе число кінцевих областей?
Рішення. Нехай - Максимальне число можливих кінцевих областей, окреслює n прямими.
Розглянемо окремі випадки (за умови, що n-я пряма не паралельна ніякої іншої прямої (отже, вона перетинає кожну з них), і не проходить через жодну з наявних точок перетину (отже, вона перетинає кожну з прямих у різних місцях)) :







Підпис:
 
Узагальнюючи, приходимо до наступного висновку: нова n-я пряма (при n ≥ 3) перетинає n-1 старих прямих у n-1 різних точках, отже, отримуємо n областей і дві крайні з яких нескінченні. Таким чином, отримали наступне рекурентне співвідношення:
при n ≥ 3

Вирішимо дане співвідношення.

при n ≥ 0.

(Тут L n = + 1 - Максимальне число областей, на які площину ділиться n прямими).
Доведемо отримане рівність методом математичної індукції по числу n:
1) База: n = 0, (Вірно);
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n-1). Доведемо для t = n: = =
=
З пунктів 1 і 2 слід: при n ≥ 0
Завдання 7. Нехай H (n) = J (n +1) - J (n). У силу рівняння (7) (див. теорію) H (2 n) = J (2 n +1) - J (2 n) (2 J (n) +1) - (2 J (n) -1) = 2, a H (2 n +1) = J (2 n +2) - - J (2 n +1) = (2 J (n +1) -1) - (2 J (n) +1) = 2 H ( n) -2 при всіх n ≥ 1. Тому представляється можливим довести індукцією по n, що H (n) = 2 при всіх n. Що тут не вірно?
Рішення. Помилка полягає в тому, що в даному міркуванні хочуть довести по індукції, що H (n) = 2 при всіх n (показали, що це рівність виконується для чисел виду 2n і 2n +1, тому що будь-яке натуральне число можна представити в такому вигляді), але при цьому не перевірили базу індукції (тобто коли n приймає своє найменше значення: n = 1).
H (1) = J (2) - J (1) = 2J (1) -1 - J (1) = 2 ∙ 1-1-1 = 0 H (1) 2 база індукції не виконується, отже рівність H (n) = 2 вірно не при всіх n.
Завдання 8. Вирішіть рекурентне співвідношення
                                   Q 0 = α, Q 1 = β,
                        Q n =               при n> 1.
Прийміть, що Q n ≠ 0 при всіх n ≥ 0.
Рішення. ; ;
;
;
; ;
; .
Отримали: ; ; ; ; .
Узагальнюючи, приходимо до висновку, що дана послідовність періодична: якщо n = 5k + r ( ), Тоді (Для n ≥ 5)
Доведемо методом математичної індукції:
1) База: n = 5 (Вірно, показано вище);
n = 6 (Вірно, показано вище);
n = 7 (Вірно, показано вище);
n = 8 (Вірно, показано вище);
n = 9 (Вірно, показано вище);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1). Доведемо для t = n: n = 5k + 0, тоді ;
· N = 5k + 1, тоді ;
· N = 5k + 2, тоді ;
· N = 5k + 3, тоді ;
· N = 5k + 4, тоді .
З пунктів 1 і 2 слід: для n ≥ 5 .
Відповідь: при всіх n ≥ 0 і k, r Z +.
Завдання 9. Іноді можливе використання «зворотної індукції», тобто доказу від n до n -1, а не навпаки. Наприклад, розглянемо твердження
P (n): , Якщо x 1, x 2, ..., x n ≥ 0
Воно справедливе для n = 2, тому що
(X 1 + x 2) 2 - 4 x 1 x 2 = (x 1 - x 2) 2 ≥ 0.
a) Вважаючи , Доведіть, що P (n) тягне P (n -1) при всякому n> 1.
b) Покажіть, що P (n) і P (2) тягнуть P (2 n).
c) Поясніть, чому звідси випливає справедливість P (n) при всіх n.
Рішення. А) підставимо в P (n):
P (n):
перетворимо праву дужку: =
отримали:
розділимо ліву і праву частини нерівності на (Ці дужки не дорівнює нулю, тому що x 1, x 2, ..., x n> 0 і n> 1, тому що випадок всіх х i = 0 тривіальний, тому ми його не розглядаємо )
отримаємо P (n-1): .
Отже, при P (n) тягне P (n-1) при всякому n> 1.
b) запишемо P (n) для двох кінцевих послідовностей чисел.
P (n): (Для n перших членів)
(Для n членів починаючи з )
перемножимо ці два нерівності, використовуючи властивість нерівностей: якщо 0 <a <b і 0 <c <d, то ac <bd. Отримаємо:
.
Перетворимо праву дужку нерівності, використовуючи твердження Р (2)
P (2):
,
зведемо ліву і праву частини нерівності в n-у ступінь, отримаємо

Таким чином, отримали:
P (2n): .
Отже, P (n) і P (2) тягнуть P (2n).
c) Вище було показано, що з P (n) слід P (n-1), а з P (n) і P (2) випливає P (2n). Отже, ми можемо стверджувати, що P (n) виконується для будь-якого n> 1, тому що P (від непарного числа n) слід з P (від парного числа (n-1)), а P (від парного числа) випливає з P (2) і P (від парного чи непарного числа) і т.д., в кінцевому підсумку приходимо до P (2), а воно виконується.
Наприклад, P (9) випливає з P (8), а P (8) випливає з P (2) і P (4), P (4) випливає з P (2) і P (2), а P (2 ) виконується.
Задача 10. Нехай Q n - мінімальне число перекладань, необхідних для переміщення вежі з n дисків з кілочка А на кілочок B, якщо все перекладання здійснюються за годинниковою стрілкою - тобто з А на B, або з B на інший кілочок, і з іншого кілочка на А. Крім того, нехай R n - Мінімальне число перекладань, необхідних для переміщення вежі з В назад на А при тому ж обмеження. Доведіть, що
(1)
якщо n = 0
якщо n> 0

(2)
якщо n> 0
якщо n = 0
                         
А
З
B
Рішення.
Розглянемо окремі випадки: Q 0 = 0, R 0 = 0; Q 1 = 1, R 1 = 2, Q 2 = 5, R 2 = 7, Q 3 = 15 = = R 2 +1 + R 2, R 3 = 21 = Q 3 +1 + Q 2.
Експеримент з трьома дисками дає ключ до загальним правилом переміщення n дисків c кілочка А на кілочок B за годинниковою стрілкою: спочатку ми переміщаємо (n-1) менших дисків з кілочка А на C, через кілочок B (для цього буде потрібно перекладань, тому що це теж саме якби ми перекладали диски з кілочка B на кілочок А через кілочок С), потім перекладаємо найбільший диск c кілочка A на кілочок B (одне перекладання), потім поміщаємо (n-1) менших дисків з кілочка C на B ( що вимагає перекладань, з тих же міркувань). Таким чином, n дисків (при n> 0) c кілочка A на кілочок B можна перемістити за перекладань. Отримали співвідношення:
якщо n> 0
якщо n = 0

Експеримент з трьома дисками дає ключ і до загальним правилом переміщення n дисків c кілочка B на кілочок A за годинниковою стрілкою: спочатку ми переміщаємо (n-1) менших дисків з кілочка B на А (що вимагає R n -1 перекладань), потім перекладаємо самий великий диск c кілочка B на кілочок С (одне перекладання), потім поміщаємо (n-1) менших дисків з кілочка А на B (що вимагає Q n -1 перекладань), потім перекладаємо найбільший диск c кілочок С на кілочок А ( одне перекладання), і, нарешті, поміщаємо (n-1) менших дисків з кілочка B на кілочок А (ще R n -1 перекладань). Таким чином, n дисків (при n> 0) c кілочка B на кілочок А можна перемістити за перекладань. Отримали співвідношення:
якщо n> 0
якщо n = 0
І якщо ми замість підставимо (Тому що , Показали вище), то отримаємо потрібну нам систему:
Таким чином, отримали, що системи (1) і (2) справедливі.
Задача 11. Подвійна ханойська башта складається з 2 n дисків n різних розмірів - за два диски кожного розміру. Як і у випадку звичайної вежі, за один раз дозволяється перекладати тільки один диск і не можна класти більший диск на менший.
a) Скільки перекладань необхідно для переміщення подвійний вежі з одного кілочка на інший, якщо диски однакових розмірів не відрізняються один від одного?
b) Що якщо в остаточному розташуванні дисків, потрібно відтворити початковий порядок всіх однакових дисків зверху до низу?
Рішення. A) Нехай - Мінімальне число перекладань вежі 2n дисків з одного кілочка на інший. Розглянемо окремі випадки: P 0 = 0, P 2 = 2, P 4 = 6, P 6 = 14. Експеримент з шістьма дисками дає ключ до загальним правилом переміщення 2n дисків: спочатку перемістити (2n-2) менших дисків з одного кілочка на інший (що вимагає перекладань), потім перекладаємо 2 самих великих диска (одне перекладання), потім поміщаємо (2n-2) менших дисків на великі диски (що вимагає перекладань). Таким чином, 2n дисків (при n> 0) можна перемістити за перекладань.
Отримали рекурентне співвідношення:
при n> 0

Вирішимо дане співвідношення. P 0 = 0 = , P 2 = 2 = , P 4 = 6 = , P 6 = = 14 = (Тут T n = 2 n -1 - Мінімальне число перекладань, необхідних для переміщення n дисків з одного кілочка на інший за правилами Люка) гіпотеза: при n ≥ 0
Доведемо методом математичної індукції по числу n, що при n ≥ 0.
1) База: n = 1 (Вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (2n-2). Доведемо для 2n дисків:
З пунктів 1 і 2 випливає, що при n ≥ 0.
b) Нехай - Мінімальне число перекладань вежі з 2n дисків з одного кілочка на інший у вихідному порядку всіх однакових дисків зверху до низу.
Розглянемо окремі випадки: R 0 = 0, R 2 = 3, R 4 = 11. Експеримент з чотирма дисками дає ключ до загальним правилом переміщення 2n дисків у вихідному порядку: спочатку перемістити (2n-2) менших дисків з одного кілочка на інший (що вимагає перекладань), потім перекладаємо два найбільших диска на вільний кілочок (два перекладання; ці диски будуть покладені неправильно), потім перекладаємо (2n-2) менших дисків на вільний кілочок (що вимагає перекладань), потім знову перекладаємо два найбільших диска (два перекладання; ці диски будуть покладені правильно), і, нарешті, перекладаємо (2n-2) менших дисків на великі диски у вихідному порядку (буде потрібно перекладань). Таким чином, 2n дисків (при n> 0) можна перемістити з одного кілочка на інший у вихідному порядку всіх однакових дисків зверху до низу за перекладань.
Отримали рекурентне співвідношення:
при n> 0
(*)
Вирішимо дане співвідношення. R 2 = 3 = 2P 2 -1, R 4 = 11 = 2P 4 -1, R 6 = 27 = 2P 6 -1 гіпотеза: при n> 0.
Доведемо методом математичної індукції по числу n, що при n> 0.
1) База: n = 1 (Вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (2n-2). Доведемо для 2n дисків:
З пунктів 1 і 2 випливає, що при n> 0.
при n> 0,
Ще можна помітити наступне: тому , Отже , То, підставляючи це рівність у співвідношення (*) отримаємо рекурентне співвідношення:
має те ж саме рішення
Задача 12. Давайте ще узагальнимо завдання 11а, припускаючи, що є n різних розмірів дисків і рівно m k дисків розміру k. Визначте найменше число A (m 1, m 2, ..., m n) перекладань дисків, необхідних для переміщення такої вежі, якщо вважати диски однакових розмірів нерозрізненними.
Рішення. Для того, що перекласти вежу, що складається з n різних розмірів дисків, серед яких рівно m k дисків розміру k, потрібно наступне число перекладань:
при n> 0,

де m n - це кількість найбільших нижніх дисків.
Вирішимо дане рекурентне співвідношення.
A (m 1) = 2A (0) + m 1 = m 1;
A (m 1, m 2) = 2A (m 1) + m 2 = 2 січня ∙ m 1 + m 2;
A (m 1, m 2, m 3) = 2A (m 1, m 2) + m 3 = 2 лютого ∙ m 1 +2 1 ∙ m 2 + m 3;
A (m 1, m 2, m 3, m 4) = 2A (m 1, m 2, m 3) + m 4 = 3 лютого ∙ m 1 +2 +2 ∙ m 2 +2 +1 ∙ m 3 + m 4 .
Звідси можна висунути гіпотезу, що
при n> 0
A (m 1, m 2, ..., m n) =
Доведемо методом математичної індукції по числу n.
1) База: n = 1 A (m 1) = 2 0 ∙ m 1 = m 1 (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1). Доведемо для t = n: = 2 ∙ ( )
=
З 1 і 2 випливає, що A (m 1, m 2, ..., m n) =
при n> 0.
Задача 13. На яку максимально можливу кількість областей площину ділиться n зигзагоподібні лініями, кожна з яких складається з двох паралельних напівнескінченних прямих, з'єднаних прямолінійним відрізком?
Рішення. Нехай - Це максимальне число областей, на які площину ділиться n зигзагоподібними лініями. Розглянемо окремі випадки:



(Тут L n = + 1 - Максимальне число областей, на які площину ділиться n прямими)
1
2
3
4
5
6
З цих окремих випадків можна бачити, що зигзагоподібна лінія подібна трьом прямим з тією лише відмінністю, що області зливаються, якщо «три» прямі не продовжувати після їх перетину:
Області 1, 2, 6 і 3, 4, 5, які були б розділені за наявності трьох прямих, перетворюються в єдину область у випадку однієї зигзагоподібної лінії, тобто ми втрачаємо чотири області. Так само у нас є дві паралельні прямі, отже, ми втрачаємо ще одну область. Таким чином, якщо привести все в належний порядок, то все зигзагоподібні лінії повинні перетинатися між собою і точки зламів повинні лежати «по той бік» перетинів з іншими лініями, і ми втрачаємо тільки п'ять областей на одну лінію. Таким чином,
.
Дану задачу можна вирішити і по іншому, якщо зауважити, що зигзаг можна розглядати як «пряму», і відрізок, що з'єднує дві напівпрямі, може бути як завгодно довгим. Тоді ця задача аналогічна задачі про знаходження максимального числа L n областей, на які площину ділиться n прямими (дві прямі мають одну точку перетину). У нашому випадку дві зигзагоподібні лінії мають дев'ять точок перетину.
З іншого боку, дві зигзагоподібні лінії подібні шести прямим з тією лише відмінністю, що області зливаються, якщо «шість» прямих не продовжувати після їх перетину,
Ці шість прямих утворюють 20 областей, отже, при перетині двох зигзагоподібних ліній ми втрачаємо вісім областей.
Таким чином, отримуємо рекурентне співвідношення:
при n> 0

Вирішимо дане співвідношення. +9 N-
-8 =
+9 ∙ (n-1) -8 +9 n-8 =
= при n ≥ 0.
Доведемо отримане рівність методом математичної індукції.
1) База: n = 0, (Вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1). Доведемо для t = n: = +9 N-7 = .
З пунктів 1 і 2 слід: при n> 0 .
Завдання 14. На яку максимальну кількість частин можна розділити головку сиру за допомогою п'яти плоских розрізів? (Головка сиру повинна залишатися у вихідному положенні, поки ви її ріжете, і кожному розрізу повинна відповідати деяка площину в тривимірному просторі.) Знайдіть рекурентне співвідношення для Р n - максимального числа тривимірних областей, на яке може бути розбите простір n довільно розташованими площинами.
Рішення. Спочатку знайдемо рекурентне співвідношення для Р n, а потім за допомогою цього співвідношення визначимо, на скільки частин можна розділити головку сиру за допомогою п'яти плоских розрізів (голівка сиру є обмеженим простором).
Отже, розглянемо окремі випадки: Р 1 = 2, Р 2 = 4, Р 3 = 4 +4 = 8, Р 4 = 8 +7 ​​= 15. Експеримент показує, що дана задача аналогічна задачі про знаходження максимального числа L n областей, на які площину ділиться n прямими (L n = L n -1 + n), але тільки з тією відмінністю, що справа йде в просторі. Дві довільні площини перетинаються по єдиною прямою, і для того, щоб отримати максимальне число тривимірних областей треба, щоб кожна нова проведена площина не була паралельна ніякої іншій площині (отже, вона перетинає кожну з них), і не проходила через жодну з наявних прямих перетину (отже, вона перетинає кожну з площин по різним прямим). Таким чином, проводячи нову n-у площину, ми до старих областям додаємо стільки тривимірних областей, що утвориться областей на n-ій площині утворених прямий перетину цієї площини з усіма іншими площинами. Тому рекурентне співвідношення має вигляд:


Отже, головку сиру можна розділити за допомогою п'яти плоских розрізів не більше ніж на 26 частин.
Задача 15. У Йосипа був друг, якого він врятував, поставивши на передостаннє рятівне місце. Чому дорівнює F (n) - ​​номер передостаннього вижив, якщо екзекуції підлягає кожен другий?
Рішення. Припустимо, що спочатку є 2n людей. Після першого обходу ми залишаємося з номерами: 1, 3, 5, 7, ..., 2n-3, 2n-1. Наступний обхід буде починатися з номеру 3. Це те ж саме, якби ми починали з n людей, за винятком того, що номер кожного вцілілого подвоюється і зменшується на 1. Тим самим
F (2n) = 2 ∙ F (n) - 1 при n> 1
Тепер подивимося, що буде у випадку, коли є 2n +1 людей. Після першого обходу жертва з номером 1 знищується відразу після жертви з номером 2n, і ми залишаємося з номерами: 3, 5, 7, ..., 2n-1, 2n +1. Отримали майже первісну ситуацію з n людьми, але на цей раз номери уцілілих подвоюються і збільшуються на 1. Таким чином,
F (2n +1) = 2 ∙ F (n) + 1 при n> 1
Об'єднання отриманих рівностей дає рекурентне співвідношення, яке визначає F (n) для n> 3, тому що F (1) не визначено:
(**)
F (2n) = 2 ∙ F (n) - 1 при n> 3
F (2n +1) = 2 ∙ F (n) + 1 при n> 3
Вирішимо дане рекурентне співвідношення. Складемо таблицю перших значень F (n) і J (n) (тут J (n) - ​​номер останнього вцілілого, коли з кола виключається кожен другий), і нехай n має вигляд: n = 2 m + k, де 2 m - найбільша ступінь 2, не перевершує n (m> 0), а k - те, що залишається (0 ≤ k <2 m):
n
F (n) = J (n) +2 2
F (n) = J (n) -2 +3
2 Березня
F (n) = J (n) +2 1
F (n) = J (n) -2 2
2 Січень
2 лютого
1
2 Березня
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18
F (n)
-
2 Січень
3 5 1 3
5 7 9 11 1 3 5 7
11 вересня 1913
J (n)
1
3 січня
1 3 5 7
1 3 5 7 9 11 13 15
1 3 5
Якщо згрупувати значення n за ступенями двійки (у таблиці ці групи відокремлені суцільними вертикальними лініями), то в кожній групі F (n) є ще дві групи (див. таблицю). Тому рішення рекурентного співвідношення повинне мати вигляд для n> 1:
якщо 0 ≤ k <2 m -1
якщо 2 m -1 ≤ k <2 m

Доведемо отримане співвідношення методом математичної індукції по числу m.
1) База: n = 2, тоді m = 1, k = 0
F (2 1 +0) = J (2) + 2 0 = 1 + 1 = 2 (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (m - 1). Доведемо для t = m:
a) якщо m> 0 і 2 m + k = 2n, то k - четноe і
F (2 m + k) = F (2 ∙ (2 m -1 + )) 2 ∙ F (2 m -1 + ) - 1 =
якщо 0 ≤ k <2 m -1
якщо 2 m -1 ≤ k <2 m
= =
якщо 0 ≤ k <2 m -1
якщо 2 m -1 ≤ k <2 m
=
b) якщо m> 0 і 2 m + k = 2n +1, то k - непарне (тобто k = 2t +1) і
F (2 m + k) = F (2 m + (2t +1)) = F (2 (2 m-1 + t) +1) 2 ∙ F (2 m-1 + t) + 1
якщо 2 m -1 ≤ k <2 m
якщо 0 ≤ k <2 m -1
= =
2 m -1 ≤ k <2 m
0 ≤ k <2 m -1
= = =
З пунктів 1 і 2 слід вірність доказуваного рівності.
Завдання 16. Позначимо через W n найменше число перекладань, необхідних для переміщення вежі з n дисків з одного кілочка на інший, коли є не три, а чотири кілочка. Покажіть, що
                        при n> 0
(Тут T n = 2 n -1 - Число перекладань в звичайному випадку трьох кілочків.)
Рішення. Подивимося на числа і , Вони відрізняються на n, тому що . Тому, щоб перекласти дисків з одного кілочка на інший, маючи в розпорядженні чотири кілочка, треба: спочатку перемістити менших дисків на будь-який з кілочків, використовуючи всі чотири кілочка (що вимагає перекладань), потім перекладаємо n нижніх, найбільших дисків, використовуючи тільки три кілочка, тому що більший диск не можна поміщати на менший диск (буде потрібно перекладань) і, нарешті, поміщаємо менших дисків назад на найбільші диски, використовуючи знову чотири кілочка (ще перекладань). Таким чином, для переміщення дисків (при n> 0) досить наступне число перекладань: .
Завдання 17. Припустимо, що в коло поставлено 2 n людина, перші n з яких - «славні хлопці», а n останніх - «бридкі хлопці». Покажіть, що завжди знайдеться ціле m (залежне від n), таке, що якщо, рухаючись по колу, ми караємо кожного m-го, то першими будуть покарані всі бридкі хлопці. (Приміром, при n = 3 можна взяти m = 5, а при n = 4 взяти m = 30.)
Рішення. Рухаючись по колу, ми повинні покарати всіх «бридких хлопців», тому повинні викреслювати кімнати від n +1 до 2n. Якщо ми викреслимо в перший раз номер 2n, то в колі залишиться 2n-1 людина, і наступне коло почнемо з номера 1 (для того, щоб викреслити номер 2n ми повинні обійти ціле число кругів). Якщо другий раз ми викреслимо номер 2n-1, то в колі залишиться 2n-2 чоловік, і знову, наступне коло будемо починати з номера 1 (для того, щоб викреслити номер 2n-1 ми знову повинні обійти ціле число кругів). І так далі, будемо по черзі викреслювати номери 2n-2, 2n-3, ..., n +1 (а для цього ми повинні щоразу між викреслювання «бридких хлопців» проходити ціле число кіл) і щоразу після викреслювання кількість осіб зменшується на одиницю , і нове коло будемо починати з номера 1. Тому треба взяти таке число m, яке ділилося б на 2n, 2n-1, ..., n +1. Наприклад, можна взяти m - найменше спільне кратне цих чисел.
Висновок
У даній роботі поставлені цілі були досягнуті. Однак тема далеко не вичерпана. Є перспективи у вигляді узагальнення або зміни умов деяких завдань, і їх подальшого вирішення. Наприклад, завдання про «діаграмах Венна» можна узагальнити, розглядаючи не окружність, а овали або опуклі багатокутники, і для них визначити, яку максимальну кількість можливих підмножин з їх допомогою можна проілюструвати. Задачу Йосипа Флавія можна змінити, наприклад, так: Йосип займає конкретне j-е місце і може назвати фатальний параметр q, після чого знищується кожен q-а людина, чи завжди він зможе врятуватися?
У роботі не розглянуто репертуарний метод рішення узагальнених рекурентності з певним числом параметрів (тому що не стояло такого завдання). Репертуарним методом можна, наприклад, вирішити узагальнену рекурентність з чотирма параметрами:
при j = 0, 1 і n ≥ 1

Бібліографічний список
1. Грехем, Р. Конкретна математика. Підстава інформатики. [Текст] / Р. Грехем, Д. Кнут, О. Паташнік. Пер. з англ. - М.: Світ, 1998. - С. 17-37.
2. Маркушевич А. І. Зворотні послідовності. Популярні лекції з математики [Текст]. - М.: Наука, 1983.
3. Мантуров О. В. Математика в поняттях, визначеннях і термінах. Ч.2 [Текст] / О. В. Мантуров, Ю. К. Солнцев, Ю. І. Соркін, Н. Г. Федін; Під. ред. Л. В. Сабініна. - М.: Просвещение, 1982. - С. 207-208.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Диплом
206.2кб. | скачати


Схожі роботи:
Зворотні послідовності
Зворотні зв`язки в живих системах
Інтерфейси зворотні виклики внутрішні класи
Зворотні матриці над кільцем цілих чисел
Задачі з Хімії
Комбінаторні задачі
Задачі з геометрії
Аpифметичнi задачі
Основні задачі аудиту
© Усі права захищені
написати до нас