Олимпиадные задачи по теме «Инварианты и полуинварианты» - сложность 3 с решениями

Изначально на доске записаны 10 последовательных натуральных чисел. За одну операцию разрешается выбрать любые два числа на доске (обозначим их <i>a</i> и <i>b</i>) и заменить их на числа  <i>a</i>² – 2011<i>b</i>²  и <i>ab</i>. После нескольких таких операций на доске не осталось ни одного из исходных чисел. Могли ли там опять оказаться 10 последовательных натуральных чисел (записанных в некотором порядке)?

У Носорога на шкуре есть вертикальные и горизонтальные складки. Всего складок 17. Если Носорог чешется боком о дерево, то либо две горизонтальные, либо две вертикальные складки на этом боку пропадают, зато на другом боку прибавляются две складки: горизонтальная и вертикальная. (Если двух складок одного направления нет, то ничего не происходит.) Носорог почесался несколько раз. Могло ли случиться, что на каждом боку вертикальных складок стало столько, сколько там раньше было горизонтальных, а горизонтальных стало столько, сколько там было вертикальных?

У Пети и Коли в тетрадях записаны по два числа; изначально – это числа 1 и 2 у Пети, 3 и 4 – у Коли. Раз в минуту Петя составляет квадратный трёхчлен <i>f</i>(<i>x</i>), корнями которого являются записанные в его тетради два числа, а Коля – квадратный трёхчлен <i>g</i>(<i>x</i>), корнями которого являются записанные в его тетради два числа. Если уравнение  <i>f</i>(<i>x</i>) = <i>g</i>(<i>x</i>)  имеет два различных корня, то один из мальчиков заменяет свою пару чисел на эти корни; иначе ничего не происходит. Какое второе число могло оказаться у Пети в тетради в тот момент, когда первое стало равным 5?

Дано натуральное число. Разрешается расставить между цифрами числа плюсы произвольным образом и вычислить сумму (например, из числа 123456789 можно получить  12345 + 6 + 789 = 13140).  С полученным числом снова разрешается выполнить подобную операцию, и так далее. Докажите, что из любого числа можно получить однозначное, выполнив не более 10 таких операций.

На плоскости лежит игла. Разрешается поворачивать иглу на 45° вокруг любого из её концов.

Можно ли, сделав несколько таких поворотов, добиться того, чтобы игла вернулась на исходное место, но при этом её концы поменялись местами?

По кругу стоят 100 напёрстков. Под одним из них спрятана монетка. За один ход разрешается перевернуть четыре напёрстка и проверить, лежит ли под одним из них монетка. После этого их возвращают в исходное положение, а монетка перемещается под один из соседних с ней напёрстков. За какое наименьшее число ходов наверняка удастся обнаружить монетку?

На кольцо свободно нанизано 2009 бусинок. За один ход любую бусинку можно передвинуть так, чтобы она оказалась ровно посередине между двумя соседними. Существуют ли такие изначальная расстановка бусинок и последовательность ходов, при которых какая-то бусинка пройдёт хотя бы один полный круг?

Двое играющих по очереди пишут – каждый на своей половине доски – по одному натуральному числу (повторения разрешаются) так, чтобы сумма всех чисел на доске не превосходила 10000. После того, как сумма всех чисел на доске становится равной 10000, игра заканчивается подсчетом суммы всех цифр на каждой половине. Выигрывает тот, на чьей половине сумма цифр меньше (при равных суммах – ничья). Может ли кто-нибудь из игроков выиграть, как бы ни играл противник?

На доске написано натуральное число. Если на доске написано число <i>x</i>, то можно дописать на нее число  2<i>x</i> + 1  или ^<i>x</i>/_<i>x</i>+2. В какой-то момент выяснилось, что на доске присутствует число 2008. Докажите, что оно там было с самого начала.

В клетках квадрата 5×5 изначально были записаны нули. Каждую минуту Вася выбирал две клетки с общей стороной и либо прибавлял по единице к числам в них, либо вычитал из них по единице. Через некоторое время оказалось, что суммы чисел во всех строках и столбцах равны. Докажите, что это произошло через чётное число минут.

На шахматной доске расставлены во всех клетках 32 белых и 32 черных пешки. Пешка может бить пешки противоположного цвета, делая ход по диагонали на одну клетку и становясь на место взятой пешки (белые пешки могут бить только вправо-вверх и влево-вверх, а чёрные – только влево-вниз и вправо-вниз). Другим образом пешки ходить не могут. Какое наименьшее количество пешек может остаться на доске?

Написанное на доске четырехзначное число можно заменить на другое, прибавив к двум его соседним цифрам по единице, если ни одна из этих цифр не равна 9, либо вычтя из соседних двух цифр по единице, если ни одна из них не равна 0. Можно ли с помощью таких операций из числа 1234 получить число 2002?

Даны числа 1, 2, ..., <i>N</i>, каждое из которых окрашено либо в чёрный, либо в белый цвет. Разрешается перекрашивать в противоположный цвет любые три числа, одно из которых равно полусумме двух других. При каких <i>N</i> всегда можно сделать все числа белыми?

У нескольких крестьян есть 128 овец. Если у кого-то из них оказывается не менее половины всех овец, остальные сговариваются и раскулачивают его: каждый берёт себе столько овец, сколько у него уже есть. Если у двоих по 64 овцы, то раскулачивают кого-то одного из них. Произошло 7 раскулачиваний. Докажите, что все овцы собрались у одного крестьянина.

Ножки циркуля находятся в узлах бесконечного листа клетчатой бумаги, клетки которого – квадраты со стороной 1. Разрешается, не меняя раствора циркуля, поворотом его вокруг одной из ножек перемещать вторую ножку в другой узел на листе. Можно ли за несколько таких шагов поменять ножки циркуля местами?

На доске записано целое число. Его последняя цифра запоминается, затем стирается и, умноженная на 5, прибавляется к тому числу, что осталось на доске после стирания. Первоначально было записано число 7¹⁹⁹⁸. Может ли после применения нескольких таких операций получиться число 1998⁷?

Имеется таблица <i>n×n</i>, в  <i>n</i> – 1  клетках которой записаны единицы, а в остальных клетках – нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?

На столе лежали две колоды, по 36 карт в каждой. Первую колоду перетасовали и положили на вторую. Затем для каждой карты первой колоды подсчитали количество карт между ней и такой же картой второй колоды (то есть сколько карт между семёрками червей, между дамами пик, и т.д.). Чему равна сумма 36 полученных чисел?

В каждой клетке квадратной таблицы размером <i>n×n</i> клеток  (<i>n</i> ≥ 3)  записано число 1 или –1. Если взять любые две строки, перемножить числа, стоящие в них друг над другом и сложить <i>n</i> получившихся произведений, то сумма будет равна 0. Докажите, что число <i>n</i> делится на 4.

В магическом квадрате <i>n×n</i>, составленном из чисел 1, 2, ..., <i>n</i>², центры каждых двух клеток соединили вектором в направлении от большего числа к меньшему. Докажите, что сумма всех полученных векторов равна нулю. (Магическим называется клетчатый квадрат, в клетках которого записаны числа так, что суммы чисел во всех его строках и столбцах равны.)

Имеется три кучи камней. Сизиф таскает по одному камню из кучи в кучу. За каждое перетаскивание он получает от Зевса количество монет, равное разности числа камней в куче, в которую он кладёт камень, и числа камней в куче, из которой он берёт камень (сам перетаскиваемый камень при этом не учитывается). Если указанная разность отрицательна, то Сизиф возвращает Зевсу соответствующую сумму. (Если Сизиф не может расплатиться, то великодушный Зевс позволяет ему совершать перетаскивание в долг.) В некоторый момент оказалось, что все камни лежат в тех же кучах, в которых лежали первоначально. Каков наибольший суммарный заработок Сизифа на этот момент?

Имеется семь стаканов с водой: первый стакан заполнен водой наполовину, второй – на треть, третий – на четверть, четвёртый – на &frac15;, пятый – на &frac18;, шестой – на ¹/₉, и седьмой – на ¹/₁₀. Разрешается переливать всю воду из одного стакана в другой или переливать воду из одного стакана в другой до тех пор, пока он не заполнится доверху. Может ли после нескольких переливаний какой-нибудь стакан оказаться заполненным   а) на ¹/₁₂;   б) на &frac16;?

Квадратный трёхчлен  <i>f</i>(<i>x</i>) разрешается заменить на один из трёхчленов   <img align="absmiddle" src="/storage/problem-media/109523/problem_109523_img_2.gif">   или   <img align="absmiddle" src="/storage/problem-media/109523/problem_109523_img_3.gif">   Можно ли с помощью таких операций из квадратного трёхчлена  <i>x</i>² + 4<i>x</i> + 3  получить трёхчлен  <i>x</i>² + 10<i>x</i> + 9?

Капитан Врунгель в своей каюте разложил перетасованную колоду из 52 карт по кругу, оставив одно место свободным. Матрос Фукс с палубы, не отходя от штурвала и не зная начальной раскладки, называет карту. Если эта карта лежит рядом со свободным местом, Врунгель её туда передвигает, не сообщая Фуксу. Иначе ничего не происходит. Потом Фукс называет ещё одну карту, и так сколько угодно раз, пока сам не скажет "стоп". Может ли Фукс добиться того, чтобы после "стопа" каждая карта наверняка оказалась не там, где была вначале?

На плоскости расположено такое конечное множество точек <i>M</i>, что никакие три точки не лежат на одной прямой. Некоторые точки соединены друг с другом отрезками так, что из каждой точки выходит не более одного отрезка. Разрешается заменить пару пересекающихся отрезков <i>AB</i> и <i>CD</i> парой противоположных сторон <i>AC</i> и <i>BD</i> четырёхугольника <i>ACBD</i>. В полученной системе отрезков разрешается снова произвести подобную замену, и т. д. Может ли последовательность таких замен быть бесконечной?