За­ну­ме­ру­ем клет­ки как по­ка­за­но на ри­сун­ке 1. Конь может из любой клет­ки по­пасть в любую клет­ку с таким же но­ме­ром, и не может по­пасть в дру­гие.

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

До­ба­вим две клет­ки как на ри­сун­ке 2. До­ка­жем, что те­перь конь может по­пасть из любой клет­ки в любую дру­гую. Клет­ка А со­еди­ня­ет клет­ки, от­ме­чен­ные ро­зо­вым цве­том, т. е. через ней можно из мно­же­ства 1 пе­ре­ско­чить в мно­же­ство 4. (На­хо­дясь в любой клет­ке с но­ме­ром 1, можно прий­ти в ро­зо­вую клет­ку с но­ме­ром 1, затем через A по­пасть в ро­зо­вую клет­ку с но­ме­ром 4, и из ней в любую клет­ку с но­ме­ром 4. В итоге из любой клет­ки с но­ме­ром 1 можно с по­мо­щью А по­пасть в любую клет­ку с но­ме­ром 4.)

Клет­ка В со­еди­ня­ет клет­ки, от­ме­чен­ные зелёным, т. е. через ней можно из лю­бо­го из мно­жеств 2, 3, 4 пе­ре­ско­чить так же в любое из этих мно­жеств.

В итоге, со­че­тая клет­ки A, B, можно из лю­бо­го мно­же­ства по­пасть в любое дру­гое. На­при­мер чтобы по­пасть из мно­же­ства 1 в мно­же­ство 2, вна­ча­ле с по­мо­щью А по­па­да­ем из 1 в 4, затем с по­мо­щью В по­па­да­ем из 4 в 2.

Оста­лось убе­дить­ся, что одной клет­ки не хва­тит. Из ри­сун­ка 3 видно, что все до­бав­ля­е­мые клет­ки раз­би­ва­ют­ся на два вида: в клет­ки А можно по­пасть не боль­ше чем из 3 кле­ток доски, в клет­ки В можно по­пасть из 4-х кле­ток, но среди них все­гда есть две из од­но­го мно­же­ства (от­ме­чен­ные оди­на­ко­вой циф­рой). Т. е. клет­ки, в ко­то­рую можно по­пасть из всех 4-х мно­жеств, не су­ще­ству­ет.

Ответ: 2.

Всего в стро­ке и столб­це, про­хо­дя­щих через дан­ную клет­ку 19 кле­ток, по­это­му, если мы про­де­ла­ем опе­ра­ции со всеми па­ра­ми строк и столб­цов таб­ли­цы (всего опе­ра­ций), то каж­дый знак в таб­ли­це по­ме­ня­ет­ся 19 раз, став из ми­ну­са плю­сом, по­это­му 100 опе­ра­ций до­ста­точ­но.

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

Стро­ки и столб­цы, со­дер­жа­щие чётное число крас­ных кле­ток назовём чётными, а со­дер­жа­щие нечётное число крас­ных кле­ток  — нечётными. До­пу­стим, можно по­ме­нять все знаки в таб­ли­це мень­ше чем за 100 опе­ра­ций, тогда рас­смот­рим не­ко­то­рую синюю клет­ку А в стро­ке Х и столб­це Y. Чтобы знак в А по­ме­нял­ся, нужно, чтобы, чтобы Х и Y вме­сте со­дер­жа­ли нечётное ко­ли­че­ство крас­ных кле­ток, можно счи­тать стро­ку Х чётной, а стол­бец Y  — нечётным. За­ме­тим, что на пе­ре­се­че­нии стро­ки и столб­ца оди­на­ко­вой чётно­сти долж­на сто­ять крас­ная клет­ка, а на пе­ре­се­че­нии стро­ки и столб­ца раз­ной чётно­сти  — синяя, иначе знак в этой клет­ке после всех опе­ра­ций не из­ме­нит­ся. Сле­до­ва­тель­но, ко­ли­че­ство крас­ных кле­ток в каж­дой чётной стро­ке равно числу чётных столб­цов, а ко­ли­че­ство синих  — числу нечётных столб­цов таб­ли­цы. Есть хотя бы одна чётная стро­ка Х, зна­чит, всего в таб­ли­це чётное число нечётных столб­цов. Но ко­ли­че­ство крас­ных кле­ток в каж­дой нечётной стро­ке (нечётное!) равно числу нечётных столб­цов, то есть чётному числу  — про­ти­во­ре­чие с тем, что есть хотя бы один нечётный стол­бец. Сле­до­ва­тель­но, нель­зя обой­тись мень­ше, чем 100 опе­ра­ци­я­ми.

Ответ: За 100 опе­ра­ций.

Куз­не­чик со­вер­шит 16 го­ри­зон­таль­ных прыж­ка нечётных длин 1, 3, 5, .., 31 см. Разобьём их на 4 четвёрки по­сле­до­ва­тель­ных нечётных чисел, в каж­дой четвёрке пер­вый и по­след­ний прыж­ки будут со­вер­шать­ся впра­во, а вто­рой и тре­тий  — влево. После каж­дых четырёх таких прыж­ков куз­не­чик будет ока­зы­вать­ся на оси OY. Вер­ти­каль­ных прыж­ков куз­не­чик со­вер­шит 15, разобьём их на трой­ку 2,4,6 пер­вых и 3 по­сле­до­ва­тель­ных четвёрок остав­ших­ся от 8 до 30. Прыж­ки длин 2 и 4 он сде­ла­ет вверх, а пры­жок длины 6  — вниз. В каж­дой четвёрке пер­вый и по­след­ний прыж­ки он сде­ла­ет вверх, а вто­рой и тре­тий  — вниз. Пры­гая так, после пер­вой трой­ки и после каж­дой четвёрки вер­ти­каль­ных прыж­ков он ока­жет­ся на оси ОХ. В итоге, после всех 31 прыж­ка он вернѐтся в на­ча­ло ко­ор­ди­нат.

Ответ: Да.

Куз­не­чик сде­ла­ет по 50 вер­ти­каль­ных и го­ри­зон­таль­ных прыж­ков. Длины вер­ти­каль­ных прыж­ков равны 2,4, ..,100 см. Среди этих чисел 25 де­ля­щих­ся на 4 и 25, да­ю­щих при де­ле­нии на 4 оста­ток 2, сле­до­ва­тель­но, при любой рас­ста­нов­ке плю­сов и ми­ну­сов между ними сумма будет да­вать де­ле­нии на 4 оста­ток 2 и ни­ко­гда не будет равна 0. Куз­не­чик после 100 прыж­ков не смо­жет ока­зать­ся на оси ОХ, а, зна­чит, и в на­ча­ле ко­ор­ди­нат.

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

Если таб­ли­ца 2 по­лу­че­на из таб­ли­цы 1 одним из ука­зан­ных дей­ствий, то что для таб­лиц А и В не вы­пол­не­но. По­это­му ука­зан­ным спо­со­бом по­лу­чить таб­ли­цу B из таб­ли­цы А нель­зя.

Таб­ли­ца 1

Таб­ли­ца 2

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

Для крат­ко­сти ко­ман­ду влево будем обо­зна­чать Л, впра­во – П, вверх – В, вниз – Н. Чтобы робот вер­нул­ся в ис­ход­ное по­ло­же­ние не­об­хо­ди­мо и до­ста­точ­но, чтобы ему было от­да­но ко­манд Л столь­ко же, сколь­ко и ко­манд П, а ко­манд В – столь­ко же, сколь­ко и Н. Пусть k –ко­ли­че­ство ко­манд Л в по­сле­до­ва­тель­но­сти. Под­счи­та­ем ко­ли­че­ство N_k ис­ко­мых по­сле­до­ва­тель­но­стей для k от 0 до 2.

 ·  По­сле­до­ва­тель­ность со­сто­ит толь­ко из ко­манд В и Н. Так как их по­ров­ну, то на 2 ме­стах из 4 долж­на быть ко­ман­да В, а на остав­ших­ся двух – Н. Вы­брать 2 места из 4 можно спо­со­ба­ми. Сле­до­ва­тель­но,

 ·  Каж­дая из ко­манд Л, П, В, Н встре­ча­ет­ся в по­сле­до­ва­тель­но­сти ровно 1 раз. Число пе­ре­ста­но­вок из 4 эле­мен­тов равно 4!. По­это­му

 ·  Здесь две Л, две П и нет ко­манд В и Н. Две ко­ман­ды Л можно раз­ме­стить спо­со­ба­ми. Зна­чит,

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

Ответ: 36.

Для крат­ко­сти ко­ман­ду влево будем обо­зна­чать Л, впра­во – П, вверх – В, вниз – Н. Чтобы робот вер­нул­ся в ис­ход­ное по­ло­же­ние, не­об­хо­ди­мо и до­ста­точ­но, чтобы ему было от­да­но ко­манд Л столь­ко же, сколь­ко и ко­манд П, а ко­манд В – столь­ко же, сколь­ко и Н. Пусть k – ко­ли­че­ство ко­манд Л в по­сле­до­ва­тель­но­сти. Под­счи­та­ем ко­ли­че­ство N_k ис­ко­мых по­сле­до­ва­тель­но­стей для k от 0 до 4.

 ·  По­сле­до­ва­тель­ность со­сто­ит толь­ко из ко­манд В и Н. Так как их по­ров­ну, то на 4 ме­стах из 8 долж­на быть ко­ман­да В, а на остав­ших­ся двух – Н. Вы­брать 4 места из 8 можно спо­со­ба­ми. Сле­до­ва­тель­но,

 ·  По­сле­до­ва­тель­ность со­сто­ит из одной ко­ман­ды Л, одной П, а также трех В и трех Н. Раз­ме­стить две ко­ман­ды Л и П на 8 по­зи­ци­ях можно спо­со­ба­ми: – число спо­со­бов во­об­ще вы­брать 2 по­зи­ции из 8, – число спо­со­бов раз­ме­стить на этих двух по­зи­ци­ях ко­ман­ды Л и П. На остав­ших­ся 6 по­зи­ци­ях сле­ду­ет раз­ме­стить 3 ко­ман­ды В, что можно сде­лать спо­со­ба­ми. По­это­му

 ·  Здесь две Л, две П а также по 2 ко­ман­ды В и Н. Для Л и П имеем ва­ри­ан­тов раз­ме­ще­ния. На остав­ших­ся 4 по­зи­ци­ях раз­ме­стить 2 ко­ман­ды В можно спо­со­ба­ми. Зна­чит,

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

Ответ: 4900.

На­зо­вем «ве­ли­чи­ной» слова число n − m, где n и m  — ко­ли­че­ство букв Л и A со­от­вет­ствен­но в дан­ном слове. За­ме­тим, что все до­пу­сти­мые опе­ра­ции со­хра­ня­ют оста­ток «ве­ли­чи­ны» слова по мо­ду­лю 3. «Ве­ли­чи­на» из­вест­но­го слова ЛЛAФAЛAФФAЛAФФФAЛAФФФФAЛЛ равна 7 − 8 = −1, а «ве­ли­чи­на» слова ЛФAЛФAЛФAЛФAЛAФЛAФЛAФЛAФЛ равна 9 − 8 = 1, то есть такое слово не может встре­тить­ся в ал­фа­ви­те этого языка.

Ответ: нет.

Сумма цифр ис­ход­но­го числа

Сумма цифр ко­неч­но­го числа такая же.

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

Если в числе ровно 100 цифр, и сумма цифр в какой-то паре боль­ше 10, то общая сумма цифр боль­ше 500. Зна­чит, в каж­дом 100-знач­ном числе, ко­то­рое может у нас по­лу­чить­ся, сумма цифр в каж­дой паре ровно 10.

Об­ра­ти­те вни­ма­ние: утвер­жде­ние о том, что в каж­дом таком числе сумма со­сед­них цифр равна 10 во­об­ще го­во­ря, не­вер­но: может по­лу­чить­ся, на­при­мер, число в ко­то­ром это усло­вие на­ру­ша­ет­ся.

В каж­дой паре нам не­об­хо­ди­мо мак­си­ми­зи­ро­вать первую цифру и ми­ни­ми­зи­ро­вать вто­рую. По­сколь­ку каж­дая пара цифр по­лу­ча­ет­ся ука­зан­ны­ми в усло­вии опе­ра­ци­я­ми из 1234, вто­рая цифра не мень­ше 4 и наи­боль­ший вари ант для каж­дой пары это 64, от­ку­да мы полу чаем ответ.

Ответ: 64...64  — 100-знач­ное число.

Сумма цифр ис­ход­но­го числа

Сумма цифр ко­неч­но­го числа такая же.

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

Если в числе ровно 150 цифр, и сумма цифр в какой-то паре боль­ше 10, то общая сумма цифр боль­ше 750. Зна­чит, в каж­дом 150-знач­ном числе, ко­то­рое может у нас по­лу­чить­ся, сумма цифр в каж­дой паре ровно 10.

Об­ра­ти­те вни­ма­ние: утвер­жде­ние о том, что в каж­дом таком числе сумма со­сед­них цифр равна 10 во­об­ще го­во­ря, не­вер­но: может по­лу­чить­ся, на­при­мер, число в ко­то­ром это усло­вие на­ру­ша­ет­ся.

В каж­дой паре нам не­об­хо­ди­мо мак­си­ми­зи­ро­вать первую цифру и ми­ни­ми­зи­ро­вать вто­рую. По­сколь­ку каж­дая пара цифр полу ча­ет­ся ука­зан­ны­ми в усло­вии опе­ра­ци­я­ми из 1225, вто­рая цифра не ме­ны­шее 5 и наи­боль­ший ва­ри­ант для каж­дой пары это 55, от­ку­да мы полу чаем ответ.

Ответ: 55...55  — 100-знач­ное число.

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

В те­че­ние одной фазы ни­ка­кое число не может уве­ли­чит­ся боль­ше, чем на 4. Дей­стви­тель­но, если мы уве­ли­чи­ли само число, то ни к нему, ни к его со­се­дям не может быть при­ме­не­на наша опе­ра­ция в те­че­ние этой фазы ни до, не после, по­сколь­ку число, уве­ли­чен­ное на один в не­ко­то­рой фазе, не может ока­зать­ся ми­ни­маль­ным в те­че­ние той же самой фазы. Среди со­се­дей числа можно вы­брать не боль­ше 4 не со­сед­них между собой, зна­чит, дей­стви­тель­но мы можем уве­ли­чить число не боль­ше, чем на 4 за одну фазу.

Рас­смот­рим пер­вые, четвёртые, седь­мые и де­ся­тые клет­ки в пер­вой, четвёртой, седь­мой и де­ся­той стро­ках таб­ли­цы, всего 16 штук. За­ме­тим, что ни­ка­кая опе­ра­ция не за­тра­ги­ва­ет две из них. Зна­чит, чтобы сме­ни­лось n фаз, надо со­вер­шить хотя бы 16n опе­ра­ций. Важно! Мы не можем утвер­ждать, что одна фаза длит­ся хотя бы 16 опе­ра­ций, так как не­ко­то­рые из наших чисел могли быть уве­ли­че­ны на преды­ду­щих фазах.

Зна­чит, у нас про­шло не более 5 фаз и в каж­дой ни­ка­кое число не могло уве­ли­чит­ся более, чем на 4. Сле­до­ва­тель­но, за 80 опе­ра­ций ни­ка­кое число не могло стать боль­ше, чем 20.

При­мер стро­ит­ся сле­ду­ю­щим об­ра­зом: рас­смот­рим вто­рые, четвёртые, седь­мые и де­ся­тые клет­ки во вто­рой, четвёртой, седь­мой и де­ся­той стро­ках таб­ли­цы, всего 16 штук. Будем при­ме­нять опе­ра­ции толь­ко к ним. Опе­ра­ции, при­менённые к одной из этих кле­ток, не за­тра­ги­ва­ют осталь­ные 15, и при этом после при­ме­не­ния опе­ра­ций ко в сем 16 клет­кам все числа в таб­ли­це уве­ли­чи­ва­ют­ся хотя бы на 1. При этом число в тре­тьей клет­ке тре­тьей стро­ки будет каж­дую фазу уве­ли­чи­вать­ся на 4.

Ра­зу­ме­ет­ся, при­мер не един­ствен­ный.

Ответ: 20.

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

В те­че­ние одной фазы ни­ка­кое число не может уве­ли­чит­ся боль­ше, чем на 4. Дей­стви­тель­но, если мы уве­ли­чи­ли само число, то ни к нему, ни к его со­се­дя м не может быть при­ме­не­на наша опе­ра­ция в те­че­ние этой фазы ни до, не после, по­сколь­ку число, уве­ли­чен­ное на один в не­ко­то­рой фазе, не может ока­зать­ся ми­ни­маль­ным в те­че­ние той же самой фазы. Среди со­се­дей числа можно вы­брать не боль­ше 4 не со­сед­них между собой, зна­чит, дей­стви­тель­но мы можем уве­ли­чить число не боль­ше, чем на 4 за одну фазу.

Рас­смот­рим пер­вые, четвёртые и седь­мые клет­ки в пер­вой, четвёртой и седь­мой стро­ках таб­ли­цы, всего 9 штук. За­ме­тим, что ни­ка­кая опе­ра­ция не за­тра­ги­ва­ет две из них. Зна­чит, чтобы сме­ни­лось n фаз, надо со­вер­шить хотя бы 9n опе­ра­ций. Важно! Мы не можем утвер­ждать, что одна фаза длит­ся хотя бы 9 опе­ра­ций, так как не­ко­то­рые из наших чисел могли быть уве­ли­че­ны на преды­ду­щих фазах.

Зна­чит, у нас про­шло не более 10 фаз и в каж­дой ни­ка­кое число не могло уве­ли­чит­ся более, чем на 4. Сле­до­ва­тель­но, за 90 опе­ра­ций ни­ка­кое число не могло стать боль­ше, чем 40.

При­мер стро­ит­ся сле­ду­ю­щим об­ра­зом: рас­смот­рим вто­рые, четвёртые и ше­стые клет­ки во вто­рой, четвёртой и ше­стой стро­ках таб­ли­цы, всего 9 штук. Будем при­ме­нять опе­ра­ции толь­ко к ним. Опе­ра­ции, при­менённые к одной из этих кле­ток, не за­тра­ги­ва­ют осталь­ные 8, и при этом после при­ме­не­ния опе­ра­ций ко в см 9 клет­кам все числа в таб­ли­це уве­ли­чи­ва­ют­ся хотя бы на 1. При этом число в тре­тьей клет­ке тре­тьей стро­ки будет каж­дую фазу уве­ли­чи­вать­ся на 4.

Ра­зу­ме­ет­ся, при­мер не един­ствен­ный.

Ответ: 40.

Обо­зна­чим через P про­из­ве­де­ние всех чисел в трой­ке. Оче­вид­но, что P не ме­ня­ет­ся после каж­до­го хода (это ин­ва­ри­ант). Од­на­ко для пер­вой трой­ки

а для вто­рой

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

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

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

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

По­ка­жем, что все осталь­ные кон­фи­гу­ра­ции нель­зя по­лу­чить друг из друга. Дей­стви­тель­но, наша опе­ра­ция не ме­ня­ет раз­ность ко­ли­че­ства орлов на чётных ме­стах и ко­ли­че­ства орлов на нечётных ме­стах. Когда боль­шая груп­па со­сто­ит из од­но­го орла, т. е. когда все орлы стоят на нечётных ме­стах, а решки на чётных, эта раз­ность равна Уве­ли­че­ние ко­ли­че­ства орлов в боль­шой груп­пе умень­ша­ет эту раз­ность на 1, по­это­му все раз­но­сти от 0 до воз­мож­ны. Ана­ло­гич­но, когда боль­шая груп­па со­сто­ит из решек по­лу­чат­ся раз­но­сти от −1 до Итого по­лу­ча­ем раз­лич­ную кон­фи­гу­ра­цию.

Ответ: 2 ва­ри­ан­та для нечётных n и ва­ри­ант для чётных n.

Обо­зна­чим через n_i ко­ли­че­ство дей­ствий каж­до­го из че­ты­рех воз­мож­ных типов. Тре­бу­ет­ся ре­шить си­сте­му (пер­вое урав­не­ние со­от­вет­ству­ет из­ме­не­нию ко­ли­че­ства пя­те­рок, вто­рое  — двоек)

Умно­жим вто­рое урав­не­ние на два и сло­жим с пер­вым

Со­глас­но усло­вию, ве­ли­чи­на яв­ля­ет­ся целым чис­лом. Од­на­ко урав­не­ние не имеет ре­ше­ния в целых чис­лах.

Ответ: не может.

Разо­бьем таб­ли­цу на 2500 квад­ра­ти­ков 2 × 2. Не­слож­но ви­деть, что в каж­дом квад­ра­ти­ке можно сде­лать числа рав­ны­ми (в квад­ра­ти­ке 2 × 2. при­бав­ле­ние еди­ниц к чис­лам из угол­ка со­от­вет­ству­ет вы­чи­та­нию еди­ни­цы из од­но­го числа с по­сле­ду­ю­щим уве­ли­че­ни­ем всех чисел квад­ра­та на один, а та­ки­ми вы­чи­та­ни­я­ми легко сде­лать числа рав­ны­ми). Кроме того, че­тырь­мя опе­ра­ци­я­ми все числа в квад­ра­ти­ке можно уве­ли­чить на три. По­это­му до­ста­точ­но до­бить­ся того, чтобы числа из раз­ных квад­ра­ти­ков да­ва­ли оди­на­ко­вый оста­ток от де­ле­ния на три.

Даль­ше будем смот­реть толь­ко на остат­ки. Возь­мем два со­сед­них квад­ра­ти­ка. С по­мо­щью че­ты­рех опе­ра­ций можно уве­ли­чить все числа в одном квад­ра­ти­ке на еди­ни­цу, a все числа в дру­гом квад­ра­ти­ке  — на двой­ку. По­это­му можно оста­ток чисел в одном квад­ра­ти­ке уве­ли­чить на 1, а в дру­гом  — умень­шить на 1. Пусть оста­ток суммы чисел во всей таб­ли­це равен r. По­ка­жем, как до­бить­ся того, чтобы все числа в таб­ли­це имели оста­ток r. По­сле­до­ва­тель­но слева на­пра­во прой­дем по парам квад­ра­ти­ков сна­ча­ла в верх­ней стро­ке и по­лу­чим во всех квад­ра­ти­ках, кроме са­мо­го пра­во­го, оста­ток r. Про­де­ла­ем те же дей­ствия с осталь­ны­ми стро­ка­ми. На­ко­нец, дви­га­ясь свер­ху вниз, по­сле­до­ва­тель­но об­ра­бо­та­ем пра­вый стол­бец. В ре­зуль­та­те всех квад­ра­ти­ках, кроме пра­во­го ниж­не­го, будут числа, да­ю­щие оста­ток r, а в пра­вом ниж­нем  — числа, да­ю­щие оста­ток x. Тогда сумма чисел во всей таб­ли­це дает оста­ток

по­это­му

Ответ: все­гда.

а)  С по­мо­щью 55 сле­ду­ю­щих опе­ра­ций можно по­лу­чить 56 еди­ниц:

Из них с по­мо­щью 28 опе­ра­ций по­лу­чим 28 нулей:

а затем после 27 опе­ра­ций  — один 0.

б)  За­ме­тим, что при любой опе­ра­ции чет­ность суммы чисел на доске не ме­ня­ет­ся (так как числа и одной чет­но­сти). Вна­ча­ле сумма была не­чет­ной (в ней 55 не­чет­ных сла­га­е­мых и 55 чет­ных). Зна­чит, в ре­зуль­та­те всех опе­ра­ций по­лу­чить 0 не удаст­ся. По­лу­чить еди­ни­цу можно спо­со­бом, ана­ло­гич­ным ука­зан­но­му в пунк­те а): а имен­но,

здесь 55 еди­ниц, и далее

то есть по­лу­чим еди­ни­цу и 27 нулей, а затем  — одну еди­ни­цу.

Ответ: a) 0; б) 1.

За­ме­тим, для каж­до­го дей­ствия есть об­рат­ное ему. По­это­му если мы из си­ту­а­ции 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.

За­ме­тим, что при любой из опи­сан­ных опе­ра­ций раз­ность между лю­бы­ми двумя на­пи­сан­ны­ми чис­ла­ми либо не из­ме­ня­ет­ся, либо из­ме­ня­ет­ся на 10. Разобьём все числа на 5 пар: 1 и 11, 2 и 12, 3 и 13, 4 и 4, 5 и 5, раз­но­сти чисел в каж­дой паре равны 0 или 10. Если после не­сколь­ких опе­ра­ций все числа ста­нут раз­ны­ми, то раз­но­сти чисел в каж­дой паре ста­нут не мень­ше 10.

Мень­шие числа в парах будут не мень­ше 0, 1, 2, 3, 4, боль­шие числа в парах не мень­ше 10, 11, 12, 13, 14 и сумма всех по­лу­чен­ных чисел будет не мень­ше

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

Ответ: нет.

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

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

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

Ответ: 32.