Обо­зна­чим через S_n мно­же­ство всех тре­бу­е­мых рас­ста­но­вок для таб­ли­цы n × n. Тогда f (n) по опре­де­ле­нию равно ко­ли­че­ству эле­мен­тов в мно­же­стве S_n. Введём опе­ра­цию g над таб­ли­цей, за­клю­ча­ю­щу­ю­ся в уда­ле­нии по­след­не­го (край­не­го пра­во­го) столб­ца и по­след­ней (край­ней ниж­ней) стро­ки таб­ли­цы. При­мер:

Оче­вид­но, если то

а)  Мы до­ка­жем, что отоб­ра­же­ние яв­ля­ет­ся инъ­ек­тив­ным (смысл тер­ми­на будет разъ­яснён далее), и при этом его образ не по­кры­ва­ет всего мно­же­ства S₉. От­сю­да будет сле­до­вать тре­бу­е­мое не­ра­вен­ство.

Утвер­жде­ние 1. Пусть дана таб­ли­ца Тогда су­ще­ству­ет не более одной таб­ли­цы такой, что

До­ка­за­тель­ство. Будем вос­ста­нав­ли­вать таб­ли­цу x по из­вест­ной таб­ли­це

Для на­гляд­но­сти изоб­ра­зим обе таб­ли­цы сле­ду­ю­щим об­ра­зом:

Т. е. пусть по­след­ний стол­бец таб­ли­цы x со­дер­жит не­из­вест­ные числа по­след­няя стро­ка со­дер­жит не­из­вест­ные числа

Число a_i долж­но от­ли­чать­ся от всех чисел в стро­ке с но­ме­ром i таб­ли­цы y. Но в любой стро­ке таб­ли­цы y стоят 9 раз­лич­ных чисел из мно­же­ства т. е. для a_i остаётся един­ствен­ное воз­мож­ное зна­че­ние. Сле­до­ва­тель­но, все числа од­но­знач­но опре­де­ля­ют­ся по таб­ли­це y. Ана­ло­гич­но, рас­смат­ри­вая столб­цы, од­но­знач­но вос­ста­нав­ли­ва­ем числа b_j.

Если среди вос­ста­нов­лен­ных чисел есть оди­на­ко­вые, по­лу­ча­ем про­ти­во­ре­чие с усло­ви­ем, и, сле­до­ва­тель­но, таб­ли­цы x, удо­вле­тво­ря­ю­щей ра­вен­ству не

су­ще­ству­ет. Если же все a_i раз­лич­ны, и все b_j раз­лич­ны, то число c долж­но от­ли­чать­ся от них всех, и такое число тоже един­ствен­но.

Итак, если таб­ли­ца x су­ще­ству­ет, то она един­ствен­на, что и тре­бо­ва­лось.

След­ствие: если и то (Отоб­ра­же­ние g с таким свой­ством в ма­те­ма­ти­ке на­зы­ва­ет­ся инъ­ек­тив­ным).

Утвер­жде­ние 2. Су­ще­ству­ет таб­ли­ца такая, что любое

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

Вос­ста­нав­ли­вая по ней таб­ли­цу x так же, как то сде­ла­но выше, мы по­лу­ча­ем что про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, ис­ко­мой таб­ли­цы x не су­ще­ству­ет.

Из до­ка­зан­ных утвер­жде­ний сле­ду­ет, что в мно­же­стве S₉ боль­ше эле­мен­тов, чем в S₁₀, т. е.

Про­ил­лю­стри­ру­ем на­гляд­но по­след­ний шаг рас­суж­де­ния. Пред­по­ло­жим, что мы вы­пи­са­ли в ряд все воз­мож­ные таб­ли­цы из мно­же­ства S₁₀. Рас­смот­рим сле­ду­ю­щую диа­грам­му отоб­ра­же­ния g:

В мно­же­стве S₁₀ ровно K эле­мен­тов, и все они вы­пи­са­ны в верх­нем ряду. В ниж­нем ряду для каж­дой таб­ли­цы x вы­пи­са­на со­от­вет­ству­ю­щая таб­ли­ца g(x), а также по­стро­ен­ная в утвер­жде­нии 2 таб­ли­ца y. Все таб­ли­цы в ниж­нем ряду при­над­ле­жат мно­же­ству S₉, и все они по до­ка­зан­но­му раз­лич­ны. Сле­до­ва­тель­но, ко­ли­че­ство таб­лиц в мно­же­стве S₉ боль­ше, чем в S₁₀.

б)  До­ка­жем, что при отоб­ра­же­нии в каж­дую таб­ли­цу мно­же­ства S₅ отоб­ра­жа­ет­ся более одной таб­ли­цы мно­же­ства S₆. От­сю­да будет сле­до­вать тре­бу­е­мое не­ра­вен­ство.

Утвер­жде­ние 3. Пусть дана таб­ли­ца y S₅. Тогда су­ще­ству­ет не менее 4 раз­лич­ных таб­лиц таких, что

До­ка­за­тель­ство. Так же, как в п. а), изоб­ра­зим на­гляд­но ра­вен­ство :

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

В объ­еди­не­нии пер­вой стро­ки и пер­во­го столб­ца таб­ли­цы y на­пи­са­но 9 чисел (не­обя­за­тель­но все раз­лич­ные), по тому су­ще­ству­ет число из мно­же­ства ко­то­ро­го нет ни в пер­вой стро­ке, ни в пер­вом столб­це таб­ли­цы y. По­ло­жим a₁ и b₁ рав­ны­ми тому числу. Т. е. со­глас­но на­ше­му вы­бо­ру a₁ = b₁.

Для будем по­сле­до­ва­тель­но вы­би­рать числа a_i так, чтобы число a_i не рав­ня­лось ни од­но­му из чисел в i-й стро­ке таб­ли­цы y, а также не рав­ня­лось уже вы­бран­ным чис­лам Такой выбор все­гда су­ще­ству­ет, т. к. "за­прещёнными" ока­зы­ва­ют­ся все­гда не более 5 + 4 = 9 чисел.

Ана­ло­гич­но для будем по­сле­до­ва­тель­но вы­би­рать числа b_j так, чтобы число b_j не рав­ня­лось ни од­но­му из чисел в j-м столб­це таб­ли­цы y, а также не рав­ня­лось чис­лам

Мы из­на­чаль­но вы­бра­ли a₁ = b₁, по­это­му среди чисел a_i, b_j, i, j = 1 . . . 5, не более 9 раз­лич­ных. По тому можно вы­брать число c от­лич­ным от них всех, и тем самым за­вер­шить по­стро­е­ние таб­ли­цы x. По­стро­ен­ная таб­ли­ца x удо­вле­тво­ря­ет всем усло­ви­ям за­да­чи и при­над­ле­жит мно­же­ству S₆, при том

За­ме­тим, что при вы­бо­ре числа a₂ за­прещёнными были не более 6 чисел (числа во вто­рой стро­ке таб­ли­цы y и число a₁). По­это­му име­лось не менее 4 спо­со­бов вы­брать число a₂, и все они при­ве­ли бы к раз­лич­ным таб­ли­цам x. Сле­до­ва­тель­но, таких таб­лиц x, для ко­то­рых не менее 4, что и тре­бо­ва­лось до­ка­зать.

Ответ: а) f (9) > f (10), б) f (6) > f (5).

Обо­зна­чим через S_n мно­же­ство всех тре­бу­е­мых рас­ста­но­вок для таб­ли­цы n × n. Тогда f (n) по опре­де­ле­нию равно ко­ли­че­ству эле­мен­тов в мно­же­стве S_n. Введём опе­ра­цию g над таб­ли­цей, за­клю­ча­ю­щу­ю­ся в уда­ле­нии по­след­не­го (край­не­го пра­во­го) столб­ца и по­след­ней (край­ней ниж­ней) стро­ки таб­ли­цы. При­мер:

Оче­вид­но, если то

а)  Мы до­ка­жем, что отоб­ра­же­ние яв­ля­ет­ся инъ­ек­тив­ным (смысл тер­ми­на будет разъ­яснён далее), и при этом его образ не по­кры­ва­ет всего мно­же­ства S₂₀₁₅. От­сю­да будет сле­до­вать тре­бу­е­мое не­ра­вен­ство.

Утвер­жде­ние 1. Пусть дана таб­ли­ца Тогда су­ще­ству­ет не более одной таб­ли­цы такой, что

До­ка­за­тель­ство. Будем вос­ста­нав­ли­вать таб­ли­цу x по из­вест­ной таб­ли­це

Для на­гляд­но­сти изоб­ра­зим обе таб­ли­цы сле­ду­ю­щим об­ра­зом:

Т. е. пусть по­след­ний стол­бец таб­ли­цы x со­дер­жит не­из­вест­ные числа по­след­няя стро­ка со­дер­жит не­из­вест­ные числа

Число a_i долж­но от­ли­чать­ся от всех чисел в стро­ке с но­ме­ром i таб­ли­цы y. Но в любой стро­ке таб­ли­цы y стоят 2015 раз­лич­ных чисел из мно­же­ства т. е. для a_i остаётся един­ствен­ное воз­мож­ное зна­че­ние. Сле­до­ва­тель­но, все числа од­но­знач­но опре­де­ля­ют­ся по таб­ли­це y. Ана­ло­гич­но, рас­смат­ри­вая столб­цы, од­но­знач­но вос­ста­нав­ли­ва­ем числа b_j.

Если среди вос­ста­нов­лен­ных чисел есть оди­на­ко­вые, по­лу­ча­ем про­ти­во­ре­чие с усло­ви­ем, и, сле­до­ва­тель­но, таб­ли­цы x, удо­вле­тво­ря­ю­щей ра­вен­ству не

су­ще­ству­ет. Если же все a_i раз­лич­ны, и все b_j раз­лич­ны, то число c долж­но от­ли­чать­ся от них всех, и такое число тоже един­ствен­но.

Итак, если таб­ли­ца x су­ще­ству­ет, то она един­ствен­на, что и тре­бо­ва­лось.

След­ствие: если и то (Отоб­ра­же­ние g с таким свой­ством в ма­те­ма­ти­ке на­зы­ва­ет­ся инъ­ек­тив­ным).

Утвер­жде­ние 2. Су­ще­ству­ет таб­ли­ца такая, что любое

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

Вос­ста­нав­ли­вая по ней таб­ли­цу x так же, как то сде­ла­но выше, мы по­лу­ча­ем что про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, ис­ко­мой таб­ли­цы x не су­ще­ству­ет.

Из до­ка­зан­ных утвер­жде­ний сле­ду­ет, что в мно­же­стве S₂₀₁₅ боль­ше эле­мен­тов, чем в S₂₀₁₆, т. е.

Про­ил­лю­стри­ру­ем на­гляд­но по­след­ний шаг рас­суж­де­ния. Пред­по­ло­жим, что мы вы­пи­са­ли в ряд все воз­мож­ные таб­ли­цы из мно­же­ства S₂₀₁₆. Рас­смот­рим сле­ду­ю­щую диа­грам­му отоб­ра­же­ния g:

В мно­же­стве S₂₀₁₆ ровно K эле­мен­тов, и все они вы­пи­са­ны в верх­нем ряду. В ниж­нем ряду для каж­дой таб­ли­цы x вы­пи­са­на со­от­вет­ству­ю­щая таб­ли­ца g(x), а также по­стро­ен­ная в утвер­жде­нии 2 таб­ли­ца y. Все таб­ли­цы в ниж­нем ряду при­над­ле­жат мно­же­ству S₂₀₁₅, и все они по до­ка­зан­но­му раз­лич­ны. Сле­до­ва­тель­но, ко­ли­че­ство таб­лиц в мно­же­стве S₂₀₁₅ боль­ше, чем в S₂₀₁₆.

б)  До­ка­жем, что при отоб­ра­же­нии в каж­дую таб­ли­цу мно­же­ства S₁₀₀₈ отоб­ра­жа­ет­ся более одной таб­ли­цы мно­же­ства S₁₀₀₉. От­сю­да будет сле­до­вать тре­бу­е­мое не­ра­вен­ство.

Утвер­жде­ние 3. Пусть дана таб­ли­ца y S₁₀₀₈. Тогда су­ще­ству­ет не менее 1007 раз­лич­ных таб­лиц таких, что

До­ка­за­тель­ство. Так же, как в п. а), изоб­ра­зим на­гляд­но ра­вен­ство :

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

В объ­еди­не­нии пер­вой стро­ки и пер­во­го столб­ца таб­ли­цы y на­пи­са­но 2015 чисел (не­обя­за­тель­но все раз­лич­ные), по тому су­ще­ству­ет число из мно­же­ства ко­то­ро­го нет ни в пер­вой стро­ке, ни в пер­вом столб­це таб­ли­цы y. По­ло­жим a₁ и b₁ рав­ны­ми тому числу. Т. е. со­глас­но на­ше­му вы­бо­ру a₁ = b₁.

Для будем по­сле­до­ва­тель­но вы­би­рать числа a_i так, чтобы число a_i не рав­ня­лось ни од­но­му из чисел в i-й стро­ке таб­ли­цы y, а также не рав­ня­лось уже вы­бран­ным чис­лам Такой выбор все­гда су­ще­ству­ет, т. к. "за­прещёнными" ока­зы­ва­ют­ся все­гда не более 1008 + 1007 = 2015 чисел.

Ана­ло­гич­но для будем по­сле­до­ва­тель­но вы­би­рать числа b_j так, чтобы число b_j не рав­ня­лось ни од­но­му из чисел в j-м столб­це таб­ли­цы y, а также не рав­ня­лось чис­лам

Мы из­на­чаль­но вы­бра­ли a₁ = b₁, по­это­му среди чисел a_i, b_j, i, j = 1 . . . 1008, не более 2015 раз­лич­ных. По тому можно вы­брать число c от­лич­ным от них всех, и тем самым за­вер­шить по­стро­е­ние таб­ли­цы x. По­стро­ен­ная таб­ли­ца x удо­вле­тво­ря­ет всем усло­ви­ям за­да­чи и при­над­ле­жит мно­же­ству S₁₀₀₉, при том

За­ме­тим, что при вы­бо­ре числа a₂ за­прещёнными были не более 1009 чисел (числа во вто­рой стро­ке таб­ли­цы y и число a₁). По­это­му име­лось не менее 1007 спо­со­бов вы­брать число a₂, и все они при­ве­ли бы к раз­лич­ным таб­ли­цам x. Сле­до­ва­тель­но, таких таб­лиц x, для ко­то­рых не менее 1007, что и тре­бо­ва­лось до­ка­зать.

Ответ: а) f (2015) > f (2016), б) f (1009) > f (1008).

Разобьём слова, на­пи­сан­ные на доске на 4 клас­са U, D, L, R со­глас­но пер­вой букве (будем ма­лень­ки­ми бук­ва­ми u, d, l, r обо­зна­чать число эле­мен­тов в них, u + d + l + r  =  1 000 000). Тогда в тет­ра­ди уче­ни­ка U будет на­пи­са­но u + l + r слов, на­чи­на­ю­щих­ся на вверх (ибо к лю­бо­му слову не из клас­са D он при­пи­шет "вверх"). Зна­чит, если у него в тет­ра­ди со­дер­жит­ся N_u новых слов, то На­пи­сав три ана­ло­гич­ных не­ра­вен­ства и сло­жив их вме­сте, по­лу­чим, что

то есть не мень­ше 2 000 000.

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

Речь, ко­неч­но, идёт о не­со­кра­ти­мых сло­вах в сво­бод­ной груп­пе с двумя об­ра­зу­ю­щи­ми. Тогда утвер­жда­ет­ся, что какое бы (ко­неч­ное) под­мно­же­ство в этой груп­пе мы не взяли, при его умно­же­нии на a, b, a − 1, b − 1 хотя бы раз мы по­лу­чим силь­но дру­гое мно­же­ство.

Если бы вна­ча­ле на доске было на­пи­са­но не сто, а три числа: a, b, c, то в конце на доске было бы на­пи­са­но число abc + ab + bc + ac + a + b + c. То есть сумма всех воз­мож­ных мо­но­мов, со­став­лен­ных из чисел a, b, c, взя­тых не боль­ше, чем по од­но­му разу.

В слу­чае, когда на доске на­пи­са­но сто чисел. Легко ви­деть, что по­след­ним на доске оста­нет­ся число, пред­ста­ви­мое в виде суммы раз­лич­ных мо­но­мов вида для все­воз­мож­ных на­ту­раль­ных чисел и при этом для всех i. Школь­ни­ки долж­ны будут это до­ка­зы­вать.

Те­перь за­ме­тим, что эта сумма пред­ста­ви­ма в виде:

Пре­об­ра­зу­ем её:

Ответ: 100.

Разобьём слова, на­пи­сан­ные на доске на 4 клас­са U, D, L, R со­глас­но пер­вой букве (будем ма­лень­ки­ми бук­ва­ми u, d, l, r обо­зна­чать число эле­мен­тов в них, u + d + l + r  =  1 000 000). Тогда в тет­ра­ди уче­ни­ка U будет на­пи­са­но u + l + r слов, на­чи­на­ю­щих­ся на вверх (ибо к лю­бо­му слову не из клас­са D он при­пи­шет "вверх"). Зна­чит, если у него в тет­ра­ди со­дер­жит­ся N_u новых слов, то На­пи­сав три ана­ло­гич­ных не­ра­вен­ства и сло­жив их вме­сте, по­лу­чим, что

то есть не мень­ше 2 000 000.

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

Речь, ко­неч­но, идёт о не­со­кра­ти­мых сло­вах в сво­бод­ной груп­пе с двумя об­ра­зу­ю­щи­ми. Тогда утвер­жда­ет­ся, что какое бы (ко­неч­ное) под­мно­же­ство в этой груп­пе мы не взяли, при его умно­же­нии на a, b, a − 1, b − 1 хотя бы раз мы по­лу­чим силь­но дру­гое мно­же­ство.

До­ка­жем, что до­рас­ста­вить тре­бу­е­мым об­ра­зом фо­на­ри можно.

Раз­де­лим синие фо­на­ри на два вида  — освещённые дру­ги­ми и нет. Пусть не­освещённые имеют ко­ор­ди­на­ты (x₁, y₁), . . . , (x_n, y_n). Все x-ко­ор­ди­на­ты раз­лич­ны, так как иначе бы какой-то из фо­на­рей осве­щал бы какой-то дру­гой. Тогда можно счи­тать, что x₁ < . . . < x_n. Тогда y₁ > . . . > y_n, так как иначе бы какой-то из этих фо­на­рей осве­щал бы какой-то дру­гой.

Рас­ста­вим крас­ные фо­на­ри в точки (x₁, y₂), (x₂, y₃), . . . , (x_{n − 1}, y_n), а также во все точки, где стоят освещённые дру­ги­ми си­ни­ми фо­на­ря­ми синие фо­на­ри.

Рас­смот­рим про­из­вод­ную точку плос­ко­сти. Если она не осве­ща­лась ни одним синим фонарём, то не будет осве­щать­ся ни одним крас­ным. Если она осве­ща­ет­ся хотя бы одним синим, то осве­ща­ет­ся хотя бы одним синим, ко­то­рый не осве­ща­ет­ся дру­ги­ми си­ни­ми. Тогда для вы­бран­ной точки

• ко­ли­че­ство синих, освещённых дру­ги­ми си­ни­ми и осве­ща­ю­щих дан­ную точку, со­хра­нит­ся;

• ко­ли­че­ство синих, не освещённых дру­ги­ми си­ни­ми и осве­ща­ю­щих дан­ную точку, умень­шит­ся на 1.

Таким об­ра­зом, най­ден­ная нами рас­ста­нов­ка яв­ля­ет­ся тре­бу­е­мой.

На самом деле дан­ная рас­ста­нов­ка яв­ля­ет­ся един­ствен­ной.

Ответ: да, можно.

До­ка­жем, что до­рас­ста­вить тре­бу­е­мым об­ра­зом фо­на­ри можно.

Раз­де­лим синие фо­на­ри на два вида  — освещённые дру­ги­ми и нет. Пусть не­освещённые имеют ко­ор­ди­на­ты (x₁, y₁), . . . , (x_n, y_n). Все x-ко­ор­ди­на­ты раз­лич­ны, так как иначе бы какой-то из фо­на­рей осве­щал бы какой-то дру­гой. Тогда можно счи­тать, что x₁ < . . . < x_n. Тогда y₁ > . . . > y_n, так как иначе бы какой-то из этих фо­на­рей осве­щал бы какой-то дру­гой.

Рас­ста­вим крас­ные фо­на­ри в точки (x₁, y₂), (x₂, y₃), . . . , (x_{n − 1}, y_n), а также во все точки, где стоят освещённые дру­ги­ми си­ни­ми фо­на­ря­ми синие фо­на­ри.

Рас­смот­рим про­из­вод­ную точку плос­ко­сти. Если она не осве­ща­лась ни одним синим фонарём, то не будет осве­щать­ся ни одним крас­ным. Если она осве­ща­ет­ся хотя бы одним синим, то осве­ща­ет­ся хотя бы одним синим, ко­то­рый не осве­ща­ет­ся дру­ги­ми си­ни­ми. Тогда для вы­бран­ной точки

• ко­ли­че­ство синих, освещённых дру­ги­ми си­ни­ми и осве­ща­ю­щих дан­ную точку, со­хра­нит­ся;

• ко­ли­че­ство синих, не освещённых дру­ги­ми си­ни­ми и осве­ща­ю­щих дан­ную точку, умень­шит­ся на 1.

Таким об­ра­зом, най­ден­ная нами рас­ста­нов­ка яв­ля­ет­ся тре­бу­е­мой.

На самом деле дан­ная рас­ста­нов­ка яв­ля­ет­ся един­ствен­ной.

Ответ: да, можно.

Пусть   — ко­ли­че­ство ше­сти­знач­ных чисел, ко­то­рые можно со­ста­вить из на­бо­ра цифр

По­лу­ча­ем, что

Ответ: 233 200.

Будем ме­нять ме­ста­ми 1 и 2, 2 и 3, 3 и 4, ... 500 и 501. Ясно, что тут встре­ча­ют­ся шары из обоих со­су­дов. Пусть k,   — пер­вая пара со­сед­них шаров из раз­ных со­су­дов. Тогда мы их дей­стви­тель­но по­ме­ня­ем, а даль­ше k ме­нять­ся ни с кем не будет.

Разо­бьем почти все шары на трой­ки. В каж­дой трой­ке (a, b, c) при­ка­жем по­ме­нять сна­ча­ла a с b, потом b с c. Если все они были в раз­ных со­су­дах, то все они по­ме­ня­ют сосуд, если два из них были в одном со­су­де, то по­ме­ня­ют сосуд два из трёх (на­при­мер, можно разо­брать все три слу­чая). В итоге по­ме­ня­ет­ся силь­но боль­ше по­ло­ви­ны шаров (почти две трети).

Будем пред­став­лять, что внут­ри со­су­ды раз­де­ле­ны на ячей­ки и в каж­дой лежит по шару. Тогда мы можем пред­став­лять, что (не­за­ви­си­мо от на­хож­де­ния в одном со­су­де или в раз­ных) шары i и j про­сто ме­ня­ют­ся ячей­ка­ми по ко­ман­де (ij). Таким об­ра­зом, любая по­сле­до­ва­тель­ность ко­манд осу­ществ­ля­ет про­сто фик­си­ро­ван­ную пе­ре­ста­нов­ку шаров в ячей­ках. (От­ме­тим, что транс­по­зи­ции поз­во­ля­ют сде­лать любую пе­ре­ста­нов­ку). Сде­ла­ем пе­ре­ста­нов­ку типа «куча цик­лов по 3 и один по 5», тогда в каж­дом цикле 3 ми­ни­мум двое по­ме­ня­ют при­над­леж­ность, в цикле длины 5  — ми­ни­мум трое. Итого 533. Боль­ше га­ран­ти­ро­вать никак нель­зя  — в цикле длины k мы можем га­ран­ти­ро­вать мак­си­мум

смен при­над­леж­но­стей (цикл может со­сто­ять как раз из пар шаров-со­се­дей (сто­я­щих рядом на цикле) +, воз­мож­но, один не­пар­ный шар), а две трети от 800 мень­ше 534.

Ответ: 533.

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

При дву­крат­ном при­ме­не­нии цик­ли­че­ской пе­ре­ста­нов­ки с чет­ной дли­ной цикла по­лу­ча­ет­ся пе­ре­ста­нов­ка, со­сто­я­щая из двух цик­лов по­ло­вин­ной длины. Так как 800 не де­лит­ся на 64, то длина од­но­го из цик­лов тоже не де­лит­ся на 64. Тогда, деля этот цикл на два не более пяти раз (т. е. по­вто­ряя не более раз ис­ход­ную по­сле­до­ва­тель­ность ко­манд) мы по­лу­чим цикл не­чет­ной длины  — в этот мо­мент га­ран­ти­ро­ван­но хотя бы один шар ока­жет­ся в род­ном со­су­де. Ясно, что мень­ше, чем 32 по­вто­ре­ни­я­ми от­де­лать­ся нель­зя. На­при­мер, если ис­ход­ная пе­ре­ста­нов­ка  — цикл длины 800, то его l  — крат­ное при­ме­не­ние даст кучу цик­лов длины   — это число при четно, так что такой набор цик­лов впол­не цик­лов длины   — это число при четно, так что такой набор цик­лов впол­не до­пус­ка­ет ис­ход­ный рас­клад, ко­то­рый под дей­стви­ем дан­ной пе­ре­ста­нов­ки пре­вра­тит­ся в свою про­ти­во­по­лож­ность.

Ответ: 32.

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

Для дан­ной рас­ста­нов­ки рас­смот­рим по­лу­ча­е­мую из неё рас­ста­нов­ку с наи­мень­шим воз­мож­ным ко­ли­че­ством чер­ных кле­ток. По преды­ду­ще­му пунк­ту, между лю­бы­ми двумя чер­ны­ми не менее четырёх белых. Пре­об­ра­зо­вы­ва­ем пятёрку ЧББББ: ЧББББ, БЧЧББ, БЧБЧЧ, ББББЧ. Таким об­ра­зом, любую чер­ную фишку можно сдви­нуть на 4 по­зи­ции, и если чер­ных фишек боль­ше одной, до­бить­ся–таки того, чтобы рас­сто­я­ние между чер­ны­ми было мень­ше че­ты­рех, после чего умень­шим их ко­ли­че­ство  — про­ти­во­ре­чие.

Если же чер­ная фишка всего одна, на­при­мер, на по­зи­ции 1 (про­ну­ме­ру­ем по­зи­ции про­тив ча­со­вой стрел­ки), при­ме­ним первую опе­ра­цию к по­зи­ци­ям 2 и 4, после чего нач­нем сдви­гать чёрную фишку на по­зи­ции 4 впра­во на че­ты­ре по­зи­ции, как в про­шлом аб­за­це, и при­го­ним её на по­зи­цию 2016. Те­перь все чёрные фишки со­дер­жат­ся во фраг­мен­те ЧББЧЧ, и мы его пре­об­ра­зу­ем: ЧББЧЧ,ЧБЧББ, БББББ.

По­кра­сим в три цвета по­зи­ции; чет­но­сти ко­ли­честв чер­ных на всех по­зи­ци­ях ме­ня­ют­ся од­но­вре­мен­но. С фик­си­ро­ван­ным на­бо­ром чет­но­стей ровно 2¹² рас­ста­но­вок, с фик­си­ро­ван­ным с точ­но­стью до ин­вер­сии  —

Нель­зя. Пусть если на i-ой по­зи­ции стоит белая фишка и иначе. Рас­смот­рим сумму по мо­ду­лю 5  — она кор­рект­но опре­де­ле­на, т. к. остат­ки по мо­ду­лю 5 по­вто­ря­ют­ся с пе­ри­о­дом 4, а 1000 де­лит­ся на 4. Пер­вая опе­ра­ция до­бав­ля­ет или вы­чи­та­ет из суммы вто­рая:

Tо есть эта сумма яв­ля­ет­ся ин­ва­ри­ан­том, но для белой рас­ста­нов­ки она равна нулю, а для рас­ста­нов­ки с одной чер­ной  — не равна.

Ответ: нет, нель­зя.

Пусть окра­ше­но n чисел. Упо­ря­до­чим их по воз­рас­та­нию:

За­ме­тим, что для лю­бо­го спра­вед­ли­во не­ра­вен­ство Дей­стви­тель­но, в про­тив­ном слу­чае при имеем

и мы не смо­жем пред­ста­вить a_k в виде суммы двух крас­ных чисел. Тогда

Зна­чит, и Оста­лось при­ве­сти при­мер по­крас­ки 10 чисел: 1, 2, 4, 5, 10, 20, 40, 80, 160, 320.

Ответ: 10.

Так как

то

Ана­ло­гич­но

Таким об­ра­зом, по­лу­ча­ет­ся, что в пре­де­лах от 2 до на­хо­дит­ся на­ту­раль­ных чисел и Зна­чит, какие-то два из них не­пре­мен­но сов­па­да­ют. Но числа все раз­лич­ны  — среди них нет сов­па­де­ний, ана­ло­гич­но нет сов­па­де­ний среди чисел По­это­му сов­па­да­ют какие-то два числа и

Ответ: да, верно.

По­сколь­ку все суммы раз­ные, все числа тоже раз­ные. Упо­ря­до­чим эти числа в по­ряд­ке воз­рас­та­ния и обо­зна­чим сле­ду­ю­щим об­ра­зом:

Тогда

Кроме того,

зна­чит

Решая си­сте­му, по­сле­до­ва­тель­но на­хо­дим

от­сю­да:

Ответ: 2, 5, 7, 14, 15.

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

Рас­смот­рим фишку с но­ме­ром n: вна­ча­ле у неё ко­ор­ди­на­та рав­ня­лась n, а в конце стала равна 1. По­это­му n – 1 де­лит­ся на 3. Ана­ло­гич­но, рас­смот­рим фишку с но­ме­ром n – 1: в конце у неё ко­ор­ди­на­та стала равна 2 и по­это­му n – 1 – 2 де­лит­ся на 3, то есть n долж­но быть крат­но 3  — про­ти­во­ре­чие.

Ответ: не су­ще­ству­ет.

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

По срав­не­нию с при­ве­ден­ном ре­ше­ни­ем здесь име­ет­ся до­пол­ни­тель­ная воз­мож­ность пе­ре­став­лять ме­ста­ми две фишки, между ко­то­ры­ми пять фишек. Это поз­во­ля­ет из­ме­нять ко­ор­ди­на­ты на 6 еди­ниц, но эта до­пол­ни­тель­ная воз­мож­ность не ме­ня­ет остат­ка при де­ле­нии на 3 ко­ор­ди­на­ты фишки, по­это­му выше при­ве­ден­ное до­ка­за­тель­ство за­да­чи остаётся в силе.