Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Применение классических комбинаторных методов к разным задачам

Тема КОМБИНАТОРИКА

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

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

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

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

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

Подтемы раздела комбинаторика

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

Вероятностный метод (усреднение)

Индукция в комбинаторике

Дискретная непрерывность

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

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

Задача 81#90823Максимум баллов за задание: 7

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

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

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

Предположим, что какие-то два из отрезков ( $AB$ и $CD$ ) имеют общую точку $O$ .

$PIC$

Применим неравенство треугольника:

AO + OD > AD, BO +OC > BC

Сложим эти неравенства:

(AO + BO)+ (OD + OC )>AD + BC

AB + CD > AD +BC

Тогда если мы поменяем пары $AB,CD$ в разбиении на пары $AD, CB,$ то сумма длин проведенных отрезков уменьшится. Но это противоречит минимальности суммы длин во взятом разбиении на пары.

Второй способ. Мысленно проведем всевозможные отрезки между $2n$ точками. Их конечное число, а возможных направлений прямых на плоскости бесконечно. Тогда найдется прямая, которая не параллельна ни одному из отрезков. Введем декартову систему координат на плоскости, где эта прямая будет осью абсцисс.

Так как ось абсцисс не параллельна ни одному из отрезков между $2n$ точками, у всех точек будут различные ординаты. Тогда пронумеруем точки сверху вниз. И проведём отрезки, соединяющие $2$ самые “верхние” точки, затем следующие по высоте $2$ точки и так далее. (Пример на картинке)

$PIC$

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

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

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

Задача 82#94915Максимум баллов за задание: 7

На полке стоит $55$ томов собрания сочинений В.И.Ленина. За раз разрешается взять несколько подряд идущих томов и переставить их в обратном порядке. Докажите, что такими операциями можно расставить тома по порядку.

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

Будем решать задачу для $n$ томов.

База для $n= 1$ и $n= 2.$ Для $n =1$ расстановка верна. Для $n= 2$ либо порядок уже верен, либо его можно изменить за один ход из $2,1$ в $1,2.$

Переход: $n→ n +1$

Найдём, где стоит $(n +1)−$ й том. Возьмём блок, начинающийся с этого тома до последнего, и переставим книги в нём в обратном порядке. Тем самым получаем следующую расстановку: тома с $1−$ го по $n−$ й стоят в произвольном порядке, а $(n+ 1)−$ й том находится на последнем месте. Теперь можно применить индукцию к первым $n$ томам. Получаем верную расстановку $(n+ 1)−$ го тома. Переход доказан.

Значит, и 55 томов можно расставить.

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

Задача 83#94936Максимум баллов за задание: 7

Торт разрезали прямолинейными разрезами на несколько кусков. Оказалось, что одна сторона у ножа была грязная. Докажите, что всегда найдётся хотя бы один чистый кусок.

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

База для $n = 1$ очевидна.

Переход: $n→ n +1$

Рассмотрим ситуацию перед последним разрезом. К этому моменту было уже $n$ действий. По предположению индукции, после $n$ разрезов остаётся чистый кусок. После $(n+1)−$ го разреза этот кусок мог остаться нетронутым или мог быть разрезан на две части, но так как нож с одной стороны чистый, то с этой стороны кусок также останется полностью чистым. Значит, после $(n +1)−$ го разреза найдётся чистый кусок. Переход доказан.

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

Задача 84#94938Максимум баллов за задание: 7

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

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

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

База для $n= 1$ очевидна.

Переход: $n→ n +1$ . Будем воспринимать лестницу из $(n+ 1)−$ й ступеньки как лестницу из $n$ ступенек и ещё одной дополнительной ступеньки.

Первое решение. Если человек стоит на $(n +1)−$ й ступеньке и при следующем ходе уходит с лестницы, то переход доказан. Если первым ходом он попадает на лестницу из $n$ ступенек, то будем считать, что он изначально стоял на ней.

(*) Пусть человек стоит на лестнице из $n$ ступенек. По предположению индукции он точно покинет её. Если он сойдёт с её 1-й ступеньки, то переход доказан. Если нет, то он встанет на $(n+ 1)$ -ю ступеньку. Здесь возможны два варианта: если на этой ступеньке стрелка показывает в сторону окончания лестницы, то переход доказан. Если нет, то стрелка развернётся в сторону выхода, и человек снова окажется на лестнице из $n$ ступенек. Рассуждения с места (*) повторятся, но теперь, в случае попадания на $(n +1)−$ ю ступеньку, мы гарантируем, что он выйдет с лестницы. Переход доказан.

Второе решение. Предположим, что человек может бесконечно ходить по лестнице из $(n+ 1)−$ й ступеньки. На $(n+ 1)−$ ю ступеньку он может встать не более одного раза, потому что если он встал на неё и сошёл на $n−$ ю ступеньку, то стрелка развернулась в сторону выхода, и в следующий раз при наступлении на неё человек точно сойдёт с лестницы. Тогда если человек не становится на $(n+ 1)−$ ю ступеньку, то он бесконечно ходит по лестнице из $n$ ступенек, что противоречит предположению индукции. Если он всё-таки встал на $(n+ 1)−$ ю ступеньку, то до этого он сделал конечное число шагов, а продолжить бесконечное число шагов он должен на лестнице из $n$ ступенек, что снова противоречит предположению индукции. Противоречие. Значит, он обязательно сойдёт с лестницы.

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

Задача 85#96342Максимум баллов за задание: 7

Докажите, что среди любых $25$ различных положительных вещественных чисел можно выбрать два, сумма и разность которых не совпадают ни с одним из оставшихся $23$ чисел.

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

Данное утверждение верно для $n$ чисел при любом $n≥ 4$ и доказывается «от противного».

Предположим, что сумма или разность любых двух из $n$ разлчных чисел $a1 < a2 <...< an−1 <an$ cодержится среди остальных $n − 2$ чисел. Тогда

an+ ai > an =⇒ an− ai = an−1,

где $1 ≤i≤ n− 1.$

При четном $n= 2k$ получаем

an− ak =ak

значит, разность $an$ и $ak$ не содержится среди остальных чисел.

При нечетном $n= 2k +1$ надо рассмотреть пары $(an−1;ai).$ Для них

an−1+a1 =an

an−1+ a> an i

при $2≤ i≤n − 2$ и потому должны выполняться равенства

an−1− ai =an−i−1

в частности

an−1− ak =ak

что также приводит к противоречию.

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

Задача 86#96610Максимум баллов за задание: 7

Взяли несколько одинаковых равносторонних треугольников. Вершины каждого из них пометили цифрами $1,$ $2$ и $3.$ Затем их сложили в стопку. Могло ли оказаться, что сумма чисел, находящихся в каждом углу, равна $55?$

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

Подсказка 1

Попробуйте сложить в стопку несколько таких треугольников. Что можно сказать про сумму чисел в каждом углу? А про общую сумму?

Подсказка 2

Посмотрите, на что делится сумма чисел во всех углах!

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

Сумма чисел в вершинах каждого треугольника равняется $6.$ Поэтому сумма чисел во всех углах стопки должна делиться на $6.$ Но если в каждом углу стопки сумма чисел равна $55,$ то сумма всех чисел равна $55 ⋅3$ — не делится на $6.$

Ответ:

Нет

Курсы

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

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

Задача 87#97573Максимум баллов за задание: 7

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

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

Подсказка 1

Рассмотрим город A, из которого ведет больше всего дорог. Попробуйте доказать, что это как раз город, который мы искали.

Подсказка 2

Рассмотрим город B, из которого идет дорога в A. Тогда попробуйте доказать, что найдется город С такой, что в него идет дорого из A и не идет дорога из B.

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

Рассмотрим город $A,$ из которого выходит наибольшее число дорог, и произвольный город $B.$ Если дорога ведёт из $A$ в $B,$ то всё в порядке. Если же дорога ведёт из $B$ в $A,$ то, поскольку из $B$ выходит не больше дорог, чем из $A,$ найдётся город $C,$ в который ведёт дорога из $A,$ но не ведёт дорога из $B.$ Тогда можно из $A$ попасть в $B$ по маршруту $A → C → B.$

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

Задача 88#97574Максимум баллов за задание: 7

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

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

Подсказка 1

Конечно, в этой задаче хочется использовать индукцию. К сожалению, при n=3 существует контрпример, поэтому переход стоит делать от n к n+2.

Подсказка 2

Мы хотим "расширить" наш пример. По предположению индукции точно есть цепочка, в которой хотя бы n человек. Нетрудно получить решение, если их n+1, но вот встроить оставшихся двух человек не получается. Что тогда можно сделать?

Подсказка 3

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

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

Докажем утверждение по индукции. База $n =2$ очевидна. Переход будем делать, добавляя по $2$ человека. Пусть для $2k$ человек их можно расставить, как требуется по условию. Покажем, что и $2k +2$ тоже можно. Выделим в этих $2k+ 2$ самую длинную цепочку, подходящую по условию. По предположению индукции там хотя бы $2k$ человек.

1.: Предположим, что там $2k+ 1$ человек. Без ограничения общности, можно считать, что крайние люди $A$ и $B$ проиграли своим соседям (по чётности их результаты будут одинаковы). Будем писать $A >B,$ если $A$ выиграл у $B.$ Без ограничения общности, можно считать, что $A >B.$ Рассмотрим оставшегося человека $X.$ Если он выиграл у $A$ или у $B,$ то можно увеличить цепочку, добавив $X$ на край. Значит, $X < A$ и $X < B.$ Тогда переставим $A$ на другой край, а потом на тот же край поставим $X.$ Получим подходящую цепочку $B < A >X.$ Мы в любом случае сможем добавить человека $X,$ что и хотели.
2.: Предположим, что там $2k$ человек. Тогда уберём одного с краю, останется три человека. Опять можно считать, что крайние люди $A$ и $B$ проигравшие и $A >B$ . Пусть их зовут $X,Y,Z.$ Среди них обязательно есть человек, который одному проиграл, а у другого выиграл. Пусть это $Y$ и $X > Y > Z.$ Посмотрим, как $Y$ сыграл с $A.$ Если $Y > A,$ то добавим на край после $A$ $Y,$ а потом $Z.$ Получим корректную цепочку $Z <Y > A.$ Теперь в ней $2k+ 1$ человек, противоречие. Пусть $Y < A.$ Тогда перекинем $A$ на другой край, допишем за ним $Y,$ а дальше $X.$ Снова получим цепочку, которая теперь кончается на $B < A> Y <X$ и в ней $2k +1$ человек. Так что мы всегда сможем найти увеличить нашу цепочку, пока в ней не станет $2k+ 2$ человек, ЧТД.

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

Задача 89#97823Максимум баллов за задание: 7

Докажите, что вершины любого графа можно покрасить в $d$ цветов так, чтобы доля ребер с одноцветными концами была не более $1∕d.$

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

Подсказка 1

Рассмотрите все раскраски вершин. Таких всего n^d, где d - количество вершин. Как доказать, что среди них есть хорошая?

Подсказка 2

Можно доказать, что плохих раскрасок меньше, чем всего раскрасок. Оцените через количество ребер число плохих раскрасок.

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

Пусть в графе $n$ вершин и $k$ ребер. Рассмотрим все $nd$ расскаросок графа в $d$ цветов. Предположим противное, то есть в каждой раскраске больше, чем $k d$ одноцветных ребер.

Посчитаем количество одноцветных ребер во всех раскрасках. С одной стороны их больше $k d knd d × n = d .$ Теперь посчитаем в скольки раскрасках наше ребро одноцветное, для этого обе вершины должны быть одного цвета, тогда раскрасок, где ребро одноцветное ровно $nd d-,$ суммируя по всем ребрам получим $d knd-$ — противоречие, так как мы показали, что их больше, значит, изначальное предположение неверно, то есть вершины любого графа можно покрасить в $d$ цветов так, чтобы доля ребер с одноцветными концами была не более $1∕d.$

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

Задача 90#97824Максимум баллов за задание: 7

Докажите, что числа $1,2,...,2022$ можно покрасить в четыре цвета так, чтобы не было одноцветных арифметических прогрессий из $10$ членов.

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

Подсказка 1

Как доказать, что существует хорошая раскраска чисел? Можно рассмотреть все раскраски и показать, что «плохих» меньше. Как оценить количество плохих раскрасок?

Подсказка 2

Чтоб оценить количество плохих раскрасок, нам нужно научиться считать число арифметических прогрессий длины 10. Зная это количество, мы сможем понять, в скольких раскрасках она одноцветная. Как всё-таки найти это количество?

Подсказка 3

Арифметическая прогрессия длины 10 задается первым членом, последним членом, такими, что их разность кратна 9(поймите почему это так). Как после этого наблюдения посчитать количество арифметических прогрессий?

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

Рассмотрим все $42022$ раскрасок чисел от $1$ до $2022$ в $4$ цвета. Найдем количество “плохих” раскрасок, если это число окажется меньше, чем $2022 4 ,$ то искомая раскраска существует.

Посчитаем количество арифметических прогрессий длины $10,$ состоящих из натуральных чисел, не превосходящих $2022.$ Для задания арифметической последовательности длины $10,$ достаточно определить первое и последнее число, так чтобы их разность делилась на $9,$ то есть у выбраных чисел совпадали остатки при делении на $9,$ тогда искомое количество равно $2 2 3⋅C224+ 6⋅C225.$

Для каждой арифметической прогрессии существует ровно $2012 4 ⋅4$ “плохих” расскрасок. Действительно саму прогрессию можно покрасить в один из $4$ цветов, а остальные числа как угодно.

Тогда общее количество “плохих” раскрасок не превышает $( 2 2 ) 2012 3⋅C224+6 ⋅C 225 4 ,$ что меньше, чем $2022 4 ,$ значит, “хорошие” раскраски существуют.

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

Задача 91#97825Максимум баллов за задание: 7

В классе $n$ учеников. Каждую неделю ровно $k$ из них дежурят. Докажите, что если прошло меньше $tk−1$ недель, то всех учеников можно разбить на $t$ групп так, чтобы в каждом дежурстве принимали участие ученики хотя бы из двух групп.

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

Подсказка 1

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

Подсказка 2

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

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

Будем считать, что в группе может быть $0$ людей. Пусть прошло $tk−1− 𝜖$ недель. Рассмотрим произвольное разбиение всех учеников на $t$ групп. Всего существует ровно $n t$ способов так сделать. Посчитаем количество плохих разбиений, то есть тех, где найдется дежурство, в котором принимали участие ученики из одной группы. Возьмем этих $k$ учащихся, они принадлежат одной из $t$ групп, дежурили они вместе в одну из $k− 1 t − 𝜖$ недель, а остальных можно распределить по группам $n−k t$ способами. Тогда плохих распределений не более $(k−1 ) n−k n t − 𝜖 ⋅t ⋅t< t .$ Значит, найдется хорошее распределение по группам.

Интенсивы

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

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

Задача 92#97826Максимум баллов за задание: 7

Рассмотрим двудольный граф $G = (V,E)$ с $n$ вершинами. Пусть для каждой вершины $v ∈V$ задан список $S(v)$ из более чем $log n 2$ цветов. Докажите, что существует правильная раскраска вершин графа $G,$ приписывающая каждой вершине $v$ цвет из ее списка $S(v).$

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

Подсказка 1

Как можно покрасить двудольный граф правильно? Вообще достаточно двух цветов, одну долю можно покрасить в первый цвет, а другую во второй. Но у нас цветов больше, как быть? Можно все цвета распределить на 2 группы. Как можно это сделать?

Подсказка 2

Рассмотрите все разбиения цветов на 2 группы. Когда разбиение плохое? Только тогда, когда все цвета какой-то вершины попали в другую группу. С какой вероятностью это произошло?

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

Пусть $C$ — множество всех цветов в наборах. Рассморим всевозможные разбиения $C$ на $2$ непустые группы: первую и вторую. Тогда если удастся найти разбиение, такое что у всех вершин из первой доли будет цвет из первой группы, а у второй — из второй, то мы сможем выбрать цвета правильным образом. Далее будем доказывать, что такое разбиение существует.

Очевидно, что каждый цвет побывает в первой и второй группе поровну раз, поэтому вероятность того, что цвет в определенной группе составляет $1 2.$ Пусть какое-то разбиение не подошло, значит, существует вершина, все цвета которой попали в другую группу, вероятность такого события составляет $1- 2k,$ где $k$ — количество цветов в списке вершины. В силу того, что список состоит более чем из $log2n$ цветов, то данная вероятность строго меньше $1 n.$ Суммируя по всем вершинам, получим число меньшее единицы, значит, существует правильная раскраска вершин графа $G.$

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

Задача 93#98551Максимум баллов за задание: 7

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

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

Подсказка 1

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

Подсказка 2

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

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

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

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

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

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

Задача 94#98552Максимум баллов за задание: 7

На доске записаны несколько чисел. За один ход разрешается любые два из них $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)

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

Ответ:

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

Задача 95#98553Максимум баллов за задание: 7

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

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

Задача 96#98554Максимум баллов за задание: 7

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

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

Подсказка 1

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

Подсказка 2

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

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

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

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

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

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

Задача 97#98555Максимум баллов за задание: 7

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 5

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

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

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

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

Задача 98#98556Максимум баллов за задание: 7

Вася выписал в тетрадку несколько положительных чисел, меньших $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) .$

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

Ответ:

Нет, не может

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

Задача 99#98557Максимум баллов за задание: 7

В год выборов все города страны $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$ дней данный процесс закончится.

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

Задача 100#99359Максимум баллов за задание: 7

Будем говорить, что число $N$ обладает свойством $RRR(m,n),$ если в любой компании из $N$ человек найдутся либо $m$ попарно знакомых, либо $n$ попарно незнакомых. Наименьшее из таких чисел будем называть $R(m,n).$ Докажите, что $n∕2 R(n,n)≥ 2$ при $n ≥2.$

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

Переведём задачу сразу на язык графов так, что человек — вершина, а рёбра(антирёбра) — знакомство(незнакомство). Заметим, что при $n =2$ задача очевидна, поэтому будем считать, что $n ≥3.$ Рассмотри число $N,$ которое меньше, чем $n∕2 2 .$ Тогда всего графов на $N$ вершинах $N(N−1) 2 2 .$ Идея доказательства следующая: если графов, содержащих клику, $N(N−-1) < 2--22---$ (аналогично для антиклик), то существует граф, в котором нет ни того, ни другого, а значит $N < R(n,n).$ Всего графов на $N$ вершинах, содержащих клику на данных $n$ вершинах, $N (N−1) n(n−1) 2---2- −--2--.$ Следовательно, всего графов размера $N,$ содержащих $n−$ клику:

n ≤ CnN ⋅2N(N2−1)− n(n−2-1)< N-⋅2N(N2−1)− n(n−21) n!

Последнее выражение меньше, чем $2N(N2−1), 2$ если $N <(n!)1n ⋅2 n−21− 1n.$ Легко доказать (по индукции например), что $n!> 2n∕2+1$ при $n ≥3.$ Поэтому можно взять $N = [2n∕2]$ так, как

1 n−1− 1 n∕2+11∕n n−1− 1 n∕2 (n!)n ⋅2 2 n > (2 ) ⋅2 2 n = 2 ≥N

А значит и $R (n,n)> 2n∕2,$ что и требовалось.

Следующая подтема