Разобьём всех го­стей на упо­ря­до­чен­ные трой­ки; пер­во­му че­ло­ве­ку из трой­ки на­де­нем ци­линдр с бук­вой A, вто­ро­му  — с бук­вой Б, тре­тье­му  — с бук­вой В. Для этого по­ста­вим го­стей в ше­рен­гу (это можно сде­лать (3n)! спо­со­ба­ми), пер­вых трёх объ­еди­ним в одну трой­ку, вто­рых трёх  — в дру­гую и т. д. По­сколь­ку трой­ки можно пе­ре­став­лять внут­ри ше­рен­ги и по­лу­чать то же самое раз­би­е­ние на трой­ки, то каж­дое раз­би­е­ние по­счи­та­но n! раз. Таким об­ра­зом, ко­ли­че­ство спо­со­бов раз­бить го­стей на упо­ря­до­чен­ные трой­ки равно

Те­перь для того, чтобы раз­бить го­стей на хо­ро­во­ды, до­ста­точ­но раз­бить на хо­ро­во­ды пер­вых n че­ло­век из своих троек (эти хо­ро­во­ды могут со­сто­ять из од­но­го че­ло­ве­ка), a затем по­ста­вить после каж­до­го че­ло­ве­ка его трой­ку, что можно сде­лать един­ствен­ным об­ра­зом. До­ка­жем ин­дук­ци­ей по n, что ко­ли­че­ство спо­со­бов сде­лать это равно n!, что за­вер­шит ре­ше­ние.

База для оче­вид­на. Пусть утвер­жде­ние верно для n, до­ка­жем его для Рас­ста­вим n че­ло­век в хо­ро­во­ды, это можно сде­лать n! спо­со­ба­ми. В каж­дом раз­би­е­нии на хо­ро­во­ды n че­ло­век есть ровно место, куда можно по­ста­вить остав­ше­го­ся че­ло­ве­ка: в каж­дом су­ще­ству­ю­щем хо­ро­во­де из k че­ло­век таких мест ровно k, а ещё можно вы­де­лить этого че­ло­ве­ка в новый хо­ро­вод.

За­ме­ча­ние.

По­след­нее рас­суж­де­ние можно упро­стить, если за­ме­тить, что каж­дое раз­би­е­ние на хо­ро­во­ды со­от­вет­ству­ет пе­ре­ста­нов­ке на мно­же­стве из n эле­мен­тов, пред­став­лен­ной в форме цик­лов, а ко­ли­че­ство пе­ре­ста­но­вок, как из­вест­но, равно n!.

При­ве­дем дру­гое ре­ше­ние.

За­ну­ме­ру­ем людей чис­ла­ми от 1 до 3n. Есть как раз (3n)! спо­со­бов рас­ста­вить этих людей в ряд, по­это­му до­ста­точ­но уста­но­вить вза­им­но од­но­знач­ное со­от­вет­ствие между та­ки­ми рас­ста­нов­ка­ми и раз­би­е­ни­я­ми на хо­ро­во­ды.

Возьмём любую рас­ста­нов­ку, на­де­нем всем ци­лин­дры в по­ряд­ке АБ­ВА­БВ...АБВ слева на­пра­во. Мыс­лен­но раз­де­лим людей под­ряд на n троек. В пер­вый хо­ро­вод берём под­ряд всех людей от на­ча­ла и до той трой­ки вклю­чи­тель­но, где стоит че­ло­век с но­ме­ром 1 (и за­мы­ка­ем в хо­ро­вод); во вто­рой хо­ро­вод берём сле­ду­ю­щие трой­ки под­ряд до той вклю­чи­тель­но, где стоит че­ло­век с наи­мень­шим из остав­ших­ся но­ме­ров (и за­мы­ка­ем в хо­ро­вод), и так далее.

Об­рат­но, по на­бо­ру хо­ро­во­дов легко вос­ста­но­вить рас­ста­нов­ку: берём хо­ро­вод, где стоит че­ло­век 1, на­хо­дим трой­ку АБВ, в ко­то­рой он на­хо­дит­ся, раз­ре­за­ем хо­ро­вод сразу за этой трой­кой, вы­тя­ги­ва­ем в линию и ста­вим в на­ча­ло рас­ста­нов­ки. Далее берём че­ло­ве­ка с наи­мень­шим но­ме­ром из остав­ших­ся, на­хо­дим «его» хо­ро­вод, так же раз­ре­за­ем и под­со­еди­ня­ем к рас­ста­нов­ке и т. д.

Рас­смот­рим число N и по­сле­до­ва­тель­ность, ко­то­рую Глеб мог вы­пи­сать на доску. Ис­ход­ное число а обо­зна­чим через a₁, а все по­сле­ду­ю­щие через a₂, a₃, ..., a_n. Из усло­вия имеем при а также где через q_k обо­зна­че­ны не­пол­ные част­ные от де­ле­ний.

Мы хотим до­бить­ся вы­пол­не­ния не­ра­вен­ства

Как не­труд­но ви­деть, от­ку­да кроме того, Сле­до­ва­тель­но, до­ста­точ­но до­бить­ся вы­пол­не­ния не­ра­вен­ства

По­ка­жем, что су­ще­ству­ют такие из­на­чаль­ные числа N и a, что при всех вы­пол­не­но и Если это удаст­ся, то за­да­ча будет ре­ше­на, так как не­ра­вен­ство

как из­вест­но, верно при до­ста­точ­но боль­ших n (см. ком­мен­та­рий 1 в конце ре­ше­ния).

Итак, мы вы­бра­ли не­пол­ные част­ные, оста­лось найти под­хо­дя­щие N и a_k. За­ме­тим, что ра­вен­ство

до­пол­нен­ное не­ра­вен­ством эк­ви­ва­лент­но тому, что яв­ля­ет­ся остат­ком от де­ле­ния N на с не­пол­ным част­ным k.

Сна­ча­ла вы­бе­рем и Далее опре­де­лим все по фор­му­ле (1), на­чи­ная с конца. Часть из по­лу­чен­ных чисел, воз­мож­но, ока­жут­ся ра­ци­о­наль­ны­ми; од­на­ко, как легко ви­деть, если N и все a_k до­мно­жить на про­из­воль­ное число, ра­вен­ства (1) со­хра­нят­ся, как и усло­вие по­след­не­го де­ле­ния Про­сто до­мно­жим N и все a_k на их общий зна­ме­на­тель, и они ста­нут це­лы­ми. Оста­лось убе­дить­ся, что все a_k по­ло­жи­тель­ные и что

Для этого сна­ча­ла до­ка­жем ин­дук­ци­ей по k, что База оче­вид­на, так как Пусть мы до­ка­за­ли для до­ка­жем для k. Так как то а за­ме­няя на со­глас­но (1), по­лу­ча­ем ис­ко­мое Оста­лось за­ме­тить, что при и

Это за­вер­ша­ет до­ка­за­тель­ство того, что по­лу­чен­ная по­сле­до­ва­тель­ность ис­ко­мая.

Ответ: да, мог.

Ком­мен­та­рии.

1.  До­ка­жем, что для лю­бо­го на­ту­раль­но­го d можно вы­брать не­сколь­ко пер­вых чле­нов по­сле­до­ва­тель­но­сти чтобы их сумма была боль­ше d. На­при­мер, можно взять пер­вые чисел. Дей­стви­тель­но, их можно раз­бить на 2d ча­стей: в пер­вой части число во вто­рой  — числа и в тре­тьей  — от до и т. д., то есть в m-й части числа от до Тогда для каж­до­го m от 1 до в m-ю часть по­па­дут чисел, и их сумма будет не менее по­это­му сумма всех чисел ока­жет­ся не менее d.

2.  Не­труд­но ви­деть, что не­пол­ные част­ные воз­рас­та­ют с ро­стом k, так как со­от­но­ше­ние

не может вы­пол­нять­ся при и Ана­ло­гич­но можно по­ка­зать, что самое по­след­нее част­ное хотя бы на 2 боль­ше пред­по­след­не­го. От­сю­да ясно, что ис­поль­зу­е­мая выше по­сле­до­ва­тель­ность q_k в не­ко­то­ром смыс­ле «ми­ни­маль­на».

3.  Можно по­ка­зать, что в ка­че­стве об­ще­го зна­ме­на­телл, на ко­то­рый мы до­мно­жа­ли по­лу­чен­ные в ре­ше­нии числа a_k, чтобы они стали це­лы­ми, можно было взять Тогда не­труд­но вы­чис­лить и

За­ме­тим, для каж­до­го дей­ствия есть об­рат­ное ему. По­это­му если мы из си­ту­а­ции A, дей­ствуя по пра­ви­лам, по­лу­чи­ли си­ту­а­цию B, то из си­ту­а­ции B можем по­лу­чить си­ту­а­цию A, дей­ствуя по пра­ви­лам.

По­ка­жем по ин­дук­ции, что если есть запас в n кам­ней, то, дей­ствуя по вы­ше­ука­зан­ным пра­ви­лам, можно по­ло­жить ка­мень в любую клет­ку от 1 до

База ин­дук­ции: Оче­вид­но.

Пе­ре­ход ин­дук­ции. До­пу­стим, мы до­ка­за­ли, что при по­мо­щи за­па­са в n кам­ней можно по­ло­жить ка­мень во все клет­ки до -й. Пусть те­перь есть n чер­ных кам­ней и один крас­ный ка­мень. Будем дей­ство­вать сле­ду­ю­щим об­ра­зом:

1)  не вы­ни­мая крас­ный ка­мень из мешка, до­бьем­ся того, чтобы в -й клет­ке ока­зал­ся чер­ный ка­мень. Это можно сде­лать по пред­по­ло­же­нию ин­дук­ции;

2)  по­ло­жим крас­ный ка­мень в 2ⁿ-ю клет­ку;

3)  про­ве­дем опе­ра­ции как в пунк­те 1), но про­ти­во­по­лож­ные и в об­рат­ном по­ряд­ке. По­нят­но, что крас­ный ка­мень не по­ме­ша­ет это сде­лать. В конце ока­жет­ся, что все чер­ные камни снова лежат в мешке, а на по­лос­ке ровно один ка­мень  — крас­ный ка­мень в клет­ке 2ⁿ. До­го­во­рим­ся, что далее мы крас­ный ка­мень уби­рать не будем;

4)  клет­ки с но­ме­ра­ми от до об­ра­зу­ют по­лос­ку дли­ной К ней при­ме­ни­мо пред­по­ло­же­ние ин­дук­ции для n кам­ней, так как крас­ный ка­мень поз­во­ля­ет со­вер­шать опе­ра­ции с самой левой клет­кой этой по­лос­ки. По­это­му можно по­ло­жить ка­мень в по­след­нюю клет­ку.

Таким об­ра­зом, имея запас в 10 кам­ней, можно по­ло­жить ка­мень во все клет­ки с но­ме­ра­ми от 1 до

Ответ: да.

Ком­мен­та­рий.

На самом деле до­ста­точ­но по­лос­ки дли­ной 1000. Дей­стви­тель­но, за­ме­тим, что среди кле­ток с но­ме­ра­ми от 1000 до 1023 самый пер­вый ка­мень будет по­ло­жен в клет­ку с но­ме­ром 1000. То есть, чтобы по­ло­жить ка­мень в 1000-ю клет­ку, клет­ки с но­ме­ра­ми от 1001 до 1023 ис­поль­зо­вать не обя­за­тель­но, а зна­чит, при за­па­се в 10 кам­ней можно по­ло­жить ка­мень в по­след­нюю клет­ку по­лос­ки дли­ной 1000.

Пусть t  — боль­ший ко­рень мно­го­чле­на тогда До­ка­жем по ин­дук­ции, что число целое при любом целом не­от­ри­ца­тель­ном n. Дей­стви­тель­но, это верно при Кроме того,

что поз­во­ля­ет про­де­лать шаг ин­дук­ции.

По­ло­жим тогда

и зна­чит, и есть верх­няя целая часть а бли­жай­ший к ней квад­рат це­ло­го числа равен

Ком­мен­та­рий.

Не­слож­но ви­деть, что можно взять в ка­че­стве t любое число, яв­ля­ю­ще­е­ся боль­шим кор­нем мно­го­чле­на вида где на­ту­раль­ное число, не мень­шее 3. Дей­стви­тель­но, как и в ре­ше­нии выше, сумма ока­зы­ва­ет­ся целой, от­ку­да для сле­ду­ет утвер­жде­ние за­да­чи.

В этом ре­ше­нии мы уви­де­ли, что для взя­тых нами чисел t рас­сто­я­ние от сте­пе­ни t_n до бли­жай­ше­го це­ло­го стре­мит­ся к нулю с ро­стом n. На самом деле чисел, сте­пе­ни ко­то­рых ста­но­вят­ся все ближе и ближе к целым чис­лам, боль­ше (но про осталь­ные нель­зя ска­зать, что они под­хо­дят для ре­ше­ния дан­ной за­да­чи!). А имен­но, пусть P(x)  — при­ве­ден­ный мно­го­член с це­лы­ми ко­эф­фи­ци­ен­та­ми, у ко­то­ро­го все корни (в том числе ком­плекс­ные), кроме од­но­го, по мо­ду­лю мень­ше 1. Тогда этот ко­рень x₁ ве­ще­ствен­ный, и рас­сто­я­ние от до бли­жай­ше­го це­ло­го числа стре­мит­ся к 0 с ро­стом n. Это сле­ду­ет из того, что сумма n-х сте­пе­ней всех кор­ней мно­го­чле­на P це­ло­чис­лен­но вы­ра­жа­ет­ся через его ко­эф­фи­ци­ен­ты и по­то­му яв­ля­ет­ся целой. А сте­пе­ни всех осталь­ных кор­ней стре­мят­ся к 0  — как раз по­то­му, что они по мо­ду­лю мень­ше 1. Это рас­суж­де­ние можно про­чи­тать в ста­тье А. Еrорова в «Кван­те»; см. также про­ект «Дроб­ные части сте­пе­ней» на Лет­ней кон­фе­рен­ции Тур­ни­ра го­ро­дов-2000.

Такие числа  корни при­ве­ден­но­го мно­го­чле­на с це­лы­ми ко­эф­фи­ци­ен­та­ми, у ко­то­ро­го все осталь­ные корни по мо­ду­лю мень­ше 1,  — на­зы­ва­ют­ся чис­ла­ми Пизо или чис­ла­ми Пизо  — Ви­джая-ра­г­ха­ва­на. Они пред­став­ля­ют ин­те­рес в связи с за­да­ча­ми ди­о­фан­то­вой ап­прок­си­ма­ции и изу­ча­лись в ра­бо­тах Туэ, Харди, Пизо. Фрак­тал Рози (см. рис.) свя­зан с чис­лом Пизо  — кор­нем ку­би­че­ско­го урав­не­ния (и с со­от­вет­ствун­щи­ми под­ста­но­воч­ны­ми по­сле­до­ва­тель­но­стя­ми. Свое на­зва­ние эти числа по­лу­чи­ли после пуб­ли­ка­ции Шарля Пизо, ко­то­рый в своей дис­сер­та­ции от­крыл много за­ме­ча­тель­ных свойств этих чисел.

Будем рас­смат­ри­вать не­сыг­ран­ные игры. Усло­вие озна­ча­ет, что не­сыг­ран­ные игры не об­ра­зу­ют тре­уголь­ни­ков. До­ка­жем ин­дук­ци­ей по k, что для 2k ко­манд наи­боль­шее число не­сыг­ран­ных игр не боль­ше

База ин­дук­ции: (оцен­ка оче­вид­на).

Шаг ин­дук­ции: Пусть до­ка­за­но для k: до­ка­жем для Если не­сыг­ран­ных игр нет, то всё до­ка­за­но. Иначе вы­де­лим про­из­воль­ные ко­ман­ды A и B, не иг­рав­шие между собой. За­ме­тим, что не­сыг­ран­ных игр с уча­сти­ем ко­манд A или B не более (не счи­тая игры между A и B), так как для любой ко­ман­ды C сыг­ра­на хотя бы одна из игр AC и BC. Те­перь рас­смот­рим все ко­ман­ды, кроме A и B и при­ме­ним пред­по­ло­же­ние ин­дук­ции  — среди них не сыг­ра­но не более игр. От­сю­да общее ко­ли­че­ство не­сыг­ран­ных игр не более что и тре­бо­ва­лось до­ка­зать.

Под­став­ляя по­лу­ча­ем, что число не­сыг­ран­ных игр не более 100, а число всех воз­мож­ных игр от­ку­да число сыг­ран­ных игр не менее

Оцен­ка до­сти­га­ет­ся, если раз­бить ко­ман­ды на две рав­ные груп­пы, в каж­дой из ко­то­рых про­ве­сти все матчи, а между груп­па­ми не про­во­дить ни од­но­го.

Ответ: 90 игр.

Будем рас­смат­ри­вать не­сыг­ран­ные игры. Усло­вие озна­ча­ет, что не найдётся трёх ко­манд, ко­то­рые во­об­ще не иг­ра­ли друг с дру­гом. До­ка­жем ин­дук­ци­ей по k, что для 2k ко­манд наи­боль­шее число не­сыг­ран­ных игр не боль­ше

База ин­дук­ции: (оцен­ка оче­вид­на).

Шаг ин­дук­ции: Пусть до­ка­за­но для k: до­ка­жем для Если не­сыг­ран­ных игр нет, то всё до­ка­за­но. Иначе вы­де­лим про­из­воль­ные ко­ман­ды A и B, не иг­рав­шие между собой. За­ме­тим, что не­сыг­ран­ных игр с уча­сти­ем ко­манд A или B не более (не счи­тая игры между A и B), так как для любой ко­ман­ды C сыг­ра­на хотя бы одна из игр AC и BC. Те­перь рас­смот­рим все ко­ман­ды, кроме A и B и при­ме­ним пред­по­ло­же­ние ин­дук­ции среди них не сыг­ра­но не более игр. От­сю­да общее ко­ли­че­ство не­сыг­ран­ных игр не более что и тре­бо­ва­лось до­ка­зать.

Под­став­ляя по­лу­ча­ем, что число не­сыг­ран­ных игр не более 64, а число всех воз­мож­ных игр от­ку­да число сыг­ран­ных игр не менее

Оцен­ка до­сти­га­ет­ся, если раз­бить ко­ман­ды на две рав­ные груп­пы, в каж­дой из ко­то­рых про­ве­сти все матчи, а между груп­па­ми не про­во­дить ни од­но­го.

Ответ: 56 игр.

По­ка­жем ин­дук­ци­ей по n, что, если по кругу за­пи­са­ны 2ⁿ чисел, то ответ за­да­чи равен 2ⁿ. База ин­дук­ции рас­смат­ри­ва­ет­ся не­слож­но: либо либо в любом слу­чае двух опе­ра­ций все­гда до­ста­точ­но, а мень­ше  — не все­гда.

Шаг ин­дук­ции. Пусть по кругу за­пи­са­ны чисел и утвер­жде­ние верно для любых 2ⁿ плюс-минус еди­ниц по кругу. Рас­смот­рим от­дель­но мно­же­ства А, из 2ⁿ чисел, сто­я­щих на ме­стах с нечётными ин­дек­са­ми и B  — из 2ⁿ чисел сто­я­щих на ме­стах с чётными ин­дек­са­ми, За­ме­тим, что после вы­пол­не­ния двух опе­ра­ций каж­дое число a_k, за­ме­нит­ся на про­из­ве­де­ние

так как От­сю­да сле­ду­ет, что, в ре­зуль­та­те вы­пол­не­ния двух опе­ра­ций на ис­ход­ном мно­же­стве из чисел мно­же­ства А и В ме­ня­ют­ся так, как если бы на каж­дом из них было вы­пол­не­но по одной опе­ра­ции. По пред­по­ло­же­нию ин­дук­ции, для того, чтобы по­лу­чить вме­сто мно­жеств А и В мно­же­ства из одних еди­ниц, до­ста­точ­но 2ⁿ опе­ра­ций, сле­до­ва­тель­но, чтобы по­лу­чить все еди­ни­цы из ис­ход­но­го мно­же­ства, до­ста­точ­но вдвое боль­ше­го числа опе­ра­ций, то есть опе­ра­ций. При­ме­ром мно­же­ства чисел, для ко­то­ро­го не­об­хо­ди­мо ровно опе­ра­ций, яв­ля­ет­ся мно­же­ство из 31 еди­ни­цы и одной минус еди­ни­цы. После двух опе­ра­ций оно даст ана­ло­гич­ные мно­же­ства чисел А и В, для ко­то­рых, по ин­дук­ции, нужно ровно 2ⁿ опе­ра­ций, зна­чит, для ис­ход­но­го мно­же­ства их нужно ровно При ко­ли­че­стве чисел число не­об­хо­ди­мых опе­ра­ций рано 32.

Ответ: 32.

За­пи­шем не­ра­вен­ство в виде Квад­ра­тич­ная функ­ция по­ло­жи­тель­на при по­это­му из по­ло­жи­тель­но­сти сле­ду­ет при всех в част­но­сти, и при Это до­ка­зы­ва­ет утвер­жде­ние за­да­чи в слу­чае

Мак­си­маль­ное зна­че­ние функ­ции на ин­тер­ва­ле равно при по­это­му при всех Это до­ка­зы­ва­ет, в част­но­сти, утвер­жде­ние за­да­чи для

Далее вос­поль­зу­ем­ся ме­то­дом ма­те­ма­ти­че­ской ин­дук­ции, в ка­че­стве базы ин­дук­ции ис­поль­зу­ем уже до­ка­зан­ные слу­чаи Пусть утвер­жде­ние за­да­чи вы­пол­не­но для На ин­тер­ва­ле

функ­ция мо­но­тон­но воз­рас­та­ет, сле­до­ва­тель­но,

что до­ка­зы­ва­ет спра­вед­ли­вость шага ин­дук­ции.

Вы­ра­зим явно через a_n, найдём не­сколь­ко пер­вых зна­че­ний a_n, до­га­да­ем­ся до общей фор­му­лы и до­ка­жем её по ин­дук­ции.

Итак,

обе части боль­ше 0, воз­во­дим в квад­рат, по­лу­ча­ем:

Сле­до­ва­тель­но, яв­ля­ет­ся одним из кор­ней квад­рат­но­го урав­не­ния

На­хо­дим эти корни:

ввиду ра­вен­ства

вы­брать нужно тот, ко­то­рый с плю­сом,

Под­став­ля­ем по­лу­чим под­став­ля­ем по­лу­чим под­став­ля­ем по­лу­чим после чего ра­зум­но пред­по­ла­га­ем, что

Оста­лось до­ка­зать это ра­вен­ство по ин­дук­ции. База ин­дук­ции толь­ко что про­ве­ре­на. Шаг ин­дук­ции: если то, дей­стви­тель­но,

что и тре­бо­ва­лось до­ка­зать.

Ответ:

Это из­вест­ная за­да­ча о Ха­ной­ской башне, ко­то­рую часто рас­смат­ри­ва­ют среди пер­вых задач на метод ма­те­ма­ти­че­ской ин­дук­ции. Соб­ствен­но го­во­ря, для ре­ше­ния этой за­да­чи нам не тре­бу­ет­ся ис­поль­зо­вать метод ма­те­ма­ти­че­ской ин­дук­ции, по­сколь­ку в ее усло­вии дано кон­крет­ное число колец. Разо­брав слу­чаи по­лу­чим, что по­тре­бу­ют­ся, со­от­вет­ствен­но, одно, три или семь пе­ре­кла­ды­ва­ний. Для того, чтобы пе­ре­ло­жить «башню» из че­ты­рех колец, не­об­хо­ди­мо: снять верх­ние три коль­ца, затем пе­ре­ло­жить ниж­нее коль­цо на сво­бод­ную па­лоч­ку и, на­ко­нец, по­ло­жить на него три коль­ца мень­ше­го диа­мет­ра. Таким об­ра­зом, по­тре­бу­ют­ся пе­ре­кла­ды­ва­ний. Решим за­да­чу для про­из­воль­но­го числа n колец. Из при­ве­ден­но­го рас­суж­де­ния сразу сле­ду­ет ре­кур­рент­ная фор­му­ла для чисел p_n наи­мень­ше­го числа пе­ре­кла­ды­ва­ний для башни, со­сто­я­щей из n колец:

Дей­стви­тель­но, для того, чтобы пе­ре­ло­жить ниж­нее, -е, коль­цо, нам вна­ча­ле надо пе­ре­ло­жить n ле­жа­щих над ним колец, на что будут за­тра­че­но p_n пе­ре­кла­ды­ва­ний. Затем мы пе­ре­ло­жим ниж­нее коль­цо и по­тра­тим еще p_n пе­ре­кла­ды­ва­ний, чтобы по­ме­стить на нем n верх­них колец. Не­труд­но до­га­дать­ся, что После этого оста­лось сде­лать по­след­ний шаг, со­сто­я­щий в при­ме­не­нии ме­то­да ма­те­ма­ти­че­ской ин­дук­ции для до­ка­за­тель­ства най­ден­ной фор­му­лы. Таким об­ра­зом, оста­лось ре­шить сле­ду­ю­щую за­да­чу: из­вест­но, что и для всех n До­ка­жи­те, что База ин­дук­ции: Ин­дук­ци­он­ный пе­ре­ход: если то

За­да­ча о ха­ной­ской башне яв­ля­ет­ся одной из луч­ших задач на ин­дук­ци­он­ный метод рас­суж­де­ния, в ее ре­ше­нии соб­ствен­но «метод ма­те­ма­ти­че­ской ин­дук­ции» иг­ра­ет не слиш­ком со­дер­жа­тель­ную роль. Ана­лиз при­ве­ден­но­го ре­ше­ния по­ка­зы­ва­ет, что су­ще­ство ре­ше­ния  — в по­стро­е­нии так на­зы­ва­е­мо­го ре­кур­сив­но­го ал­го­рит­ма.

Ответ:

До­ка­за­тель­ство можно про­ве­сти по ин­дук­ции, вос­поль­зо­вав­шись тож­де­ством

За­ме­тим, од­на­ко, что здесь тре­бу­ет­ся от­лич­ная от стан­дарт­ной, но как из­вест­но, рав­но­силь­ная ей, фор­му­ли­ров­ка прин­ци­па ма­те­ма­ти­че­ской ин­дук­ции: если верно утвер­жде­ние P(1) и из того, что утвер­жде­ние P(k) верно при всех сле­ду­ет, что верно утвер­жде­ние P(k + 1), то утвер­жде­ние P(n) верно при всех на­ту­раль­ных n.

Пункт а) оче­ви­ден и при­ве­ден здесь в ка­че­стве под­сказ­ки к ре­ше­нию пунк­та б). Пусть p_n  — число об­ла­стей, на ко­то­рые делят плос­кость n пря­мых. До­ка­жи­те, что от­ку­да по ин­дук­ции не­слож­но по­лу­чить ответ.

Ответ: а) б)

Фор­маль­ная сто­ро­на за­да­чи свя­за­на с до­ка­за­тель­ством (по ин­дук­ции) тож­де­ства

Идея ре­ше­ния видна уже на доске (см. рис.): раз­де­лив ее на че­ты­ре квад­ра­та и по­ло­жив уго­лок в центр так, чтобы он не за­де­вал квад­ра­ти­ка, из ко­то­ро­го уда­ле­на клет­ка, мы об­на­ру­жим, что на доске по­яви­лись места еще для че­ты­рех угол­ков. После рас­суж­де­ние про­во­дит­ся ин­дук­ци­ей по n.

Рас­смот­рим слу­чай, когда тогда сол­дат либо уже на­хо­дит­ся в пра­виль­ном по­ло­же­нии, либо при­хо­дит в него за 1 се­кун­ду. Если то пе­ре­би­рая все ва­ри­ан­ты на­чаль­но­го рас­по­ло­же­ния при­хо­дим к вы­во­ду, что мак­си­маль­ное время −3 се­кун­ды. Если то мак­си­маль­ное время  — 5 се­кунд. Сде­ла­ем пред­по­ло­же­ние ин­дук­ции, что для про­из­воль­но­го n время будет Пусть есть сол­дат. За­ме­тим, что для дви­жу­щих­ся левее еф­рей­то­ра сол­дат ока­зы­ва­ет­ся, что после того как еф­рей­тор ока­зы­ва­ет­ся смот­ря­щим на­ле­во, сол­да­ты дей­ству­ют также как если бы еф­рей­тор по­сто­ян­но смот­рел на­ле­во, по­сколь­ку на сле­ду­ю­ще­го за еф­рей­то­ром сол­да­та по­ло­же­ние еф­рей­то­ра вли­я­ет толь­ко в тех слу­ча­ях, когда они стоят с еф­рей­то­ром лицом к лицу. Еф­рей­тор после каж­до­го сво­е­го раз­во­ро­та воз­вра­ща­ет­ся в «пра­виль­ное» по­ло­же­ние за одну се­кун­ду и не ме­ня­ет сво­е­го по­ло­же­ния до тех пор, пока сле­ду­ю­щий за ним сол­дат не при­дет в «не­пра­виль­ное» по­ло­же­ние, а для того, чтобы сто­я­щий за еф­рей­то­ром сол­дат вер­нул­ся в «не­пра­виль­ное» по­ло­же­ние также долж­но прой­ти не менее одной се­кун­ды.

Пусть еф­рей­тор из­на­чаль­но на­хо­дит­ся в «пра­виль­ном» по­ло­же­нии, тогда даль­ней­шая эво­лю­ция си­сте­мы из n сол­дат, сто­я­щих за ним будет про­хо­дить также как в слу­чае n сол­дат  — зa се­кун­ду они вы­стро­ят­ся в «пра­виль­ном» по­ряд­ке. Если еф­рей­тор из­на­чаль­но не на­хо­дит­ся в пра­виль­ном по­ло­же­нии, то он по­тра­тит 1 се­кун­ду перед этим, чтобы при­дти в него. После того как n сол­дат вы­стро­и­лись пра­виль­но, в не­пра­виль­ном по­ло­же­нии может остать­ся еф­рей­тор, ко­то­ро­му нужно по­тра­тить 1 се­кун­ду, чтобы при­дти в пра­виль­ное по­ло­же­ние. Скла­ды­вая не­об­хо­ди­мое время по­лу­ча­ем, что сол­дат вы­стро­ят­ся пра­виль­но за се­кун­ду. Чтобы по­ка­зать, что это время дей­стви­тель­но мак­си­маль­но (то есть оцен­ку для сол­дат нель­зя улуч­шить), при­ве­дем при­мер кон­фи­гу­ра­ции, ко­то­рая дает ровно се­кун­ду. Обо­зна­чим за →, сол­да­та, смот­ря­ще­го на­пра­во, и за ← — сол­да­та, смот­ря­ще­го на­ле­во. Таким свой­ством об­ла­да­ет кон­фи­гу­ра­ция где по­след­няя стрел­ка от­ве­ча­ет сер­жан­ту. Через n се­кунд си­сте­ма будет на­хо­дить­ся в со­сто­я­нии имея в виду, что по­ло­же­ния сол­дат будут по­вто­рять­ся через од­но­го. После этого через каж­дую се­кун­ду слева будет уве­ли­чи­вать­ся ко­ли­че­ство сол­дат, смот­ря­щих «на­ле­во» и сто­я­щих при этом под­ряд. Про­цесс за­кон­чит­ся, когда слева ока­жет­ся n, смот­ря­щих «на­ле­во» сол­дат, сто­я­щих при этом под­ряд. Для этого нужно, чтобы после n-той се­кун­ды слева «при­рос­ло» ещё сол­дат, по­это­му после n-той се­кун­ды по­на­до­бить­ся еще се­кун­да. Таким об­ра­зом, сол­да­ты при­дут в «пра­виль­ное» по­ло­же­ние ровно через се­кун­ду. Таким об­ра­зом, мак­си­маль­ное время для n сол­дат не боль­ше, чем се­кун­да, и не мень­ше, чем се­кун­да.

Ответ: мак­си­маль­ное время для n сол­дат не боль­ше, чем се­кун­да, и не мень­ше, чем се­кун­да.

До­ка­жем ме­то­дом ма­те­ма­ти­че­ской ин­дук­ции, что для лю­бо­го на­ту­раль­но­го

где Для ра­вен­ство вы­пол­ня­ет­ся с ко­эф­фи­ци­ен­та­ми Пред­по­ло­жим те­перь, что утвер­жде­ние верно для не­ко­то­ро­го фик­си­ро­ван­но­го n до­ка­жем, что из ра­вен­ства для n сле­ду­ет ра­вен­ство для Тогда

Об­ра­тим вни­ма­ни­ем, что мы по­лу­чи­ли ре­кур­рент­ные со­от­но­ше­ния и при­чем

Ана­ло­гич­но до­ка­зы­ва­ет­ся, что

с теми же ко­эф­фи­ци­ен­та­ми a_n, b_n. Из ра­венств

пе­ре­мно­жая левые и пра­вые части, по­лу­ча­ем

1)  До­ка­жем сна­ча­ла, что для лю­бо­го на­ту­раль­но­го k и про­из­воль­ных дей­стви­тель­ных чисел a₁, ..., a_k спра­вед­ли­во не­ра­вен­ство

Будем рас­суж­дать по ин­дук­ции. База ин­дук­ции при оче­вид­на. Сде­ла­ем шаг ин­дук­ции. Пусть утвер­жде­ние спра­вед­ли­во для k сла­га­е­мых. До­ка­жем его для сла­га­е­мо­го. Тогда

По пред­по­ло­же­нию ин­дук­ции в пра­вой части по­след­не­го не­ра­вен­ства, По­лу­чим:

от­ку­да и по­лу­ча­ет­ся ис­ко­мое не­ра­вен­ство.

2)  Те­перь зай­мем­ся утвер­жде­ни­ем из усло­вия за­да­чи. Оно опять же оче­вид­но при Для по до­ка­зан­но­му в 1) имеем:

Учи­ты­вая те­перь не­ра­вен­ство из усло­вия за­да­чи, по­лу­чим:

от­ку­да сле­ду­ет вы­те­ка­ет, что Те­перь про­сто из­ме­няя по­ря­док ну­ме­ра­ции чисел можно ана­ло­гич­но по­ка­зать, что любое

Ин­дук­ци­ей по n до­ка­жем, что

База ин­дук­ции: при ра­вен­ство, оче­вид­но, верно.

Шаг ин­дук­ции: пусть при верно ра­вен­ство

Рас­смот­рим от­сю­да

что и тре­бо­ва­лось до­ка­зать.

По до­ка­зан­но­му, ис­ход­ное урав­не­ние рав­но­силь­но урав­не­нию Его кор­нем яв­ля­ет­ся

Ответ:

Рас­смот­рим точки, ко­то­рые яв­ля­ют­ся пра­вы­ми ниж­ни­ми и ле­вы­ми верх­ни­ми уг­ла­ми ло­ма­ной, то есть точки вида и Легко ви­деть, что это точки P₁, P₄, P₉, и т. д. Дей­стви­тель­но, рас­сто­я­ние от точки до по ло­ма­ной со­став­ля­ет что есть раз­ность между и Ана­ло­гич­но, рас­сто­я­ние от до равно что есть раз­ность между и По ин­дук­ции по­лу­ча­ем, что и

За­ме­тим, что Зна­чит, точка P₂₀₂₅ имеет ко­ор­ди­на­ты (23, −22). Точка P₂₀₁₇ на 8 пра­вее ее, то есть имеет ко­ор­ди­на­ты (15, −22).

Ответ: (15, −22).

Рас­смот­рим точки, ко­то­рые яв­ля­ют­ся пра­вы­ми ниж­ни­ми и ле­вы­ми верх­ни­ми уг­ла­ми ло­ма­ной, то есть точки вида и Легко ви­деть, что это точки P₁, P₄, P₉, и т. д. Дей­стви­тель­но, рас­сто­я­ние от точки до по ло­ма­ной со­став­ля­ет что есть раз­ность между и Ана­ло­гич­но, рас­сто­я­ние от до равно что есть раз­ность между и По ин­дук­ции по­лу­ча­ем, что и

За­ме­тим, что Зна­чит, точка P₁₅₂₁ имеет ко­ор­ди­на­ты (20, −19). Точка P₁₅₅₇ на 36 выше ее, то есть имеет ко­ор­ди­на­ты (20, 17).

Ответ: (20, 17).