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

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

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

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

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

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

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

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

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

Задача 1#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,$ следовательно, процесс конечен.

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

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

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

Задача 2#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$

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

Задача 3#98551

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

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

Подсказка 1

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

Подсказка 2

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

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

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

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

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

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

Задача 4#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)

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

Ответ:

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

Задача 5#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.$ Поскольку сумма остается натуральной, рано или поздно процесс должен прекратиться или зациклиться. Он может прекратиться только если операцию нельзя выполнить. Это означает, что одно число вдвое меньше другого. Зацикливание же возможно только если сумма перестанет уменьшаться, а это может случиться только если числа станут равными.

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

Задача 6#98554

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

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

Подсказка 1

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

Подсказка 2

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

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

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

Курсы

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

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

Задача 7#98555

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 5

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

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

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

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

Задача 8#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) .$

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

Ответ:

Нет, не может

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

Задача 9#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$ дней данный процесс закончится.

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

Задача 10#34066

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

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

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

Ответ:

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

Задача 11#34068

Есть 10 целых различных чисел. За одну операцию можно два неравных целых числа заменить на два равных целых с той же суммой. Может ли процесс продолжаться бесконечно?

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

Будем следить за суммой квадратов всех чисел. Покажем, что за каждую операцию она уменьшается, причем хотя бы на $1∕2.$ Пусть у нас есть два различных целых числа $a$ и $b,$ после операции у нас будет два числа $a+b- 2 .$ Тогда нам нужно понять, почему $2 2 (a+b)2 1 a + b − -2---≥2.$ Действительно, умножим обе части на $2$

2a2+2b2− (a+ b)2 ≥1

2 (a− b) ≥ 1

Последнее неравенство верно, так как $a$ и $b$ целые числа, причём различные. Значит, исходное неравенство верно, и мы получаем, что сумма квадратов всех чисел уменьшается после каждой операции хотя бы на $1∕2.$ Но сумма квадратов не может уменьшаться бесконечно, так как она как минимум больше нуля. Получается, что процесс конечен.

Ответ:

Нет, не может

Интенсивы

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

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

Задача 12#74789

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

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

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

Подсказка 1

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

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

Рассмотрим произвольный вырезаемый куб $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#94114

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

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

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

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

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

Задача 16#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$ , а значит, когда-то она станет отрицательной, но тогда хотя бы одно из чисел отрицательно, что нам и требовалось доказать.

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

Предыдущий раздел

Следующий раздел