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

Изначально на доске записаны 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° вокруг любого из её концов.

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

За круглым столом заседают <i>N</i> рыцарей. Каждое утро чародей Мерлин сажает их в другом порядке. Начиная со второго дня Мерлин разрешил рыцарям делать в течение дня сколько угодно пересадок такого вида: два сидящих рядом рыцаря меняются местами, если только они не были соседями в первый день. Рыцари стараются сесть в том же порядке, что и в какой-нибудь из предыдущих дней: тогда заседания прекратятся. Какое наибольшее число дней Мерлин гарантированно может проводить заседания?

(Рассадки, получающиеся друг из друга поворотом, считаются одинаковыми. Мерлин за столом не сидит.)

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

По кругу стоят2009целых неотрицательных чисел, не превышающих 100. Разрешается прибавить по1к двум соседним числам, причем с любыми двумя соседними числами эту операцию можно проделать не более<i> k </i> раз. При каком наименьшем<i> k </i>все числа гарантированно можно сделать равными?

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

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

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

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

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

а) В 99 ящиках лежат яблоки и апельсины.

Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов. б) В 100 ящиках лежат яблоки и апельсины.

Докажите, что можно так выбрать 34 ящика, что в них окажется не менее трети всех яблок и не менее трети всех апельсинов.

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

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

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

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

Куб со стороной<i> n </i>(<i> n<img src="/storage/problem-media/109948/problem_109948_img_2.gif"></i>3) разбит перегородками на единичные кубики. Какое минимальное число перегородок между единичными кубиками нужно удалить, чтобы из каждого кубика можно было добраться до границы куба?

На доске записано целое число. Его последняя цифра запоминается, затем стирается и, умноженная на 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>положительным</i>, если при его обходе против часовой стрелки цвета улиц идут в следующем порядке: белый, синий, красный, и <i>отрицательным</i> в противном случае. Докажите, что разность между числом положительных и числом отрицательных перекрёстков кратна 4.

Дано дерево с <i>n</i> вершинами,  <i>n</i> ≥ 2.  В его вершинах расставлены числа <i>x</i>₁, <i>x</i>₂, <i>x_n</i>, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через <i>S</i> сумму чисел на всех рёбрах. Докажите, что   <img align="absmiddle" src="/storage/problem-media/109782/problem_109782_img_2.gif">