Федеральне агентство з освіти
Державна освітня установа вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Зворотні задачі
Виконала:
студентка 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 дають рекурентне співвідношення:
Т 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 прямими?
Знову почнемо з розгляду крайніх випадків. SHAPE \ * MERGEFORMAT
Експеримент з трьома прямими показує, що додана третя пряма може розсікати найбільше три старих області незалежно від того, як розташовані перші дві прямі:
Таким чином, 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
А тепер невелика варіація на тему прямих на площині: припустимо, що замість прямих ліній ми використовуємо ламані лінії, кожна з яких представлена одним «зігом». Яке максимальне число Z n областей, на які площину ділиться n такими ламаними лініями?
Окремі випадки:
Ламана лінія подібна двом прямим з тією лише відмінністю, що області зливаються, якщо «дві» прямі не продовжувати після їх перетину:
Області 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).
Державна освітня установа вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Зворотні задачі
Виконала:
студентка 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 =
I m =
8). Інтеграл I n =
I n =
9). Формула довжини сторони при подвоєнні числа сторін правильного вписаного багатокутника
a n =
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 дають рекурентне співвідношення:
|
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
З пунктів 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 прямими?
|
2 |
L 1 = 2 |
2 |
1 |
3 |
4 |
L 2 = 4 |
1 |
L 0 = 1 |
Експеримент з трьома прямими показує, що додана третя пряма може розсікати найбільше три старих області незалежно від того, як розташовані перші дві прямі:
1а |
1b |
2 |
4a |
4b |
3a |
3b |
Узагальнюючи, приходимо до наступного висновку: нова n-я пряма (при n> 0) збільшує число областей на k ó коли розсікає k старих областей ó коли перетинає колишні прямі в (k-1) різних місцях. Дві прямі можуть перетинатися не більше ніж в одній точці. Тому нова пряма може перетинати (n-1) старих прямих не більше ніж в (n-1) різних точках, і ми повинні мати k ≤ n. Встановлена верхня межа:
L n ≤ L n -1 + n при n> 0
У цій формулі можна досягти рівності наступним чином: проводимо n-у пряму так, щоб вона не була паралельна ніякої іншої прямої (отже, вона перетинає кожну з них) і так, щоб вона не проходила через жодну з наявних точок перетину (отже, вона перетинає кожну з прямих у різних місцях). Тому рекурентне співвідношення має вигляд:
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, L 0 =
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n-1). Доведемо для t = n:
L n = L n -1 + n
З пунктів 1 і 2 слід: при n ≥ 0 L n =
|
|
2 |
1 |
1 |
4 |
6 |
5 |
7 |
|
|
Ламана лінія подібна двом прямим з тією лише відмінністю, що області зливаються, якщо «дві» прямі не продовжувати після їх перетину:
1 |
4 |
3 |
2 |
Z n = L 2 n - 2n =
Порівнюючи рішення в замкненій формі (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 | 1 | 2 | 3 | 4 | 5 | 6 |
J (n) | 1 | 1 | 3 | 1 | 3 | 5 |
Отже, вирішимо поставлену задачу.
Припустимо, що спочатку є 2n людей. Після першого обходу ми залишаємося з номерами:
1 |
33 |
5 |
7 |
.... |
2n-3 |
2n-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) -
Тепер подивимося, що буде у випадку, коли є 2n +1 людей. Після першого обходу жертва з номером 1 знищується відразу після жертви з номером 2n, і ми залишаємося з номерами:
3 |
5 |
7 |
9 |
.... |
2n-1 |
2n +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 |
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 +
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)
Інший спосіб докази, коли k - непарне:
Можна помітити, що J (2n +1) - J (2n) = 2, тоді J (2 m + k) = 2 + J (2 m + (K--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 і більше разів завжди буде породжувати набір з одних одиниць зі значенням
|
Тепер давайте повернемося до нашого початкового припущенням, що J (n) =
1) База: k = 1, 4-1 = 3, три ділиться на три (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (k-1), тобто (4 t -1) ділиться на три. Доведемо для t = k:
4 k - 1 = 4 (4 k -1 - 1) + 3
Таким чином, показали, що для m - непарного (2 m - 2) ділиться на 3.
Тепер покажемо, що при m - парному (2 m - 2) не ділиться на 3. Припустимо гидке: нехай (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:
|
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))
b) якщо n - непарне, тоді k теж непарній, тобто k = 2t +1, і f (n) = = f (2 m +2 t +1) = f (2 (2 m-1 + t) +1)
З пунктів 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
Якщо 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
Таким чином, ми показали, що співвідношення (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) наступним чином:
|
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
Якщо ми розширимо систему числення з основою 2 таким чином, що в ній допустимі довільні числа, а не тільки 0 і 1, тоді попередній висновок означає, що
f ((b m b m -1 ... b 1 b 0) 2) = (α β b
Отже, зміна системи числення привело нас до компактного рішенням (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 заборонений. (Кожне перекладання повинне здійснюватися через середній кілочок. Як звичайно, більший диск не можна класти на менший.)
|
|
|
Нехай 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
З пунктів 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 =
У подальшому ми не будемо показувати достатня і необхідна умова у вирішенні подібних завдань, а відразу будемо описувати отримання потрібного рівності. Це пов'язано, по-перше, з тим, що достатня і необхідна умова показується аналогічно тому, як це зроблено в даній задачі, а по-друге, на увазі обмеженості обсягу дипломної роботи.
Завдання 3. Покажіть, що в процесі переміщення башти при обмеженнях з попередньої вправи нам зустрінуться всі допустимі варіанти розміщення n дисків на трьох кілочках.
|
|
n-2 |
n-1 |
SHAPE \ * MERGEFORMAT
n |
Існує (відповідно до умов задачі) тільки три можливих розташування кожного диска на одному з кілочків: або на першому кілочку (А), або на другому кілочку (B), або на третьому кілочку (С). Це будуть перестановки довжини n з трьох елементів. Наприклад,
У попередній задачі було показано, що найменше число перекладань з кілочка А на кілочок B через кілочок З одно
Завдання 4. Чи є які-небудь початкова та кінцева конфігурації з n дисків на трьох кілочках, які вимагають більш ніж
Рішення. Доведемо методом математичної індукції, що будь-яка початкова та кінцева конфігурації з n дисків на трьох кілочках вимагають не більше ніж
1) База: якщо n = 1, то потрібно одне перекладання, тоді 1 ≤ 2 0 -1 (вірно);
2) Індуктивний перехід: нехай для будь-якої початкової та кінцевої конфігурації з n-1 дисків на трьох кілочках потрібно не більше ніж
· Якщо початкова та кінцева конфігурації не припускають перекладання самого великого нижнього диска, тоді ми перекладаємо лише n-1 верхніх дисків, а по індуктивному припущенню для цього буде потрібно не більше ніж
· Якщо початкова та кінцева конфігурації припускають перекладання самого великого нижнього диска, тоді ми перекладаємо n-1 верхніх дисків, а по індуктивному припущенню для цього буде достатньо
З усього цього випливає, що не існує початкової та кінцевої конфігурації з n дисків на трьох кілочках вимагає більш ніж
Завдання 5. Так звана «діаграма Венна» з трьома пересічними колами часто наводиться для ілюстрації восьми можливих підмножин, пов'язаних із трьома заданими множинами:
А |
B |
C |
А |
B |
C |
А |
B |
C |
Якщо додана окружність перетинає зовнішнє безліч, то вона не зможе перетнути як мінімум два внутрішніх безлічі (залежить від радіусу кола).
Якщо додана окружність лежить усередині трьох пересічних кіл, то вона не перетинає зовнішнє безліч і як мінімум одне внутрішнє безліч.
Таким чином, отримали, що чотирма колами можна проілюструвати максимум 14 (8 +6 = 14) можливих підмножин.
Завдання 6. Деякі з областей, окреслює n прямими на площині, нескінченні, в той час як інші кінцеві. Яке максимально можливе число кінцевих областей?
Рішення. Нехай
Розглянемо окремі випадки (за умови, що n-я пряма не паралельна ніякої іншої прямої (отже, вона перетинає кожну з них), і не проходить через жодну з наявних точок перетину (отже, вона перетинає кожну з прямих у різних місцях)) :
Узагальнюючи, приходимо до наступного висновку: нова n-я пряма (при n ≥ 3) перетинає n-1 старих прямих у n-1 різних точках, отже, отримуємо n областей і дві крайні з яких нескінченні. Таким чином, отримали наступне рекурентне співвідношення:
|
Вирішимо дане співвідношення.
|
(Тут L 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)
Рішення. Помилка полягає в тому, що в даному міркуванні хочуть довести по індукції, що 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
Завдання 8. Вирішіть рекурентне співвідношення
Q 0 = α, Q 1 = β,
Q n =
Прийміть, що Q n ≠ 0 при всіх n ≥ 0.
Рішення.
Отримали:
Узагальнюючи, приходимо до висновку, що дана послідовність періодична: якщо n = 5k + r (
Доведемо методом математичної індукції:
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
Відповідь:
Завдання 9. Іноді можливе використання «зворотної індукції», тобто доказу від n до n -1, а не навпаки. Наприклад, розглянемо твердження
P (n):
Воно справедливе для n = 2, тому що
(X 1 + x 2) 2 - 4 x 1 x 2 = (x 1 - x 2) 2 ≥ 0.
a) Вважаючи
b) Покажіть, що P (n) і P (2) тягнуть P (2 n).
c) Поясніть, чому звідси випливає справедливість P (n) при всіх n.
Рішення. А) підставимо
P (n):
перетворимо праву дужку:
отримали:
розділимо ліву і праву частини нерівності на
отримаємо P (n-1):
Отже, при
b) запишемо P (n) для двох кінцевих послідовностей чисел.
P (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 - Мінімальне число перекладань, необхідних для переміщення вежі з В назад на А при тому ж обмеження. Доведіть, що
|
|
|
|
|
|
А |
З |
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 (для цього буде потрібно
|
|
Експеримент з трьома дисками дає ключ і до загальним правилом переміщення 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 на кілочок А можна перемістити за
|
|
Таким чином, отримали, що системи (1) і (2) справедливі.
Задача 11. Подвійна ханойська башта складається з 2 n дисків n різних розмірів - за два диски кожного розміру. Як і у випадку звичайної вежі, за один раз дозволяється перекладати тільки один диск і не можна класти більший диск на менший.
a) Скільки перекладань необхідно для переміщення подвійний вежі з одного кілочка на інший, якщо диски однакових розмірів не відрізняються один від одного?
b) Що якщо в остаточному розташуванні дисків, потрібно відтворити початковий порядок всіх однакових дисків зверху до низу?
Рішення. A) Нехай
Отримали рекурентне співвідношення:
|
Вирішимо дане співвідношення. P 0 = 0 =
Доведемо методом математичної індукції по числу n, що
1) База: n = 1
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (2n-2). Доведемо для 2n дисків:
З пунктів 1 і 2 випливає, що
b) Нехай
Розглянемо окремі випадки: R 0 = 0, R 2 = 3, R 4 = 11. Експеримент з чотирма дисками дає ключ до загальним правилом переміщення 2n дисків у вихідному порядку: спочатку перемістити (2n-2) менших дисків з одного кілочка на інший (що вимагає
Отримали рекурентне співвідношення:
|
Вирішимо дане співвідношення. R 2 = 3 = 2P 2 -1, R 4 = 11 = 2P 4 -1, R 6 = 27 = 2P 6 -1
Доведемо методом математичної індукції по числу n, що
1) База: n = 1
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (2n-2). Доведемо для 2n дисків:
З пунктів 1 і 2 випливає, що
|
має те ж саме рішення
Задача 12. Давайте ще узагальнимо завдання 11а, припускаючи, що є n різних розмірів дисків і рівно m k дисків розміру k. Визначте найменше число A (m 1, m 2, ..., m n) перекладань дисків, необхідних для переміщення такої вежі, якщо вважати диски однакових розмірів нерозрізненними.
Рішення. Для того, що перекласти вежу, що складається з n різних розмірів дисків, серед яких рівно m k дисків розміру k, потрібно наступне число перекладань:
|
де 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.
1) База: n = 1 A (m 1) = 2 0 ∙ m 1 = m 1 (вірно);
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1). Доведемо для t = n:
=
З 1 і 2 випливає, що A (m 1, m 2, ..., m n) =
при n> 0.
Задача 13. На яку максимально можливу кількість областей площину ділиться n зигзагоподібні лініями, кожна з яких складається з двох паралельних напівнескінченних прямих, з'єднаних прямолінійним відрізком?
Рішення. Нехай
(Тут L n =
1 |
2 |
3 |
4 |
5 |
6 |
Області 1, 2, 6 і 3, 4, 5, які були б розділені за наявності трьох прямих, перетворюються в єдину область у випадку однієї зигзагоподібної лінії, тобто ми втрачаємо чотири області. Так само у нас є дві паралельні прямі, отже, ми втрачаємо ще одну область. Таким чином, якщо привести все в належний порядок, то все зигзагоподібні лінії повинні перетинатися між собою і точки зламів повинні лежати «по той бік» перетинів з іншими лініями, і ми втрачаємо тільки п'ять областей на одну лінію. Таким чином,
Дану задачу можна вирішити і по іншому, якщо зауважити, що зигзаг можна розглядати як «пряму», і відрізок, що з'єднує дві напівпрямі, може бути як завгодно довгим. Тоді ця задача аналогічна задачі про знаходження максимального числа L n областей, на які площину ділиться n прямими (дві прямі мають одну точку перетину). У нашому випадку дві зигзагоподібні лінії мають дев'ять точок перетину.
З іншого боку, дві зигзагоподібні лінії подібні шести прямим з тією лише відмінністю, що області зливаються, якщо «шість» прямих не продовжувати після їх перетину,
Ці шість прямих утворюють 20 областей, отже, при перетині двох зигзагоподібних ліній ми втрачаємо вісім областей.
Таким чином, отримуємо рекурентне співвідношення:
|
Вирішимо дане співвідношення.
-8 =
+9 ∙ (n-1) -8 +9 n-8 =
=
Доведемо отримане рівність методом математичної індукції.
1) База: n = 0,
2) Індуктивний перехід: нехай вірно для всіх чисел t ≤ (n-1). Доведемо для t = n:
З пунктів 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-у площину, ми до старих
Отже, головку сиру можна розділити за допомогою п'яти плоских розрізів не більше ніж на 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 +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 |
| 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 |
якщо 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 +
якщо 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)
|
|
|
|
З пунктів 1 і 2 слід вірність доказуваного рівності.
Завдання 16. Позначимо через W n найменше число перекладань, необхідних для переміщення вежі з n дисків з одного кілочка на інший, коли є не три, а чотири кілочка. Покажіть, що
(Тут T n = 2 n -1 - Число перекладань в звичайному випадку трьох кілочків.)
Рішення. Подивимося на числа
Завдання 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-а людина, чи завжди він зможе врятуватися?
У роботі не розглянуто репертуарний метод рішення узагальнених рекурентності з певним числом параметрів (тому що не стояло такого завдання). Репертуарним методом можна, наприклад, вирішити узагальнену рекурентність з чотирма параметрами:
|
Бібліографічний список
1. Грехем, Р. Конкретна математика. Підстава інформатики. [Текст] / Р. Грехем, Д. Кнут, О. Паташнік. Пер. з англ. - М.: Світ, 1998. - С. 17-37.
2. Маркушевич А. І. Зворотні послідовності. Популярні лекції з математики [Текст]. - М.: Наука, 1983.
3. Мантуров О. В. Математика в поняттях, визначеннях і термінах. Ч.2 [Текст] / О. В. Мантуров, Ю. К. Солнцев, Ю. І. Соркін, Н. Г. Федін; Під. ред. Л. В. Сабініна. - М.: Просвещение, 1982. - С. 207-208.
Цей текст може містити помилки.
Математика | Диплом
Схожі роботи:
Зворотні послідовності
Зворотні зв`язки в живих системах
Інтерфейси зворотні виклики внутрішні класи
Зворотні матриці над кільцем цілих чисел
Задачі з Хімії
Комбінаторні задачі
Задачі з геометрії
Аpифметичнi задачі
Основні задачі аудиту