До­ка­жем это утвер­жде­ние ин­дук­ци­ей по n.

База при

При разобьём на мно­жеств а {1, 2} и {3}, от­но­ше­ние равно что мень­ше При разобьём на мно­же­ства {1, 2, 3} и {4}, От­но­ше­ние будет что как раз равно

При разобьём на мно­же­ства {1, 2, 5} и {3, 4}. От­но­ше­ние равно что мень­ше

Пе­ре­ход ин­дук­ции от n к при Пусть у нас есть раз­би­е­ние чисел от 1 до n, удо­вле­тво­ря­ю­щее усло­вию. До­ба­вим в мно­же­ство с мень­шим про­из­ве­де­ни­ем число а в мно­же­ство с боль­шим про­из­ве­де­ни­ем P₂ число

До­ка­жем, что про­из­ве­де­ния от­ли­ча­ют­ся не более чем в раз. Так как то

С дру­гой сто­ро­ны, так как то

До­ка­жем, что это не боль­ше Это рав­но­силь­но

что верно при Таким об­ра­зом, пе­ре­ход, до­ка­зан.

Рас­смот­рим не­ко­то­рый про­ме­жу­точ­ный шаг в дви­же­нии Кузи. Если она на этом шаге на­хо­дит­ся в точке A, то ве­ро­ят­ность по­пасть в A на сле­ду­ю­щем шаге равна нулю. Если же она на­хо­дит­ся в любой из остав­ших­ся точек, B, C или D,то ве­ро­ят­ность по­пасть в A на сле­ду­ю­щем шаге равна так как из каж­дой такой точки есть три рав­но­воз­мож­ных пути, толь­ко один из ко­то­рых при­во­дит в A. Пусть p_k  — ве­ро­ят­ность того, что на k  — ом шаге блоха на­хо­дит­ся в точке A. Со­от­вет­ствен­но не в точке A она на­хо­дит­ся с ве­ро­ят­но­стью Тогда на сле­ду­ю­щем шаге она ока­жет­ся в A с ве­ро­ят­но­стью

Таким об­ра­зом, а далее по­лу­чим

Фор­му­лу для p_n при до­ка­жем ме­то­дом ма­те­ма­ти­че­ской ин­дук­ции.

База ин­дук­ции:   — верно.

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

Тогда

то есть фор­му­ла верна и для А зна­чит, верна и при любых Видим, что p_n пред­став­ля­ет собой сумму чле­нов гео­мет­ри­че­ской про­грес­сии со зна­ме­на­те­лем Сле­до­ва­тель­но,

Ответ:

За­ме­тим, что по ин­дук­ции легко до­ка­зать, что в любом де­ре­ве число вер­шин на 1 боль­ше числа рёбер (на­чи­ная с одной вер­ши­не, до­бав­ля­ем по од­но­му ребру  — при этом до­бав­ля­ет­ся по одной вер­ши­не и по од­но­му ребру): Если сум­ми­ро­вать число рёбер, вхо­дя­щих в каж­дую вер­ши­ну (сте­пе­ни вер­шин), то по­лу­чит­ся число вдвое боль­ше числа рёбер, так как каж­дое ребро со­еди­ня­ет две вер­ши­ны:

Таким об­ра­зом, для пяти вер­шин сумма сте­пе­ней будет равна 2 · 4  =  8. Рас­смот­рим все раз­ло­же­ния числа 8 в сумму пяти сла­га­е­мых и со­от­вет­ству­ю­щие де­ре­вья:

Ответ: не­труд­но ви­деть, что каж­до­му раз­ло­же­нию со­от­вет­ству­ет ровно одно де­ре­во. Все дру­гие можно по­лу­чить пе­ре­ме­ще­ни­ем вер­шин из этих трёх (изо­морф­ны), в то же время ни какие два из этих трёх де­ре­вьев не изо­морф­ны, так как от­ли­ча­ют­ся сте­пе­ня­ми вер­шин.

До­ка­жем это по ин­дук­ции. База со­дер­жит­ся в усло­вии.

Для пе­ре­хо­да от к вос­поль­зу­ем­ся ин­дук­ци­он­ным пред­по­ло­же­ни­ем. Рас­смот­рим сле­ду­ю­щие эле­мен­ты для го­ло­со­ва­ния че­ло­ве­ка: все, кроме пер­во­го и вто­ро­го; все, кроме вто­ро­го и тре­тье­го и все, кроме пер­во­го и тре­тье­го че­ло­ве­ка.. Вы­хо­ды каж­до­го из этих эле­мен­тов отож­де­ствим с вхо­да­ми четвёртого эле­мен­та для го­ло­со­ва­ния трёх че­ло­век. По­лу­чен­ная схема почти все­гда будет да­вать ре­зуль­тат, сов­па­да­ю­щий с го­ло­со­ва­ни­ем боль­шин­ства. Един­ствен­ное ис­клю­че­ние  — си­ту­а­ция, в ко­то­рой боль­шин­ство со­сто­ит ровно из че­ло­ве­ка и в это боль­шин­ство вхо­дят од­но­вре­мен­но люди с но­ме­ра­ми 1, 2 и 3. Со­зда­дим ещё две ана­ло­гич­ных схемы, ко­то­рые «оши­ба­ют­ся» в дру­гих си­ту­а­ци­ях. Тогда, если мы замкнём их вы­хо­ды на вход ещё од­но­го эле­мен­та для го­ло­со­ва­ния трёх че­ло­век, по­лу­чен­ный ре­зуль­тат все­гда будет верен.

Remark that group n comprises n consecutive integers; hence the group starts with the number (easy to prove by induction) and ends by because of this, the group starts with 1 977 067 and ends by 1 979 055.

За­ме­тим, что n-ая груп­па со­сто­ит из n по­сле­до­ва­тель­ных на­ту­раль­ных чисел; по­это­му эта груп­па на­чи­на­ет­ся с числа (до­ка­зы­ва­ет­ся по ин­дук­ции) и за­кан­чи­ва­ет­ся чис­лом и, сле­до­ва­тель­но, 1989-ая груп­па на­чи­на­ет­ся с числа 1 977 067, а за­кан­чи­ва­ет­ся чис­лом 1 979 055.

Ответ: на­чи­на­ет­ся с числа 1 977 067, а за­кан­чи­ва­ет­ся чис­лом 1 979 055.

As has been demonstrated in the solution of the problem 4 for the grade, group starts with and ends by hence the sum of this group is In particular,

Из ре­ше­ния за­да­чи 4 для 9 клас­са мы знаем, что n-ая груп­па на­чи­на­ет­ся с числа (до­ка­зы­ва­ет­ся по ин­дук­ции) и за­кан­чи­ва­ет­ся чис­лом и, сле­до­ва­тель­но, сумма этой груп­пы равна По­это­му

Ответ: 3 934 363 329.

The sum of all with odd indexes from 1 до is n⁴. Proof by induction with use of the problem 6691.

Сумма всех групп с не­чет­ны­ми ин­дек­са­ми от 1 до равна n⁴. До­ка­за­тель­ство по ин­дук­ции с ис­поль­зо­ва­ни­ем за­да­чи 6691.

Ответ: n⁴.

Сна­ча­ла да­вай­те «по­экс­пе­ри­мен­ти­ру­ем» и вы­чис­лим «сим­во­ли­че­ски» зна­че­ние функ­ции g для ка­ко­го-либо не­боль­шо­го зна­че­ния m, на­при­мер, вы­чис­лим

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

База ин­дук­ции для лю­бо­го

Ин­дук­ци­он­ная ги­по­те­за: пусть для всех верно, что для лю­бо­го це­ло­го

Шаг ин­дук­ции:

Ответ: в со­от­вет­ствии с прин­ци­пом ма­те­ма­ти­че­ской ин­дук­ции для всех целых не­от­ри­ца­тель­ных m и n.

Сна­ча­ла да­вай­те «по­экс­пе­ри­мен­ти­ру­ем» и вы­чис­лим «сим­во­ли­че­ски» зна­че­ние функ­ции g для ка­ко­го-либо зна­че­ния m, близ­ко­го к 100, на­при­мер, вы­чис­лим

1)   где

2)   где

3)   сле­ду­ет из 2;

4)   сле­ду­ет из 1 и 3;

5)   где

6)   сле­ду­ет из 4 и 5;

7)   сле­ду­ет из 1 и 6.

Из этого экс­пе­ри­мен­та видно, что

а)    — см. опре­де­ле­ние функ­ции;

б)    — см. пункт 3 экс­пе­ри­мен­та;

в)    — см. пункт 7 экс­пе­ри­мен­та.

По­это­му воз­ни­ка­ет пред­по­ло­же­ние, что для любых целых зна­че­ний и любых целых зна­че­ний

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

для лю­бо­го це­ло­го

База ин­дук­ции

Ин­дук­ци­он­ная ги­по­те­за: пусть для всех верно

для лю­бо­го

Шаг ин­дук­ции:

1.   где

2.    — по пред­по­ло­же­нию ин­дук­ции;

3.    — со­глас­но 2;

4.   по пред­по­ло­же­нию ин­дук­ции;

5.    — со­глас­но 3 и 4;

6.    — со­глас­но 1 и 5;

7.    — со­глас­но 1 и 6.

Ответ: в со­от­вет­ствии с прин­ци­пом ма­те­ма­ти­че­ской ин­дук­ции для всех целых не­от­ри­ца­тель­ных и

Начнём с того, что вы­чис­лим не­сколь­ко пер­вых чле­нов по­сле­до­ва­тель­но­сти:

1)   по опре­де­ле­нию;

2)  

3)  

4)

Можно за­ме­тить, что ! для пер­вых пяти чле­нов по­сле­до­ва­тель­но­сти (то есть для всех [0. .4]).

До­ка­жем ин­дук­ци­ей по n, что для всех

База ин­дук­ции, и уже рас­смот­ре­на выше (см. вы­чис­ле­ние пер­вых чле­нов по­сле­до­ва­тель­но­сти).

Ин­дук­ци­он­ная ги­по­те­за: пусть для всех

Шаг ин­дук­ции:

Ответ: в со­от­вет­ствии с прин­ци­пом ма­те­ма­ти­че­ской ин­дук­ции, для всех

Лемма. Любое число a можно пред­ста­вить в виде суммы k дро­бей вида ко­неч­ным чис­лом спо­со­бов (если во­об­ще можно пред­ста­вить).

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

Те­перь по­ка­жем, как Петя может хо­дить так, чтобы Вася после сво­е­го хода ни­ко­гда не сде­лал сумму целой. Пусть перед ходом Пети сумма чисел на доске равна S, а Вася после его хода будет вы­пи­сы­вать k дро­бей. За­ме­тим, что после хода Васи сумма чисел точно не ста­нет боль­ше чем то есть он точно не по­лу­чит на­ту­раль­ное число, боль­шее Для каж­дой из остав­ших­ся по­тен­ци­аль­ных на­ту­раль­ных сумм (а их оста­лось ко­неч­ное ко­ли­че­ство) по­счи­та­ем, на сколь­ко надо уве­ли­чить те­ку­щую сумму, чтобы она стала такой. Из леммы сле­ду­ет, что для каж­до­го та­ко­го числа су­ще­ству­ет лишь ко­неч­ное ко­ли­че­ство пред­став­ле­ний его в виде суммы дроби вида Зна­чит, всего во всех пред­став­ле­ни­ях за­дей­ство­ва­но ко­неч­ное число дро­бей вида

Пусть Петя тогда за­пи­шет на доску ту дробь, ко­то­рая не за­дей­ство­ва­на ни в одном из пред­став­ле­ний. Тогда Вася точно не смо­жет на­пи­сать k дро­бей так, чтобы сумма стала на­ту­раль­ной.

Ответ: смо­жет.

Ре­ше­ние 1. Раз­де­лим ко­ле­со на 360 дуг и за­ну­ме­ру­ем их, на­чи­ная с точки O в по­ряд­ке «про­ка­ты­ва­ния». До­ка­жем ин­дук­ци­ей по k, что можно вы­брать окруж­ность длины 360s, про­ка­тив ко­то­рую по пря­мой, мы по­лу­чим следы внут­ри пер­вых k дуг.

База (k  =  1). До­ста­точ­но вы­брать s, боль­шее ко­ор­ди­на­ты пер­вой от­ме­чен­ной точки.

Шаг ин­дук­ции. По пред­по­ло­же­нию ин­дук­ции найдётся s_k, при ко­то­ром следы остав­ле­ны на пер­вых дугах. Пусть они остав­ле­ны точ­ка­ми с ко­ор­ди­на­та­ми

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

где m  — целое число. Тогда

Найдём такое чтобы точка оста­ви­ла след на дан­ном рас­сто­я­нии (по окруж­но­сти) от O (число t < 1 вы­бе­рем так, чтобы этот след ока­зал­ся на (k + 1)-й дуге окруж­но­сти, со­от­вет­ству­ю­щей Иными сло­ва­ми,

от­ку­да

где

Это зна­че­ние под­хо­дит, по­сколь­ку

a

Ре­ше­ние 2. Пусть на чис­ло­вой пря­мой от­ме­че­но бес­ко­неч­ное число на­ту­раль­ных точек t₁, t₂, t₃, ... До­ка­жем ин­дук­ци­ей по n такое утвер­жде­ние: для лю­бо­го на­бо­ра по­ло­жи­тель­ных чисел сум­мой 1 найдётся ко­ле­со такой длины S, что раз­де­лив его на дуги длин (имен­но в таком по­ряд­ке) и за­пу­стив из 0 (по­ста­вив в 0 на­ча­лом пер­вой дуги), мы обя­за­тель­но по­лу­чим стро­го внут­ри каж­дой из дуг след какой-то от­ме­чен­ной точки.

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

Сна­ча­ла за­ме­тим, что если для дан­но­го на­бо­ра нуж­ное S най­де­но, то по­дойдёт также любое ко­ле­со чуть мень­шей или чуть боль­шей длины. В самом деле, ко­ле­со длины S соберёт по от­мет­ке на каж­дую дугу, прой­дя опре­делённое рас­сто­я­ние. Это со­от­вет­ству­ет тому, что не­ко­то­рые от­ме­чен­ные точки лежат на пря­мой каж­дая стро­го внут­ри от­рез­ка сво­е­го цвета (цвета все раз­лич­ны). Не­боль­шое из­ме­не­ние длины ко­ле­са со­от­вет­ству­ет го­мо­те­тии пря­мой с цен­тром в 0 и ко­эф­фи­ци­ен­том, близ­ким к 1. Ясно, что можно вы­брать ко­эф­фи­ци­ент го­мо­те­тии на­столь­ко близ­ким к 1, что кар­ти­на не из­ме­нит­ся: все точки оста­нут­ся внут­ри своих «рас­тя­ну­тых» от­рез­ков.

Пе­рейдём к до­ка­за­тель­ству.

База n  =  1 оче­вид­на: можно взять ко­ле­со ир­ра­ци­о­наль­ной или про­сто до­ста­точ­но боль­шой длины.

Шаг ин­дук­ции. Пусть для всех на­бо­ров из n чисел утвер­жде­ние до­ка­за­но. До­ка­жем его для на­бо­ра Рас­смот­рим набор Для него нуж­ное S найдётся. Рас­смот­рим мо­мент, когда в каж­дой из дуг для этого на­бо­ра об­ра­зу­ет­ся след от от­ме­чен­ной точки. Это со­от­вет­ству­ет тому, что от­ме­чен­ные точки лежат на пря­мой стро­го внут­ри от­рез­ков n раз­ных цве­тов, точка лежит на от­рез­ке длины Если точка делит свой от­ре­зок как раз в от­но­ше­нии уве­ли­чим не­мно­го S, чтобы все точки по­па­ли на свои же «рас­тя­ну­тые» от­рез­ки, но точка уже де­ли­ла бы свой от­ре­зок в дру­гом от­но­ше­нии.

Точки по­па­дут в от­рез­ки раз­ных цве­тов, и толь­ко от­рез­ки од­но­го, ска­жем, зелёного цвета (со­от­вет­ству­ю­щие одной из дуг пусть дуге ), воз­мож­но, не со­дер­жат ни одной от­ме­чен­ной точки.

За­ме­тим, что есть сколь угод­но боль­шие от­ме­чен­ные точки, на рас­сто­я­нии не более чем S слева от ко­то­рых есть зелёный от­ре­зок. Пусть мы можем де­лать го­мо­те­тию с ко­эф­фи­ци­ен­том, не боль­шим так, чтобы точки оста­лись внут­ри своих «рас­тя­ну­тых» от­рез­ков.

Про­едем ко­ле­сом на­столь­ко боль­шое рас­сто­я­ние K, чтобы ко­ле­со сде­ла­ло целое число обо­ро­тов (по­след­ний окра­шен­ный от­ре­зок Z зелёный), уже со­бра­ло от­мет­ки на все дуги, кроме по­след­ней, чтобы было боль­ше S, и чтобы на рас­сто­я­нии не более S после точки K на­шлась от­ме­чен­ная точка

Уве­ли­чим длину ко­ле­са, сде­лав го­мо­те­тию с ко­эф­фи­ци­ен­том 1 + x, где Тогда зелёный от­ре­зок Z рас­тя­нет­ся, его но­вы­ми кон­ца­ми будут точки и со­от­вет­ствен­но. Оче­вид­но, можно по­до­брать так, чтобы стало боль­ше ведь но при этом боль­ше на ве­ли­чи­ну, мень­шую Тогда будет мень­ше то есть точка попадёт на «рас­тя­ну­тый» зелёный от­ре­зок Z.

Пусть a_n и a_n + m  — два про­из­воль­ных члена по­сле­до­ва­тель­но­сти До­ка­жем, что можно пред­ста­вить в виде

где P_m(x)  — мно­го­член с це­лы­ми ко­эф­фи­ци­ен­та­ми. Мы до­ка­жем этот факт по ин­дук­ции. Для имеем

то есть Для по­лу­чим

то есть

Пусть при тогда при будем иметь

и, зна­чит, мно­го­член имеет вид

и по­это­му его ко­эф­фи­ци­ен­ты целые.

Най­дем на­боль­шей обшей де­ли­тель a_n и Из по­след­не­го со­от­но­ше­ния сле­ду­ет, что если НОД то и 1 де­лит­ся на d и, сле­до­ва­тель­но, то есть a_n и вза­им­но про­сты.

По­счи­та­ем пер­вые члены по­сле­до­ва­тель­но­сти a_n, Для a₂ имеем по усло­вию то есть и от­ку­да Для a₃ имеем тогда то есть и от­ку­да От­сю­да легко уга­ды­ва­ет­ся общая фор­му­ла

До­ка­жем её по ин­дук­ции. База уже до­ка­за­на для Пусть фор­му­ла верна для n, тогда для a_n+1 имеем по усло­вию

то есть

и Дис­кри­ми­нант этого квад­рат­но­го урав­не­ния равен

от­ку­да

С учётом огра­ни­че­ния по­лу­ча­ем

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

Ответ:

За­ме­тим, что

Вос­поль­зу­ем­ся би­но­мом Нью­то­на и сгруп­пи­ру­ем все сла­га­е­мые, в ко­то­рых есть 22:

По­сколь­ку каж­дое сла­га­е­мое де­лит­ся на 11, то и все число де­лит­ся на 11.

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

То же самое ре­ше­ние можно из­ло­жить на языке срав­не­ний:

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

До­ка­жем утвер­жде­ние за­да­чи для целых не­от­ри­ца­тель­ных n ин­дук­ци­ей по n.

База. Если то

де­лит­ся на 11.

Пе­ре­ход. Пред­по­ло­жим, что при число

де­лит­ся на 11, и до­ка­жем, что при число

также де­лит­ся на 11.

За­ме­тим, что

Пер­вое сла­га­е­мое в пра­вой части де­лит­ся на 11 по пред­по­ло­же­нию ин­дук­ции, а вто­рое  — по­то­му что со­дер­жит мно­жи­тель 22. Зна­чит, и вся сумма де­лит­ся на 11. Пе­ре­ход до­ка­зан.

За­ме­тим, что

Вос­поль­зу­ем­ся би­но­мом Нью­то­на и сгруп­пи­ру­ем сла­га­е­мые, в ко­то­рых есть 39:

По­сколь­ку каж­дое сла­га­е­мое де­лит­ся на 13, всё число де­лит­ся на 13.

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

То же самое ре­ше­ние можно из­ло­жить на языке срав­не­ний:

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

До­ка­жем утвер­жде­ние за­да­чи для целых не­от­ри­ца­тель­ных n ин­дук­ци­ей по n.

База. Если де­лит­ся на 13.

Пе­ре­ход. Пред­по­ло­жим, что при число

де­лит­ся на 13. До­ка­жем, что при число

также де­лит­ся на 13. За­ме­тим, что

Пер­вое сла­га­е­мое де­лит­ся на 13, так как де­лит­ся на 39, а вто­рое де­лит­ся на 13 по пред­по­ло­же­нию ин­дук­ции. Сле­до­ва­тель­но, вся сумма де­лит­ся на 13.

Обо­зна­чим числа нашей пе­ре­ста­нов­ки слева на­пра­во за a₁, a₂, ..., a_n.

Спо­соб I. Пойдём с конца. По­след­нее число a_n за­бав­ной пе­ре­ста­нов­ки либо боль­ше, либо мень­ше всех чисел мно­же­ства 1, 2, 3, ..., n, сле­до­ва­тель­но, оно равно 1 или n. Пред­по­след­нее число a_n–1 за­бав­ной пе­ре­ста­нов­ки либо боль­ше, либо мень­ше всех чисел мно­же­ства 1, 2, 3, ..., n, кроме a_n, то есть это наи­мень­ший или наи­боль­ший эле­мент во мно­же­стве 1, 2, 3, ..., n−1 или во мно­же­стве 2, 3, ..., n. В каж­дом из слу­ча­ев есть ровно две воз­мож­но­сти вы­бо­ра, ва­ри­ан­ты для двух по­след­них чисел пе­ре­ста­нов­ки вы­гля­дят так Не­слож­но убе­дить­ся, что при любом пер­вые k чисел a₁, a₂, ..., a_k пе­ре­ста­нов­ки об­ра­зу­ют ин­тер­вал из k под­ряд иду­щих чисел из мно­же­ства 1, 2, 3, ..., n, а число a_k яв­ля­ет­ся в этом ин­тер­ва­ле ми­ни­маль­ным или мак­си­маль­ным  — всего две воз­мож­но­сти, кроме са­мо­го пер­во­го числа a₁ для ко­то­ро­го остаётся един­ствен­ная воз­мож­ность. Всего по­лу­ча­ем ровно воз­мож­но­стей вы­бо­ра.

Ответ: 2^n − 1.

Спо­соб II. Пусть a₁  =  m, где m  — одно из чисел 1, 2, ..., n. Любое число a_k мень­шее m, будет по усло­вию также мень­ше и всех чисел, мень­ших m и сто­я­щих левее a_k, по­это­му все числа за­бав­ной пе­ре­ста­нов­ки, мень­шие m об­ра­зу­ют в ней убы­ва­ю­щую под­по­сле­до­ва­тель­ность. Ана­ло­гич­но, все числа, боль­шие m, об­ра­зу­ют в ней воз­рас­та­ю­щую под­по­сле­до­ва­тель­ность. При этом любое вза­им­ное рас­по­ло­же­ние этих под­по­сле­до­ва­тель­но­стей удо­вле­тво­ря­ет усло­вию и при­во­дит к за­бав­ной пе­ре­ста­нов­ке. Сле­до­ва­тель­но, любая за­бав­ная пе­ре­ста­нов­ка пол­но­стью задаётся зна­че­ни­ем её пер­во­го эле­мен­та и но­ме­ра­ми m − 1 мест, на ко­то­рых в убы­ва­ю­щем по­ряд­ке слева на­пра­во рас­по­ло­же­ны числа m – 1, m – 2, ..., 1 среди n − 1 всех чле­нов за­бав­ной пе­ре­ста­нов­ки, кроме пер­во­го. Осталь­ные места ав­то­ма­ти­че­ски за­пол­нят­ся чис­ла­ми m + 1, m + 2, ..., n в по­ряд­ке воз­рас­та­ния. Сле­до­ва­тель­но, при фик­си­ро­ван­ном ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок равно числу со­че­та­ний а общее их ко­ли­че­ство равно сумме

Спо­соб III. Пойдём с на­ча­ла, рас­смот­рим, как ме­ня­ет­ся мно­же­ство пер­вых k чисел за­бав­ной пе­ре­ста­нов­ки при уве­ли­че­нии В ка­че­стве a₁ можно взять любое на­ту­раль­ное число из ин­тер­ва­ла 1, 2, 3, ..., n и Пусть на k-ом шаге уже вы­бра­ны числа a₁, a₂, ..., a_k, обо­зна­чим за m_k и M_k со­от­вет­ствен­но ми­ни­маль­ное и мак­си­маль­ное их них. До­ка­жем, что оче­ред­ное a_k+1 долж­но рав­нять­ся либо m_k − 1, либо m_k + 1. Дей­стви­тель­но, если сразу на­ру­ша­ет­ся усло­вие за­бав­но­сти, так как a_k+1 рас­по­ло­же­но пра­вее m_k и M_k но боль­ше од­но­го из них и мень­ше дру­го­го. Если то число m_k − 1 не вхо­дит в и ещё не ис­поль­зо­ва­но в пе­ре­ста­нов­ке, зна­чит, оно будет рас­по­ло­же­но в ней где-то пра­вее a_k+1 тогда трой­ка на­ру­ша­ет усло­вие за­бав­но­сти, так как при этом m_k − 1 мень­ше m_k, но боль­ше a_k+1, сто­я­щих левее него. Ана­ло­гич­но до­ка­зы­ва­ет­ся, что пред­по­ло­же­ние также на­ру­ша­ет усло­вие за­бав­но­сти. Остаётся толь­ко или

Из до­ка­зан­но­го сле­ду­ет, что для каж­до­го мно­же­ство A_k со­сто­ит из не­ко­то­рых k по­сле­до­ва­тель­ных чисел из ин­тер­ва­ла 1, 2, 3, ..., n и A_k+1 по­лу­ча­ет­ся из него до­бав­ле­ни­ем числа, со­сед­не­го с этим ин­тер­ва­лом слева или спра­ва. Зна­чит, за­бав­ная пе­ре­ста­нов­ка при дан­ном под­хо­де од­но­знач­но задаётся пер­вым чис­лом m, и по­сле­до­ва­тель­но­стью n − 1 до­бав­ле­ния но­во­го числа слева и спра­ва от уже ис­поль­зо­ван­ных, из ко­то­рых m − 1 будут до­бав­ле­ни­ем чисел слева и n − m  — до­бав­ле­ни­ем чисел спра­ва. По­сле­до­ва­тель­ность же до­бав­ле­ний од­но­знач­но опре­де­ля­ет­ся m − 1 но­ме­ра­ми до­бав­ле­ний слева. Сле­до­ва­тель­но, при фик­си­ро­ван­ном пер­вом числе m ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок равно числу со­че­та­ний a общее их ко­ли­че­ство равно сумме

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

Воз­мо­жен сле­ду­ю­щий ва­ри­ант этого ре­ше­ния. До­ка­зы­ва­ет­ся, что или по­это­му на каж­дом шаге раз­ность между M_k и m_k уве­ли­чи­ва­ет­ся не мень­ше, чем на 1. Ко­ли­че­ство шагов равно n − 1, а ито­го­вая раз­ность между M_n и m_n не пре­вос­хо­дит n − 1, зна­чит, на каж­дом шаге она растёт ровно на 1. От­сю­да сразу по­лу­ча­ет­ся, что для каж­до­го мно­же­ство со­сто­ит из не­ко­то­рых k по­сле­до­ва­тель­ных чисел из ин­тер­ва­ла 1, 2, 3, ..., n и A_k+1 по­лу­ча­ет­ся из него до­бав­ле­ни­ем числа, со­сед­не­го с этим ин­тер­ва­лом слева или спра­ва. Далее окон­ча­ние до­ка­за­тель­ства такое же, как в толь­ко что рас­смот­рен­ном.

Спо­соб IV. Ин­дук­ци­ей по n до­ка­жем, что для про­из­воль­но­го n ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок равно 2ⁿ. База ин­дук­ции  — при n  =  1 и n  =  2 оно, оче­вид­но, равно 1  =  2⁰ и 2  =  2¹. Пусть для n чисел утвер­жде­ние верно, рас­смот­рим про­из­воль­ную за­бав­ную пе­ре­ста­нов­ку чисел 1, 2, 3, ..., n, n + 1. Пусть число n + 1 стоит на k-ом слева месте. Если спра­ва от n + 1 стоит не­ко­то­рое число m, то любое число l < m стоит пра­вее m, иначе m будет од­но­вре­мен­но мень­ше n + 1 и боль­ше l, сто­я­щих левее него, что на­ру­ша­ет усло­вие за­бав­но­сти. Пра­вее n + 1 стоят n − k + 1 чисел, мак­си­маль­ное из ко­то­рых не мень­ше n − k + 1, сле­до­ва­тель­но, пра­вее n + 1 стоят в точ­но­сти числа ..., 2, 1 в убы­ва­ю­щем по­ряд­ке. Тогда левее n + 1 в не­ко­то­ром по­ряд­ке рас­по­ло­же­но k − 1 число Оче­вид­но, что усло­вие за­бав­но­сти для них вы­пол­не­но, по­это­му они пред­став­ля­ют собой за­бав­ную пе­ре­ста­нов­ку k − 1 чисел. По пред­по­ло­же­нию ин­дук­ции, при число таких пе­ре­ста­но­вок равно 2^k − 2 числа пра­вее n + 1 рас­по­ла­га­ют­ся един­ствен­ным об­ра­зом, сле­до­ва­тель­но, ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок n + 1 числа, в ко­то­рых n + 1 стоит на месте равно 2^k − 2 Кроме того, если в за­бав­ной пе­ре­ста­нов­ке число n + 1 стоит на пер­вом месте, то, как было по­ка­за­но, она равна Зна­чит, общее ко­ли­че­ство за­бав­ных пе­ре­ста­но­вок n + 1 числа равно сумме

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

Вос­поль­зу­ем­ся ма­те­ма­ти­че­ской ин­дук­ци­ей. Пусть верно при n – 1.

Шаг ин­дук­ции: n. Знаем, что n-я пря­мая может пе­ре­сечь­ся со всеми пря­мы­ми (про­дол­же­ни­я­ми сто­рон), так же до­ба­вит­ся еще и n кус­ков, сле­до­ва­тель­но,

Ответ: на

I. Пусть Легко по­ка­зать, что при при f воз­рас­та­ет, когда x из­ме­ня­ет­ся от 0 до e, и f убы­ва­ет, когда x из­ме­ня­ет­ся от e до Сле­до­ва­тель­но, мак­си­маль­ное зна­че­ние, ве­ли­чин f(k), где равно По­сколь­ку от­ку­да Тогда для всех по­ло­жи­тель­ных целых m. Если то сле­до­ва­тель­но,

II. Пред­по­ло­жим сна­ча­ла, что тогда нам нужно до­ка­зать, что или что Но по­след­нее не­ра­вен­ство легко до­ка­зать при по­мо­щью ма­те­ма­ти­че­ской ин­дук­ции. Дей­стви­тель­но,

Но это вы­ра­же­ние боль­ше при Слу­чаи три­ви­аль­ны.

Далее пред­по­ло­жим, что Тогда

Ответ:

За­ме­тим, что если в куче не­чет­ное число кам­ней, то пер­вый игрок га­ран­ти­ру­ет себе по­бе­ду, взяв на пер­вом ходу 1 ка­мень: тогда каж­дым сле­ду­ю­щим ходом иг­ро­ки будут за­би­рать по од­но­му камню, и по­след­ний ка­мень за­бе­рет пер­вый игрок. Когда n чётно, тот, кто пер­вым сде­ла­ет не­чет­ный шаг, про­иг­ра­ет: такой шаг был сде­лан из чет­но­го числа  — зна­чит, он не будет по­след­ним, а про­тив­ник за­бе­рет один ка­мень, что и обес­пе­чит ему по­бе­ду.

Если то вто­рой игрок, оче­вид­но, по­беж­да­ет. Если то по­беж­да­ет пер­вый игрок, за­би­рая пер­вым ходом 1 ка­мень. Если то по­беж­да­ет вто­рой игрок: если пер­вый берет 1 ка­мень, то вто­рой возь­мет по­след­ний ка­мень, а если пер­вый игрок пер­вым ходом берет 2 или 3 камня, то вто­рой игрок пер­вым своим ходом за­би­ра­ет осталь­ные камни.

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

Пусть те­перь для Тогда уже вто­рой игрок при­ме­ня­ет стра­те­гию «по­ло­вин­ча­той», то есть берет в 2 раза боль­ше кам­ней, чем взял бы в игре с кам­ня­ми. Со­глас­но пред­по­ло­же­нию ин­дук­ции, это обес­пе­чит ему по­бе­ду.

Note, that if there is an odd number of stones in the pile, then the first player guarantees himself a victory by taking 1 stone on the first move: then each next move the players will take 1 stone, and the last stone will be taken by the first player. When n is even, the first one to make an odd step will lose: such a step was made from an even number - so it will not be the last one, and the opponent will immediately take 1 stone, which will ensure his victory.

If then the second player wins obviously. If then the first player wins by taking 1 stone on the first move. If then the second player wins: if the first player takes 1 stone, then the second player takes the last stone, and if the first player takes 2 or 3 stones on the first move, then the second player takes the remaining ones.

Lets prove by induction that for all even n from to (while is an integer) the first player wins, and for so does the second player. The base of induction has been shown above.

Let for integer Then the first player reduces the game to that with stones (i. e. he takes twice as many stones as he would take in the game with stones), where he has a winning strategy according to the induction hypothesis, since The only way to stop him is to take an odd number of stones, but as shown above, whoever is the first to take an odd number of stones loses.

Let now for Then the second player applies his strategy of the game with stones, i. e. he takes 2 times more stones than he would take in the game with stones. According to the induction hypothesis, this will ensure his victory.

Ответ: при (для вто­рой игрок может га­ран­ти­ро­вать себе по­бе­ду. При про­чих вы­иг­рыш­ная стра­те­гия есть у пер­во­го иг­ро­ка.