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

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

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

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

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

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

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

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

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

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

Квадратный трёхчлен  <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?

Бильярдный стол имеет форму многоугольника (не обязательно выпуклого), у которого соседние стороны перпендикулярны друг другу. Вершины этого многоугольника – лузы, при попадании в которые шар там и остаётся. Из вершины <i>A</i> с (внутренним) углом 90° выпущен шар, который отражается от бортов (сторон многоугольника) по закону "угол падения равен углу отражения". Докажите, что он никогда не вернётся в вершину <i>A</i>.

В каждой клетке таблицы размером 4×4 стоит знак "+" или "–". Разрешено одновременно менять знаки на противоположные в любой клетке и во всех клетках, имеющих с ней общую сторону. Сколько разных таблиц можно получить, многократно применяя такие операции?

Пусть <i>F</i>₁, <i>F</i>₂, <i>F</i>₃, ... – последовательность выпуклых четырёхугольников, где <i>F</i>_<i>k</i>+1  (при <i>k</i> = 1, 2, 3, ...)  получается так: <i>F_k</i> разрезают по диагонали, одну из частей переворачивают и склеивают по линии разреза с другой частью. Какое наибольшее количество различных четырёхугольников может содержать эта последовательность? (Различными считаются многоугольники, которые нельзя совместить движением.)

На доске размером 15×15 клеток расставили 15 ладей, не бьющих друг друга. Затем каждую ладью передвинули ходом коня.

Докажите, что теперь какие-то две ладьи будут бить друг друга.

В колоду сложено <i>n</i> различных карт. Разрешается переложить любое число рядом лежащих карт (не меняя порядок их следования и не переворачивая) в другое место колоды. Требуется несколькими такими операциями переложить все <i>n</i> карт в обратном порядке.

  а) Докажите, что при  <i>n</i> = 9  это можно сделать за 5 операций;

Докажите, что при  <i>n</i> = 52  это

  б) можно сделать за 27 операций;

  в) нельзя сделать за 17 операций;

  г) нельзя сделать за 26 операций.

Числа  1, 2, 3, ..., <i>n</i>  записываются в некотором порядке:  <i>a</i>₁, <i>a</i>₂, <i>a</i>₃, ..., <i>a_n</i>.  Берётся сумма  <i>S</i> = ^<i>a</i>₁/₁ + ^<i>a</i>₂/₂ + ... + ^<i>a_n</i>/_<i>n</i>.  Найдите такое <i>n</i>, чтобы среди таких сумм (при всевозможных перестановках  <i>a</i>₁, <i>a</i>₂,...

Какое наибольшее количество  а) ладей;  б) ферзей можно расставить на шахматной доске 8×8 так, чтобы каждая из этих фигур была под ударом не более чем одной из остальных?

На доске написана функция  sin $x$ + cos $x$.  Разрешается написать на доске производную любой написанной ранее функции, а также сумму и произведение любых двух написанных ранее функций, так можно делать много раз. В какой-то момент на доске оказалась функция, равная для всех действительных $x$ некоторой константе $c$. Чему может равняться $c$?

Дан отрезок  [0, 1].  За ход разрешается разбить любой из имеющихся отрезков точкой на два новых отрезка и записать на доску произведение длин этих двух новых отрезков.

Докажите, что ни в какой момент сумма чисел на доске не превысит ½.

На доске написаны 2$n$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего числа меньшее, все замены происходят одновременно). Докажите, что на доске больше никогда не появятся 2$n$ последовательных чисел.

На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить "Да" или "Нет" на вопрос: "На острове рыцарей больше, чем лжецов?". Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов "Да" и "Нет" было поровну, давал любой из этих ответов. Оказалось, что ответов "Да" было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова?

На доске написаны $1000$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего меньшее; все замены происходят одновременно). Докажите, что на доске больше никогда не появятся $1000$ последовательных целых чисел.

В левой нижней клетке доски 100×100 стоит фишка. Чередуя горизонтальные и вертикальные ходы в соседнюю по стороне клетку (первый ход горизонтальный), она дошла сначала до левой верхней клетки, а потом до правой верхней. Докажите, что найдутся две такие клетки $A$ и $B$, что фишка не менее двух раз делала ход из $A$

в $B$.

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

  а) каждая карта наверняка оказалась не там, где была вначале?

  б) рядом со свободным местом наверняка не было туза пик?

Изначально на доске написано натуральное число <i>N</i>. В любой момент Миша может выбрать число  <i>a</i> > 1  на доске, стереть его и дописать все натуральные делители <i>a</i>, кроме него самого (на доске могут появляться одинаковые числа). Через некоторое время оказалось, что на доске написано <i>N</i>² чисел. При каких <i>N</i> это могло случиться?

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