Тема Применение классических комбинаторных методов к разным задачам

Полуинвариант

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела применение классических комбинаторных методов к разным задачам

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#104700

В классе 28 учеников, у каждого ровно 3 друга среди одноклассников. Однажды на каникулах семеро учеников подписались на канал по олимпиадной математике. После этого ученики стали общаться между собой. Когда ученик узнаёт, что хотя бы двое из его друзей уже подписались на канал, он также подписывается на этот канал. Могло ли в итоге случиться, что весь класс подписался на канал?

Источники: ОММО - 2025, номер 10 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

В задачах на процессы и с вопросом "могло ли" очень часто работает идея полуинварианта — давайте поищем какую-то характеристику, которая монотонно убывает или возрастает (либо же меняется совсем чуть-чуть), и мы можем за ней проследить)

Подсказка 2

Рассмотрите количество пар друзей, где один подписан на канал, а другой — нет.

Подсказка 3

Количество указанных пар не возрастает! Теперь надо понять, а какие у неё значения в начале процесса и в конце :)

Показать ответ и решение

Будем называть пару друзей хорошей, если эта пара образуется между подписчиком и не подписчиком канала.

Заметим, что каждый раз, когда ученик подписывается на канал по олимпиадной математике, количество хороших пар уменьшается хотя бы на 1.

Всего у каждого из семи подписанных на канал учеников может быть не более трёх хороших друзей. Следовательно, изначально количество хороших пар не превышает 21. Рассмотрим момент, когда на канал подписались все ученики, кроме одного. Тогда в момент, когда подпишется последний ученик, количество хороших пар уменьшится уже на 3, следовательно, подписок может быть не более чем 19. Так как в классе всего 28 человек, то весь класс не может быть подписан на канал.

Ответ:

Нет, не могло

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#125626

Изначально на табло горит число 0. При нажатии на кнопку число на табло изменяется на 50 или 51. На кнопку нажали 2025 раз. Могло ли после этого на табло гореть число 25, если известно, что на табло не появлялись более чем двузначные числа, а также не появлялись отрицательные числа?

Источники: Всеросс, РЭ, 2025, 10.6 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

В этом процессе нужно найти полуинвариант.

Подсказка 2:

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

Подсказка 3:

Давайте в первую группу возьмём числа от 1 до 49, а во вторую от 50 до 99. Число из какой группы будет после 2025 нажатий?

Показать ответ и решение

Первое решение. Назовём числа 0, 1, …, 49 маленькими, а остальные числа, которые могут появиться на табло, т.е. числа 50, 51, …, 99 — большими. Заметим, что после нажатия из маленького числа обязательно получается большое, а из большого числа — маленькое. Значит, после нечётного количества операций на табло будет гореть большое число.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Выстроим все целые числа от 0 до 99 в цепочку

50− 0 − 51− 1− 52 − 2− 53− 3− 54− 4− ...− 97 − 47− 98− 48− 99− 49

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

Ответ:

не могло

Ошибка.
Попробуйте повторить позже

Задача 3#79803

На бесконечной ленте выписана некоторая конечная последовательность из $0$ и $1.$ Каждую секунду выбирается случайный кусок « $10$ » и заменяется на кусок « $011111$ ». Докажите, что рано или поздно процесс остановится.

Показать доказательство

Пронумеруем все единицы, начиная с самой левой, натуральными числами от $1$ до $n.$ Единице с номером $i$ поставим число $6ki,$ где $k i$ — количество нулей, которые находятся правее нее. Рассмотрим величину

n∑ S = 6ki i=1

Докажем, что она является полуинвариантом. Рассмотрим произвольный ход. Пусть он был произведен над единицей с номером $m.$ Тогда изменение $S$ составило

km km− 1 − 6 + 5⋅6 =− 1< 0

Таким образом, каждый ход уменьшает $S$ на $1,$ следовательно, процесс конечен.

Ошибка.
Попробуйте повторить позже

Задача 4#85560

На доске написано $20$ -буквенное слово, состоящее только из букв А и В. Назовем крутизной слова количество способов стереть некоторые его буквы так, чтобы на доске остались четыре буквы, образующих комбинацию ABBA. Например, слово ABBAAB имеет крутизну $2,$ поскольку нужную комбинацию можно получить двумя способами: $ABBA$ АВ и $ABB$ А $A$ В. Какова наибольшая возможная крутизна слова, выписанного на доске?

Подсказки к задаче

Подсказка 1

Таких 20-буквенных слов много… Давайте для начала посмотрим на одно любое слово и попробуем подвигать в нем какую-нибудь букву. Как изменилась крутизна? И вообще, какой порядок букв выбивается, что его изменение может повлиять на искомую величину?

Подсказка 2

Да, давайте рассмотрим случай, когда между двух букв В “зажата” A. Само по себе сочетание "ВАВ” в комбинацию не входит, поэтому вычеркивать из него буквы все равно придется. Что произойдет с крутизной, если мы эту букву А “выпустим”?

Подсказка 3

Если передвинуть А в сторону, где меньше остальных А, то крутизна слова увеличится. Почему? Попробуйте посмотреть на то, сколькими способами можно было составить комбинации до и после. Да, один из вариантов, где "запертая" буква А стояла первой или последней буквой ушли, но добавилось еще больше! Буквы В, образующие ушедшие комбинации же никуда не делись) Что это может сказать о том, как выглядит самое "крутое" слово?

Подсказка 4

Что оно имеет вид A...AB...BA...A. Мы ведь уже выяснили, что между буквами В А стоять не должно) Тогда, вспомнив как выглядит нужная нам комбинация, несложно выразить формулу, по которой находится крутизна в таком слове. Осталось найти, в каких случаях она становится максимальной! Не забывайте, что появляются ограничения на количество букв из-за того, что для составления комбинации должно быть хотя бы две буквы В и по одной букве А с обоих сторон :)

Показать ответ и решение

Возьмём произвольное слово длины $20$ и будем последовательно передвигать в нем буквы A, не уменьшая при этом крутизну слова. Ясно, что в нашем слове должно быть хотя бы две буквы B, иначе крутизна слова равна $0.$ Далее, предположим, что в слове между двумя буквами В есть буква А, т.е. слово имеет вид …В … $A$ …В …Посмотрим, с какой стороны от буквы $A$ больше букв А, и передвинем выделенную букву $A$ в тот конец слова, где их меньше. Заметим, что при таком перемещении буквы А мы могли разрушить лишь слова вида ABBA и ABBA, которые давали вклад в размер крутизны исходного слова. Предположим, что мы переместили букву К налево. Тогда слова вида $A$ BBA сохранились, а вместо слов вида ABB $A,$ образованных буквой В слева от $A$ и двух букв В и буквы $A,$ мы получим как минимум столько же слов, которые образуются из нашей передвинутой буквы $A,$ двух любых букв У и любой буквы А, которая стояла в исходном слове справа от буквы А. Получается, что мы можем рассматривать только слова вида А...АВ...ВА...А. Если в левом блоке будет $ℓ$ букв А, а в правом $− r$ букв А, то крутизна такого слова равна $ℓr⋅C220− (ℓ+r).$

Заметим, что при фиксированной сумме $ℓ+ r$ произведение $ℓr$ будет максимальным, если числа $ℓ$ и $r$ отличаются не больше чем на $1 :$ в противном случае, если, например, $ℓ≥r+ 2,$ то переместим одну букву $K$ из левого блока в правый, и крутизна изменится на

(ℓ− 1)(r+ 1)C220−(ℓ+r)− ℓrC220−(ℓ+r) =(ℓ− r− 1)C220− (ℓ+r) >0

Таким образом, можно считать, что $r= ℓ$ или $r =ℓ− 1,$ причем $1≤ ℓ≤9$ (иначе в нашем слове не будет или букв А, или букв В). Теперь возьмем слово, в котором $r=ℓ− 1,$ и заменим последнюю букву В на букву А. При такой замене крутизна слова изменится на величину

ℓ2C220−2ℓ− ℓ(ℓ− 1)C220−(2ℓ−1) = ℓ(10− ℓ)(21− 4ℓ)

Значит, при $ℓ≤ 5$ крутизна слова после такой замены увеличивается, а при $ℓ>5−$ уменьшается. Аналогично, посмотрим, что произойдёт, если в слове, в котором $r=ℓ,$ заменить первую букву В на букву A:

ℓ(ℓ+1)C220−(2ℓ+1)− ℓ2C220−2ℓ = ℓ(19− 2ℓ)(9− 2ℓ)

Получается, что при $ℓ <5$ крутизна слова после такой замены увеличивается, а при $ℓ≥ 5$ — уменьшается. Значит, мы можем последовательно совершать такие замены, сводя величину $ℓ$ к значению $5$ и увеличивая в процессе крутизну. В итоге, наибольшая крутизна будет у слова, в котором $ℓ=r =5,$ и равна она $52 ⋅C210.$

Замечание.

Последнюю часть решения можно провести по-другому. А именно, рассмотрим крутизну слова, в котором $r=ℓ$ , как функцию от $ℓ:S(ℓ)=$ $ℓ2C2 20−2ℓ$ . Вычислим ее производную: $S′(ℓ)= ℓ(8ℓ2− 117ℓ+ 380)$ . Нас интересует натуральная точка из отрезка $[1;9]$ , которая наиболее близка к нулю $ℓ0$ этой производной. Поскольку $4,5< ℓ0 < 5$ , в качестве такой точки необходимо выбрать число $ℓ= 5$ , что и приводит нас к примеру. Аналогичные вычисления для случая $r= ℓ− 1$ также дают значение $ℓ =5$ , но крутизна такого слова оказывается меньше.

Ответ:

$52⋅C2 = 1125 10$

Ошибка.
Попробуйте повторить позже

Задача 5#98551

На доске написаны несколько натуральных чисел. Каждую минуту выбирают какие-то два из них ( $x$ и $y)$ и заменяют их на числа $x− 2$ и $y+ 1.$ Докажите, что рано или поздно на доске появится отрицательное число.

Подсказки к задаче

Подсказка 1

Как изменится сумма всех чисел после применения операции?

Подсказка 2

Верно, уменьшится на 1. Какой вывод можно сделать?

Показать доказательство

Пусть сумма всех чисел на данный момент равна $S.$ После применения операции она станет равна

(S − x− y)+ (x− 2)+ (y+ 1)= S− 1

Таким образом, после применения операций сумма уменьшается. Значит, после достаточно большого количества операций сумма чисел на доске станет отрицательной. А это означает, что хотя бы одно из чисел будет отрицательным, то есть рано или поздно появится первое отрицательное число.

Ошибка.
Попробуйте повторить позже

Задача 6#98552

На доске записаны несколько чисел. За один ход разрешается любые два из них $a$ и $b,$ одновременно не равные нулю, заменить на числа $a− b∕2$ и $b +a∕2.$ Можно ли через несколько таких ходов получить на доске исходные числа?

Подсказки к задаче

Подсказка

Как изменится после применения операции сумма квадратов чисел, написанных на доске?

Показать ответ и решение

Рассмотрим сумму квадратов $S$ выписанных чисел. После применения указанной операции она становится равной

( b)2 ( a)2 1 S− a2− b2 + a −2 + b+ 2 =S + 4(a2+ b2)

Таким образом, сумма квадратов увеличивается. Значит, исходные числа никогда не получатся.

Ответ:

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#98553

За одну операцию из пары натуральных чисел $a,$ $b$ можно получить пару $a − 2b,$ $b,$ если $a >2b$ или пару $2b − a,$ $b,$ если $b<a <2b.$ Докажите, что через несколько таких операций окажется, что одно число в паре вдвое больше другого или числа окажутся равны.

Подсказки к задаче

Подсказка 1

Что может стать с суммой чисел пары после применения операции?

Подсказка 2

Верно! Сумма может либо уменьшиться, либо остаться прежней. Какие выводы можно сделать?

Показать доказательство

Пусть $a >b.$ Если $a> 2b,$ пара $(a,b)$ заменится на пару $(a− 2b,b),$ а если $a< 2b,$ пара $(a,b)$ заменится на пару $(a,2b− a).$ В первом случае сумма чисел пары уменьшилась с $a+ b$ на $a− b,$ а во втором сумма $a+b$ заменилась на $2b,$ что меньше $a +b$ при $a> b$ и равно $a+ b$ при $a =b.$ Поскольку сумма остается натуральной, рано или поздно процесс должен прекратиться или зациклиться. Он может прекратиться только если операцию нельзя выполнить. Это означает, что одно число вдвое меньше другого. Зацикливание же возможно только если сумма перестанет уменьшаться, а это может случиться только если числа станут равными.

Ошибка.
Попробуйте повторить позже

Задача 8#98554

В классе у каждого ученика не более $20$ врагов. Учитель поделил класс на две группы. Школьники хотят, чтобы у каждого ученика из первой группы было не более $5$ врагов внутри группы, а у каждого ученика из второй группы — не более $15$ врагов внутри группы. Каждый день одного из школьников, нарушающих это правило, коллективным решением переводят в другую группу. Докажите, что этот процесс когда-то завершится.

Подсказки к задаче

Подсказка 1

Обозначим S₁ и S₂ — количество пар враждующих ребят внутри первой и второй групп. Какую величину, связанную с этими числами можно рассмотреть, чтобы доказать утверждение задачи?

Подсказка 2

Рассмотрим 3S₁ + S₂. Как это число изменяется при переводе ребят между группами?

Показать доказательство

Будем считать школьников вершинами, а вражду — ребрами. Обозначим за $S 1$ и $S 2$ количество внутренних ребер в первой группе и второй группе соответственно. Рассмотрим величину $3S1+ S2.$ Легко понять, что при любом переводе данная величина уменьшится (хотя бы на 1), но уменьшаться бесконечно она не может, поэтому в какой-то момент процесс остановится.

Ошибка.
Попробуйте повторить позже

Задача 9#98555

В клетках таблицы $8× 8$ расставлены натуральные числа. Докажите, что у некоторых из этих чисел можно сменить знак таким образом, чтобы каждое из чисел отличалось по знаку от суммы чисел, стоящих в соседних с ним (по стороне или углу) клетках. (Ноль считается отличающимся по знаку от любого ненулевого числа).

Подсказки к задаче

Подсказка 1

Иногда в комбинаторных задачах на доказательство в случае отсутствия некоторого процесса его нужно организовать. Как это можно сделать в данной задаче?

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Произведение. Нам необходимо следить за всеми произведениями чисел на соседних клетках. Проще всего, объединить их в единственное значение, можно с помощью суммы. Таким образом, наш полуинвариант - сумма всевозможных произведений чисел на соседних клетках.

Подсказка 5

Мы уже поняли, что рассматриваемая величина уменьшается с каждым шагом алгоритма. Для завершение доказательства, осталось проверить, что величина ограничена при заданных на доске числах.

Показать доказательство

Рассмотрим величину $S,$ равную сумме всех произведений вида $ab,$ где числа $a$ и $b$ стоят в соседних клетках. Пусть мы пока не добились необходимого условия на знаки. Тогда есть число $x,$ сумма $Sx$ его соседей имеет тот же знак: $xSx > 0$ (неравенство строгое, поскольку числа целые(но ненулевые), а сумма не $0).$ Тогда поменяем знак у $x.$ Теперь $xSx <0,$ а, значит, вся величина $S$ тоже уменьшилась. Она ограничена снизу(возьмём все слагаемые из $S$ со знаком минус и получим минимум), поэтому процесс остановится, и мы получим расстановку, требуемую в условии.

Ошибка.
Попробуйте повторить позже

Задача 10#98556

Вася выписал в тетрадку несколько положительных чисел, меньших $1.$ Каждую минуту он стирает из тетрадки $2$ числа $a$ и $b,$ а затем записывает вместо них два числа $ab+1- 2 .$ Может ли процесс продолжаться бесконечно долго, если на каждом шаге стираемые числа $a$ и $b$ должны отличаться хотя бы на $-1-? 1000$

Подсказки к задаче

Подсказка 1

Сначала докажем, что все числа на доске ограничены. Предположим, что заменяется пара (a, b). Можно считать, что a > b, то есть b = a - t, где t ≥ 1/1000. Как при этом изменилось a?

Подсказка 2

Чтобы ответить на этот вопрос, рассмотрим функцию f(a) = a - (a(a - 1/1000)+1)/2. Ясно, что a - 1/1000 ≥ b. Тогда, зная знак f(a), можно будет оценить и изменение числа a. Как это сделать?

Подсказка 3

Верно! Сначала найдем знак f(a). Легко проверить, что на отрезке [0,1] у функции f(a) всего один ноль. Обозначим его x₀. Мы имеем дело с квадратичной функцией, причем старший коэффициент ее отрицателен. Тогда можно понять, что если a > x₀, то новое число стало меньше, чем a. А как проверить, что новое число получилось не больше какого-то наперед заданного?

Подсказка 4

Точно! Тогда новое число (ab+1)/2 ≤ (a²+1)/2 ≤ ((x₀)²+1)/2. Итак, наши числа ограничены. А как меняется сумма чисел после k-ой минуты?

Подсказка 5

Если стирается пара (a,b), то эта сумма равна (1-a)(1-b). Поскольку a, b < C, то (1-a)(1-b) > (1 - C)². В чем выходит противоречие, если операция применяется бесконечно долго?

Показать ответ и решение

Лемма. Докажем, что для любого начального набора чисел существует число $C < 1$ такое, что на доске никогда не появится числа больше, чем $C.$

Доказательство. Рассмотрим произвольную пару $(a,b),$ которую стерли в некоторый момент времени. Без ограничений общности можем считать, что $a> b,$ тогда $b= a− t,$ при некотором $t≥ 1∕1000.$ Рассмотрим функцию

a(a− 1∕1000)+ 1 f(a)= a− ------2------

Легко проверить, что на отрезке $[0,1]$ решение уравнения $f(a) =0$ единственно (для этого можно решить квадратное это уравнение). Далее рассмотрим два случая:

$1.$ Если $a> x0,$ то $f(a)> 0,$ следовательно,

a> a(a−-1∕1000)+-1 ≥ ab+-1 2 2

то есть большое из чисел пары не увеличилось.

$2.$ Если $a≤ x0,$ то

ab+-1< a2+-1≤ x20+-1 2 2 2

Наконец, если $M$ — максимальное число начального набора, то на доске никогда не появится числа, которое было бы больше, чем $( x20+1) C = max M, 2 .$

______________________________________________________________________________________________________________________________________________________

Перейдем к доказательству основной задачи. Пусть $Sk$ — сумма чисел после минуты $k.$ Тогда для произвольного $n,$ в силу леммы,

ab+-1 ab+-1 2 Sn+1− Sn = 2 + 2 − (a +b)= (1− a)(1− b)>(1− C)

Таким образом, после каждого шага сумма чисел на доске увеличивается не меньше, чем на $2 (1− C) .$

Наконец, если данный процесс будет продолжаться бесконечно долго, то сумма чисел может быть сколько угодно большой, что невозможно.

Ответ:

Нет, не может

Ошибка.
Попробуйте повторить позже

Задача 11#98557

В год выборов все города страны $N$ подняли над ратушами флаги — красные либо синие. Каждый день жители узнают цвета флагов у соседей в радиусе $100$ км. Один из городов, где у большинства соседей флаги другого цвета, меняет свой флаг на этот другой цвет. Докажите, что со временем смены цвета флагов прекратятся.

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Верно! Будем красить вершину в цвет флага над ратушей. Пусть через k дней у нас есть A ребер с концами разного цвета, а на следующий день таких ребер B. Что больше: A или B?

Подсказка 3

Точно! Если вершина v перекрашена на k-ый день в красный цвет. Тогда смежных с ней вершин красного цвета больше, чем синих. Какой вывод можно сделать?

Показать доказательство

Рассмотрим граф $G.$ Каждому городу страны $N$ сопоставим вершину данного графа. Соединим ребрами те и только те вершины, которые соответствуют городам, расстояние между которыми не превосходит $100$ км. Будем красить вершину в цвет флага над ратушей соответствующего города.

Пусть $Sk$ — количество ребер с концами разного цвета после дня $k.$ Покажем, что для любого $n$ верно, что $Sn+1 < Sn.$ Действительно, без ограничений общности, пусть в соответствующий день вершина $v$ графа поменяла свой цвет с синего на красный, но тогда смежных с ней вершин красного цвета больше, чем тех же вершин синего цвета, но тогда количество ребер с концами разного цвета уменьшилось по крайней мере на $1.$

Таким образом, не позже чем, через $S1$ дней данный процесс закончится.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#74789

Клетки кубической таблицы $7× 7× 7$ (то есть маленькие кубики) пронумеровали по порядку числами от 1 до 343. (Сначала нумеруются клетки верхнего слоя: в первой строке слева направо от 1 до 7, в следующей от 8 до 14, и так далее до 49. Далее в таком же порядке нумеруются Клетки второго слоя и т. А.) После этого из таблицы удалили несколько непересекающихся кубов $2× 2× 2$ , а все оставшиеся числа сложили. Чему может равняться остаток от деления полученной суммы на 8 ?

Источники: ФЕ-2022, 11.6 (см. www.formulo.org)

Подсказки к задаче

Подсказка 1

Попробуем выразить числа на удаленном кубе через переменную. Так мы сможем посчитать их сумму.

Подсказка 2

Заметим, что сумма всех числе равна 8a+4*57. Что тогда можем сказать об изменении остатка от деления на 8?

Подсказка 3

Он либо сохраняет, либо изменяет остаток на 4!

Показать ответ и решение

Рассмотрим произвольный вырезаемый куб $2×2 ×2$ . Если наименьшее число обозначить $a$ , то остальные числа будут $a+ 1,a+7,a+ 8,a +49,a+49+ 1,a +49+ 7$ , $a+ 49 +8$ . Значит, их сумма $− 8a +4× 1+ 4× 7+4 ×49= 8a+ 4×57$ , то есть имеет остаток 4 от деления на 8. Значит, вырезание кубиков либо сохраняет суммарный остаток от деления на 8, либо изменяет его на 4. Осталось узнать, чему этот остаток равнялся изначально. Сумма чисел от 1 до 343 равна их среднему арифметическому $(1+343 ) 2 = 172$ на их количество 343. 172 делится на 4 , но не на 8 , а 343 нечётно, поэтому исходный остаток равен 4.

Ответ:

0 или 4

Ошибка.
Попробуйте повторить позже

Задача 13#83163

В клетках таблицы $99× 99$ расставлены плюсы и минусы. Если в каком-то ряду (строке или столбце) минусов больше чем плюсов, разрешается в этом ряду поменять все знаки на противоположные. Докажите, что через некоторое время и во всех строках, и во всех столбцах плюсов будет больше чем минусов.

Показать доказательство

Заметим следующий полуинвариант: количество плюсиков во всей таблице после операции увеличивается. Действительно, рассмотрим строчку или столбец в котором мы проводили операцию, во всей доске, кроме рассмотренной линии, количество плюсов не изменилось, а в самой линии увеличилось, поэтому и во всей доске увеличилось. Теперь поймем, что количество плюсиков не может стать больше $2 99$ , поэтому количество проделанных операций конечно (за каждую операцию количество плюсиков увеличивается хотя бы на 1 и ограничено числом $2 99$ )). Осталось теперь рассмотреть момент, когда мы не можем сделать операцию, если бы нашлась линия, в которой минусов больше чем плюсов, то мы бы смогли применить к ней операцию и увеличить число плюсов, что противоречит рассмотренному моменту.

Ошибка.
Попробуйте повторить позже

Задача 14#83165

У каждого депутата в парламенте не более трёх врагов (вражда обоюдна). Парламент разбит на 2 палаты. Каждый день один из депутатов, обнаружив в своей палате не менее двух врагов, переходит в другую палату. Докажите, что рано или поздно переходы прекратятся.

Показать доказательство

Давайте рассмотрим на количество пар враждующих между палатами. Заметим, что оно увеличивается. Действительно, для того чтобы депутат сделал переход из палаты А в палату Б, у него в палате А должно быть хотя бы 2 врага, тогда между палатами у него не больше 1 врага (так как всего не больше 3-х врагов). После его перехода между палатами у него стало хотя бы 2 вражды. Значит, количество враждующих пар между палатами увеличивается. Общее количество пар врагов число конечно, количество пар врагов между палатами не может его перерасти, поэтому в какой-то момент переходы прекратятся.

Ошибка.
Попробуйте повторить позже

Задача 15#108047

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

Источники: Всесиб-2020, 11.5 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Хочется найти что-то, что в процессе меняется каким-то понятным образом, то есть полуинвариант.

Подсказка 2

Учитывая, что за операцию можно удалить количество камней в куче, возникает логичная мысль: следить за степенью вхождения двойки в количество камней в каждой куче.

Подсказка 3

Что можно сказать про степени вхождения двойки в куче A и B, если сделали операцию: переложили из A в B? Могла ли какая-то из степеней уменьшиться? Могла так случиться, что никакая из степеней не увеличилась?

Подсказка 4

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

Подсказка 5

Пусть теперь количество камней N = 2^t(2k+1). Предположим, что камни можно сложить в одну кучу. Попробуйте проделать операции в обратном порядке. Поищите противоречие, связанное с делимостью.

Показать доказательство

Для каждой кучки назовём её показателем максимальную степень двойки, на которую делится число содержащихся в ней камней, она может быть равна $0 1 =2$ . Рассмотрим поведение показателей кучек, участвующих в перекладывании. После перекладывания камней из кучки с $a 2 (2k+1)$ камнями в кучку с $b 2 (2l+ 1)$ камнями в первой остаётся $a b 2 (2k +1)− 2(2l+1)$ камней, а во второй становится $b+1 2 (2l+1)$ камней. Если $a= b$ , то

a b a+1 2 (2k+ 1)− 2 (2l+ 1)=2 (k− l),

поэтому оба показателя возрастут. Если $a⁄= b$ , то

a b c 2 (2k+ 1)− 2(2l+ 1)= 2(2m+ 1),

где $c =min{a,b}$ . При этом минимальный в данной паре кучек показатель сохраняется, а второй гарантированно становится больше минимального. Заметим, что количество кучек с минимальным среди всех показателем при произвольном перекладывании либо уменьшается на 2, либо не меняется.

Рассмотрим произвольную раскладку $N = 2t$ камней по более, чем одной кучке. В ней число кучек с минимальным показателем $2s,s<t$ будет чётным. Действительно, общее число камней $N = 2t$ и сумма количеств камней в не минимальных кучках делятся на $2s+1$ поэтому сумма количеств камней в минимальных кучках тоже делится на $2s+1$ , значит, их количество делится на 2. Если в раскладке есть хотя бы две кучки, разбиваем все кучки с минимальным показателем на пары, выполняем в каждой перекладывание из большей в меньшую и получаем раскладку с большим минимальным показателем, чем рассматриваемая. Проделав эту процедуру не более, чем $t$ раз, получим раскладку с минимальным показателем $t$ , то есть с единственной кучкой из $t 2 = N$ камней.

Пусть теперь $t N = 2(2k +1),k ≥1$ не является степенью двойки. Рассмотрим любой процесс сборки некоторой раскладки N камней по кучкам в одну и произведём его в обратном порядке, посредством процедур перекладывания, обратных к исходным, когда половина одной из кучек перекладывается в другую. При этом в обратном процессе количество камней в первой кучке (она же последняя в исходном процессе сборки) и всех получающихся на каждом шаге будет делиться на нечётное число $2k+ 1$ . Следовательно, любая раскладка, в которой есть кучка из числа камней, не делящегося на $2k+ 1$ , не может быть собрана в одной кучке. В частности, не может быть собрана в одну раскладка ${1, N − 1}$ по двум кучкам.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. В случае $N =2t(2k +1)$ можно предложить другое решение того, что раскладка ${1, N− 1}$ по двум кучкам не может быть собрана в одну. Этого достаточно для доказательства необходимости в условии задачи, то есть того, что любая начальная раскладка N камней по кучкам может быть собрана в одной куче только тогда, когда N является степенью двойки.

Докажем по индукции, что после $k$ перекладываний количества камней в кучках имеют вид

{ } 2k− ak⋅N,(ak+ 1)⋅N − 2k

для некоторого целого числа $ak ≥0$ .

База индукции при $k = 0$ очевидна:

{1,N − 1}= {z0 − 0⋅N,1⋅N − 20},

то есть $a0 = 0$ .

Шаг индукции: либо мы перекладываем камни из правой кучки в левую, тогда в левой станет $2k+1 − 2akN$ , а в правой останется $(2ak+ 1)N − 2k+1$ камней, при этом $ak+1 = 2ak$ , либо мы перекладываем камни из левой кучки в правую, тогда в левой останется $2k+1− (2ak+ 1)N$ , а в правой станет $2(ak +1)N − 2k+1$ камней, при этом $ak+1 = 2ak+ 1$ .

Если после некоторого $k$ -ого перекладывания раскладки ${1, N − 1}$ останется всего одна кучка, то число камней в другой станет равным 0 , следовательно, выполнится равенство одно из равенств $2k− ak⋅N =0$ или $(ak+ 1)⋅N − 2k =0$ . В обоих случаях N будет делителем числа $2k$ , то есть тоже степенью двойки противоречие с тем, что в рассматриваемом случае $N = 2t(2k+ 1)$ . Следовательно, при любом N , отличном от степени двойки, раскладка ${1, N$ $1}$ не может быть собрана в одну кучку.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Объединяя оба случая $N = 2t$ и $N = 2t(2k +1)$ , получаем доказательство более общего утверждения: раскладка N камней может быть собрана в одной кучке тогда и только тогда, когда количество камней в каждой её кучке делится на набольший нечётный делитель N .

Ошибка.
Попробуйте повторить позже

Задача 16#94114

На экране компьютера горит число, большее $10000.$ Каждую секунду из числа на экране вычитается его первая цифра. Докажите, что на экране обязательно появится либо $2017,$ либо $2018.$

Источники: Лига открытий - 2017

Показать доказательство

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

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#114365

Карлсон написал дробь $5. 8$ Малыш может:

- прибавлять любое натуральное число к числителю и знаменателю одновременно,

- умножать числитель и знаменатель на одно и то же натуральное число.

Сможет ли Малыш с помощью этих действий получить дробь, равную $3 5?$

Показать ответ и решение

Заметим, что при обоих разрешённых действиях дробь не уменьшается и всегда остается меньше единицы.

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

Пусть на некотором шаге имеется дробь $a∕b$ , где $a< b$ . Мы из нее получаем дробь $a+k b+k$ , тогда $a +k <b+ k$ . Чтобы доказать неравенство

a a +k b < b+-k

просто перемножим крест-накрест, получив

a(b+ k)<b(a+k),

что равносильно

ak< bk

Последнее неравенство очевидно следует из $a< b$ .

Итак, дробь уменьшаться при действиях Малыша не может. Но исходная дробь $5∕8$ больше, чем $3∕5$ . Значит, у Малыша не выйдет получить дробь, равную $3∕5$ .

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 18#83164

На доске написаны три числа. Каждую минуту они изменяются по следующему правилу: если на данный момент на доске находятся числа $x$ , $y$ , $z$ , то они меняются на $2x− 2y+ z− 1$ , $2y− 2z+x − 1$ , $2z− 2x+y − 1$ соответственно. Докажите, что когда-нибудь на доске появится отрицательное число.

Показать доказательство

Давайте проверим сумму всех чисел. Была: $x +y+ z$ , стала: $2x− 2y +z− 1+ 2y− 2z+ x− 1+ 2z− 2x+ y− 1= x+ y+ z− 3$ . То есть сумма является полуинвариантом и всегда уменьшается на $3$ , а значит, когда-то она станет отрицательной, но тогда хотя бы одно из чисел отрицательно, что нам и требовалось доказать.

Мысль: Видишь задачу с процессом? Перебери самые популярные инварианты и полуинварианты: четность, сумма, произведение, площадь, периметр, делимость.