td valign=top>
14
16
17
19
21
22
24
25
27
29
[(3 +) n/2]
2
5
7
10
13
15
18
20
23
26
28
31
34
36
39
41
44
47
Вправа 3
Використовуючи формули
і
побудуйте послідовності, які заповнюють весь натуральний ряд без пропусків і перекриттів
В
,, ...
...,, ...
В
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
В В
Де
Вправа 4
Знайти явні формули для зростаючих послідовностей і, що заповнюють натуральний ряд без пропусків і перекриттів і задовольняють співвідношенню при всіх n = 1,2,3 ...
В В
Отже, явні формули для послідовностей доведені.
В§ 4. Геометрична інтерпретація
Дивно просте і наочний доказ теореми з В§ 1 отримуємо, якщо розглянемо геометричну інтерпретацію.
В
Нехай, як і раніше, О± і ОІ - позитивні ірраціональні числа. br/>
Причому . Тоді, звідки. br/>
Намалюємо на аркуші паперу, як на координатної площині пряму l, задану рівнянням у = (О±-1) x, яке можна записати так само у вигляді x = (ОІ-1) y.
Занумеруем поспіль всі клітини, які перетинають l, починаючи з нульової клітини, якої належить початок координат (для ... взято
О± =)
Якщо ми позначимо числа, що стоять над лінією за a-числа, а під лінією за b - числа то вийдуть дві послідовності, про які ми говорили в В§ 1.
Оскільки число О± ірраціонально, пряма l не проходить через вузли сітки. Значить, l входить до чергову клітку або ліворуч, перетинаючи вертикальну лінію сітки, або знизу, перетинаючи горизонтальну лінію. p> Якщо l увійшла в клітку ліворуч та перетнула при цьому вертикаль х = n, то номер клітини, в яку при цьому увійшла пряма дорівнює n + [(О±-1) n] = [О±n].
Якщо ж пряма l перетнула знизу горизонталь y = m, то номер відповідної клітини дорівнює [(ОІ-1) m] + m = [ОІm]. br/>
В§ 5. Деякі програми. Паліндроми
Позначимо натуральні числа належать послідовності a буквою А, а належать послідовності - буквою В.построім послідовність.
p> Розглянувши послідовність уважніше, помітимо, що її можна розділити на паліндроми.
Визначення: Паліндроми (перевертиш) - це слово, яке виглядає однаково при читанні слова як зліва направо, так і справа наліво.
Приклади:
Курінь, ротор або АВВАВАВВА.
Розглянемо задачу, пов'язану з паліндромами (аналогічне завдання вирішував у своїй статті Акуліч)
З букв А і В складено 2010-буквене слово. Доведіть, що його можна розбити менш ніж на 900 більш коротких слів, кожне з яких є паліндромом.
Візьмемо довільне 2010-буквене слово і розіб'ємо його спочатку на 5-буквені - їх буде всього 402. Кожне з цих 5-буквених слів, у свою чергу, може бути складено не більше ніж з двох паліндромів. Тому довільне 2010-буквене слово можна скласти не більше ніж з 804 паліндромів, тобто менше ніж з 900, що й потрібно було довести. p> Щоб вирішувати такі завдання в загальному вигляді, введемо функцію f (n). Через неї позначимо таке найменше натуральне число, що всяке слово довжиною n, складене з букв А і В може бути розбите не більше ніж на f (n) паліндромів.
Вправа 1
Придумайте слово з букв А і В яке не можна розбити менш ніж на 3 паліндрома, але яке після приписування до нього праворуч або ліворуч будь-який з букв А і В можна розбити на два паліндрома.
АВААВВ + А
Виявилося, що завдання можна вирішити в загальному вигляді. Введемо функцію f (n). p> Через f (n) позначимо таке найменше число, що всяке слово довжиною n, що складається з букв А і В, може бути розбите не більше ніж на f (n) паліндромів.
Приклад:
Знайдемо f (6). Всього шестібуквенних немов оскільки літери А і В рівноправні досить розглянути тільки слова починаються на букву А
АААААА
ААААА + В
ААА + АВА
АААА + ВВ
А + аава
ААА + ВАВ
АА + АВВА
ААА + ВВВ
аава + А
АА + ВААВ
А + ава...
