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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дано натуральное $n ≥3.$ Найдите количество способов расставить числа $1,2,...,n$ по кругу так, чтобы каждое число являлось делителем суммы двух соседних с ним чисел. Способы, отличающиеся поворотом или отражением, считаются одинаковыми.

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

Будем доказывать индукцией по $n,$ что для чётного $n$ способ единственный (выписать подряд по кругу числа $1,2,...,n),$ а для нечётного $n$ есть два способа: один — выписать подряд по кругу числа $1,2,...,n,$ а другой — в первом способе переставить число $n$ между $n−1 2$ и $n+1 2 .$ Для $n= 3$ способ всё же один, так как предлагаемые способы совпадают.

База для $n= 3$ и $n= 4$ очевидна. Докажем переход от $n− 1$ к $n.$ Рассмотрим число $n.$ Пусть рядом с ним стоят числа $a$ и $b.$ Тогда сумма $a+ b$ делится на $n,$ но меньше $2n,$ так как $a$ и $b$ меньше $n.$ Значит, $a+b =n.$ Выкинув число $n$ из круга, получим расстановку, удовлетворяющую условию (для всех чисел, кроме $a$ и $b$ условия не сломались, а суммы соседних чисел у $a$ и $b$ уменьшились на $a$ и $b$ соответственно, а значит, делимости сохранились).

Если $n$ — нечётное, то после выкидывания числа $n$ по предположению индукции числа должны быть выписаны подряд от 1 до $n − 1,$ но тогда $n$ можно вставить только между двумя числами, дающими в сумме $n,$ то есть между 1 и $n − 1,$ или между $n−1 -2-$ и $n+1 -2-.$ Итого, два способа, переход доказан.

Если же $n$ — чётное, то после выкидывания числа $n$ по предположению индукции числа должны быть или выписаны подряд от 1 до $n − 1,$ тогда $n$ можно вставить только между 1 и $n − 1,$ или выписаны подряд числа от 1 до $n− 2,$ но между $n−22$ и $n2$ стоит число $n − 1.$ Во втором случае число $n$ некуда вставить, так как суммы соседних чисел никак не могут равняться $n$ при $n≥ 4.$ Итого, один способ, переход доказан.

Ответ:

При четных $n$ и $n= 3$ способ единственный; при нечетных $n$ два способа

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

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

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

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

В классе 25 учеников. Учитель хочет запасти $N$ конфет, провести олимпиаду и раздать за успехи в ней $N$ конфет (решившие поровну задач должны получить поровну, решившие меньше — меньше, в том числе, возможно, и ноль конфет). При каком наименьшем $N$ это будет возможно независимо от количества задач на олимпиаде и успехов учеников?

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

Покажем, что меньшего числа конфет может не хватить. На тот случай, если все участники решили поровну задач, число конфет необходимо сделать кратным 25. Пусть $N = 25k.$ Представим себе, что 24 человека решили поровну, а 25-й решил меньше. Если каждому из первых 24 участников дать по $k$ конфет или еще меньше, то останутся лишние конфеты. Значит, каждому из них необходимо дать как минимум по $k+ 1$ конфете, откуда $25k ≥24(k+ 1),$ то есть $k≥ 24$ и $N ≥ 600.$

Теперь докажем по индукции, что можно раздать $m$ участникам $m(m − 1)$ конфет так, чтобы каждый получил меньше $2m$ конфет. База при $m= 1$ очевидна: дадим единственному участнику 0 конфет.

Переход от $m − 1$ к $m.$ Пусть есть $s$ участников с самым большим результатом и, кроме них, еще $t$ участников, $s+t= m.$ Менее успешным участникам по предположению индукции раздадим $t(t− 1)$ конфет (причём всем меньше чем по $2t$ ). После этого останется

(s+ t)(s+t− 1)− t(t− 1)= s(s+ 2t− 1)

конфет, и мы раздадим их поровну «верхним» участникам. Каждый из них получит по $s+ 2t− 1$ конфет. Это число не меньше, чем $2t,$ поэтому больше того, что мы раздали каждому из остальных. Кроме того,

s+ 2t− 1< 2s+ 2t =2m,

что и завершает переход.

Ответ:

600

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

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

У племени семпоальтеков было $24$ слитка золота, $26$ редких жемчужин и $25$ стеклянных бус. У Кортеса они могут обменять слиток золота и жемчужину на одни бусы, у Монтесумы — один слиток и одни бусы на одну жемчужину, а у тотонаков — одну жемчужину и одни бусы на один золотой слиток. После долгих обменов у семпоальтеков осталось только одна вещь. Какая?

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

Пусть у племени было $x$ слитков золота, $y$ жемчужин и $z$ бус. Если семпоальтеки один раз обменяются с Кортесом, у них будет следующая тройка количеств предметов: $x− 1,$ $y − 1,$ $z+ 1.$ Если они обменяются с Монтесумой, будет тройка $x − 1,$ $y+ 1,$ $z− 1.$ Если они обменяются с тотонаками, будет тройка $x+ 1,$ $y− 1,$ $z− 1.$ Заметим, что при каждом обмене у всех количеств предметов меняется четность, а общее количество предметов уменьшается на 1. Всего предметов было $24+ 26+25 =75.$

Обмены производились, пока у племени не осталась последняя вещь. Тогда всего обменов было произведено 74. Следовательно, четность всех количеств предметов осталась исходной. Два вида предметов должны отсутствовать у племени, то есть, их количества равны 0, это будут слитки золота и жемчужины, так как в самом начале их было 24 и 26 соответственно. Получается, что у племени останутся стеклянные бусы.

Ответ:

Стеклянные бусы

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

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

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

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

Подсказка 1:

Попробуйте применить соображения, связанные с чётностью.

Подсказка 2:

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

Подсказка 3:

Как насчет того, чтобы рассмотреть главную диагональ? Ведь на неё влияют только клетки соседних диагоналей.

Подсказка 4:

Тут стоит рассуждать в лоб. Пусть клетки диагонали, примыкающей к главной сверху, были выбраны для хода соотвественно x₁, x₂, ..., x₂₀₂₂ раз. Аналогичные обозначения введём для нижней диагонали, но с переменной y. Посчитайте количество переворотов монеты на каждой клетке главной диагонали и поработайте с их чётностью.

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

Предположим, что так могло произойти. Рассмотрим монеты на главной диагонали. Заметим, что на них могли повлиять только монеты с соседних диагоналей, будем называть их верней и нижней диагоналями. Тогда пусть мы выбирали первую монету на верхней диагонали $x1$ раз, вторую — $x2,$ и так далее до $x2022.$ Аналогично для нижней диагонали введём $y1,...,y2022.$ Все клетки главной диагонали попали под действие ходов нечётное число раз. Тогда для первой клетки получаем $x1+ y1$ нечётно. Для второй клетки $x1+ x2+ y1 +y2$ также нечётно, что означает чётность $x2+ y2.$ Аналогично получаем $x3 +y3$ нечётно, и так далее. Значит, $x2022+ y2022$ чётно, откуда получаем противоречие для последней клетки главной диагонали. Значит, такой последовательности ходов быть не могло.

Ответ:

нет

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

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

На столе лежат несколько яблок, самое большое весит $b$ граммов. Два школьника по очереди съедают по яблоку, пока не съедят всё. Докажите, что при наилучших действиях обоих игроков первый школьник сможет объесть второго, но не более, чем на $b$ граммов.

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

Для решения достаточно привести стратегию за первого, при которой он гарантированно объедает второго, а также стратегию за второго, при которой гарантированно первый если и объедает его, то не более, чем на $b$ граммов.

Начнём со стратегии для первого. Пусть он на каждом шаге берёт самое тяжёлое яблоко. Тогда если на $i−$ м шаге первый взял яблоко с весом $x,$ а второй — c весом $y,$ то $x≥ y$ (на последнем шаге второму может не достаться яблока, если количество яблок нечётное, и в этом случае считаем, что $y = 0).$ Следовательно, первый однозначно объест второго.

Теперь приведём стратегию за второго. Стратегия будет аналогичной, второй на каждом шаге берёт самое тяжелое яблоко из имеющихся. Пусть первый взял на первом шаге яблоко с весом $a.$ Теперь рассмотрим $i−$ й и $(i+ 1)−$ й шаги. Второй на $i−$ м шаге взял яблоко с весом $x,$ а первый на $(i+ 1)−$ м — с весом $y.$ Ясно, что $x≥ y.$ Таким образом, если не учитывать первое яблоко, второй объел первого. А если его учесть, то первый если и смог объесть второго, то не более чем на $b$ граммов, потому что $a ≤b.$

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

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

Есть 99 яблок. Набор из 50 яблок назовём доминирующим, если его вес строго больше половины общего веса яблок. Докажите, что доминирующих наборов не менее $49 2 .$

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

Упорядочим яблоки по весу: $a ≤ 1$ $a ≤ 2$ … $≤ a . 99$ Рассмотрим пары яблок $(a ,a), 1 2$ $(a,a ), 3 4$ …, $(a ,a ). 97 98$ Докажем, что если в набор взять $a99$ и по любому яблоку из каждой пары, он будет доминирующим (всего таких наборов $49 2 ,$ поэтому это решит задачу). Достаточно провести доказательство для набора с наименьшим суммарным весом яблок, то есть набора, в который из каждой пары взято яблоко с нечётным индексом:

a99+a97+ a95+ ...+ a3+ a1 >a98+ a96+ ...+ a2.

Ясно, что

a99 ≥ a98, a97 ≥ a96, ..., a3 ≥ a2.

Также в наборе есть $a1,$ поэтому знак неравенства будет строгим.

Курсы

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

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

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

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

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

Упорядочим коробки по количеству яблок: $a ≤ 1$ $a ≤ 2$ … $≤ a . 100$ Рассмотрим пары коробок $(a,a ), 2 3$ $(a ,a ), 4 5$ …, $(a ,a ). 98 99$ Докажем, что если в набор взять $a1,a100$ и по любой коробке из каждой пары, в нём будет не меньше половины всех яблок. Достаточно доказать его для набора с наименьшим суммарным количеством яблок в ящиках, то есть для набора, в который из каждой пары взята переменная с чётным индексом:

a100+ a98+ a96+...+a2+ a1 > a99+ a97+...+a3.

Ясно, что

a100 ≥ a99, a98 ≥ a97, ..., a4 ≥ a3.

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

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

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

Докажите неравенство для натуральных $n >1 :$

--1- -1-- 1- 13 n +1 + n+2 + ...+ 2n > 24

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

Обозначим

--1- -1-- 1- Sn =n +1 + n+ 2 + ...+ 2n

Будем доказывать по индукции по $n$ неравенство

13 Sn > 24

База. При $n =2 :$

S2 = 1 + 1 = 7-> 13 3 4 12 24

Переход. Пусть верно для $n,$ докажем для $n+ 1.$ Все дроби, кроме $n1+1,21n+1,2(n1+1),$ встречаются и в $Sn,$ и в $Sn+1,$ поэтому посмотрим на их разность:

Sn+1 − Sn =-1---+ --1---− -1--> ---1-- + --1---− -1--= --1- −--1- = 0 2n +1 2(n+ 1) n+ 1 2(n+ 1) 2(n+ 1) n+ 1 n +1 n +1

Получили неравенство $Sn+1 > Sn,$ но по предположению $13 Sn > 24$ , что и доказывает переход, а, значит, доказали и всё неравенство.

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

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

В $n$ -элементном множестве выбрали $k$ трехэлементных подмножеств. Известно, что каждые два элемента входят вместе ровно в одно выбранное подмножество. Докажите, что

n(n− 1)=6k.

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

Подсказка 1:

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

Подсказка 2:

Обратите внимание на то, что каждая пара элементов встречается лишь один раз в каком-либо из подмножеств, а каждое подмножество содержит ровно 3 пары.

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

Каждая пара элементов встречается только в одном из подмножеств. Всего в $n−$ элементном множестве $C2 n$ пар элементов. Каждое трёхэлементное множество содержит $3$ пары элементов. Значит,

C2n n(n− 1) k= -3-= ---6--,

что и требовалось.

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

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

Некая комиссия собиралась $40$ раз. Каждый раз на заседаниях присутствовали по $10$ человек, причем никакие два из членов комиссии не были на заседаниях более одного раза. Докажите, что число членов комиссии больше $60.$

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

Подсказка 1:

Обратите внимание на то, что каждая пара бывала вместе не более чем в одной из комиссий. Сколько пар побывало на всех комиссиях?

Подсказка 2:

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

Подсказка 3:

Значит, общее количество пар n(n – 1) / 2 не меньше, чем суммарное количество пар людей в каждой из 40 комиссий. Теперь можно доказать, что n > 60.

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

Пусть в комиссии $n$ членов. На каждой из комиссии присутствует $C2 10$ пар её членов. Учитывая, что никакие две пары не бывали на комиссии дважды и более, на $40$ комиссиях побывало $2 40⋅C10$ различных пар. Значит,

2 2 C n ≥ 40 ⋅C 10,

или же

n(n − 1)≥ 3600.

Левая часть возрастает на натуральных $n$ и при $n = 60$ неравенство не выполняется. Следовательно, $n> 60.$

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

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

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

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

Подсказка 1:

Назовём галочкой тройку вершин A, B, C, где B — центральная вершина. Если есть ребро AB, но нет ребра BC, назовём такую галочку разноцветной. С помощью этого понятия можно посчитать количество нужных троек.

Подсказка 2:

Сколько разноцветных галочек в неподходящей тройке? А в подходящей?

Подсказка 3:

Каждая вершина соединена с 6 другими вершинами и не соединена с 13. Это позволяет посчитать, в скольких разноцветных галочках вершина является центральной.

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

Рассмотрим граф знакомств в классе. Будем считать разноцветные галочки: для вершины $A$ пары ${B,C}$ такие, что $A$ дружит с $B$ и не дружит с $C.$ Заметим, что в каждой тройке, не подходящей по условию, ровно две разноцветные галочки, а в подходящих — ноль. Каждая вершина является центральной в $6⋅13$ разноцветных галочках. Значит, всего таких галочек

6 ⋅13⋅20= 1560.

Тогда троек, не подходящих по условию, вдвое меньше: 780. А подходящих троек

C3 − 780= 360. 20

Ответ:

360

Интенсивы

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

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

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

В стране $3k+ 1$ город, любые два из которых соединены дорогой. Все дороги делятся на 3 вида, причём из каждого города выходит по $k$ дорог каждого вида. Назовём четвёрку городов хорошей, если в этой четвёрке есть ровно один город, все три дороги из которого в остальные города четвёрки имеют разные типы. Докажите, что количество хороших четвёрок чётно.

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

Подсказка 1:

Назовём разноцветной звёздочкой город и три разноцветные дороги, выходящие из него. Сколько всего таких звёздочек. Какова чётность этого количества?

Подсказка 2:

Их (3k + 1)k³, это чётное число. Попробуйте доказать, что нечётное количество разноцветных звёздочек может быть лишь в хорошей четвёрке. Кажется, это решает задачу.

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

Будем называть разноцветной звёздочкой город и три дороги, выходящие из него, если цвета этих дорог попарно различны. Тогда каждый город даёт $3 k$ разноцветных звёздочек, а всего их $3 (3k+ 1)k ,$ что является чётным числом. Назовём плохой четвёрку, которая не является хорошей. Докажем, что в плохой четвёрке количество разноцветных звёздочек чётно. Единственным плохим случаем может быть три разноцветных звёздочки. Тогда пусть в четвёрке города $A,B,C,D.$ Не теряя общности, будем считать дорогу $AB$ цвета 1, дорогу $AC$ цвета 2, дорогу $AD$ цвета 3. Также будем считать звёздочки вершин $A,B,C$ разноцветными. Тогда дорога $BC$ обязана быть цвета 3, дорога $BD$ — цвета 2, а дорога $CD$ — цвета 1. Но тогда и звёздочка для $D$ будет разноцветной, противоречие. Таким образом, количество разноцветных звёздочек нечётно только в хороших четвёрках. Поскольку общее число разноцветных звёздочек чётно, получаем требуемое.

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

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

Пусть степени вершин графа равны $d, 1$ $d , 2$ …, $d n$ и каждая из них не меньше 4. Докажите, что количество полных пятивершинных подграфов этого графа не превосходит

C4 +...+C4 -d1------dn. 5

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

Будем называть галочкой с центром в $A$ пятёрку вершин ${A,B,C,D,E }$ такую, что рёбра $AB,$ $AC,$ $AD,$ $AE$ проведены. Заметим, что в полном подграфе на 5 вершинах содержится 5 галочек, при этом вершина степени $d$ является центральной для $4 Cd$ вершин. Таким образом, всего галочек в графе

4 4 Cd1 +...+Cdn

а полных подграфов на пяти вершинах не более

C4 +...+C4 -d1--5---dn-

что и требовалось доказать.

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

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

В один прекрасный день $11$ школьников написали тест. Учитель проверил работы и заметил, что для любых двух вопросов теста найдутся хотя бы $6$ школьников, каждый из которых ответил правильно ровно на один из этих двух вопросов. Докажите, что в тесте было не более $12$ вопросов.

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

Рассмотрим двудольный граф, в котором в одной доле будут школьники, а в другой — вопросы. Ребро будем проводить, если школьник ответил на вопрос. Будем называть галочкой с центром в $A$ тройку вершин ${A,B,C}$ такую, что из рёбер $AB$ и $AC$ проведено только одно. Пусть в тесте было $k ≥13$ вопросов. Посчитаем галочки с центром в доле школьников. Если школьник ответил на $x$ вопросов, то он даёт

k2 x(k− x)≤ 4-

галочек. Тогда всего галочек не более $2 11k4 .$ По условию для каждой пары вопросов найдётся не менее шести галочек, которые смотрят на эти два вопроса. То есть галочек должно быть не менее

6C2k =3k(k− 1).

Таким образом, получаем неравенство

k2 11-4 ≥ 3k(k − 1)

Отсюда $11k ≥12(k− 1)$ и $k≤ 12,$ что и требовалось доказать.

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

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

$300$ бюрократов разбиты на $3$ комиссии по $100$ человек. Докажите, что найдутся такие два бюрократа из разных комиссий, что в третьей есть либо $17$ человек, знакомых с обоими, либо $17$ человек, не знакомых с обоими.

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

Для трёх бюрократов $A,B,C$ из разных комиссий будем говорить, что $B$ и $C$ похожи для $A,$ если $A$ либо знаком с обоими бюрократами $B$ и $C,$ либо незнаком с обоими. Для каждой пары бюрократов из разных комиссий найдём количество бюрократов в третьей комиссии, для которых они похожи. Оценим сумму $s$ всех этих $3⋅100⋅100$ чисел. В каждой тройке бюрократов $A,B,C$ из разных комиссий есть либо две пары знакомых, либо две пары незнакомых между собой. Значит, два из них являются похожими для третьего, и вклад каждой тройки в сумму $s$ не менее $1.$ Следовательно, сумма $s$ не меньше, чем число троек бюрократов, то есть:

s≥ 100 ⋅100⋅100= 106

Поэтому одно из слагаемых не меньше $-106-= 100, 3⋅104 3$ то есть не меньше $34.$ Таким образом, какая-то пара бюрократов из разных комиссий является похожей не менее чем для $34$ бюрократов из третьей. Значит, эти два бюрократа либо знакомы хотя бы с $17$ бюрократами из оставшейся комиссии, либо незнакомы хотя бы с $17$ бюрократами из оставшейся комиссии.

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

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

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

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

Подсказка 1:

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

Подсказка 2:

Ясно, что числа будут разбиваться на тройки не хаотично. Скорее всего, стоит попытаться разбить на тройки последовательные числа.

Подсказка 3:

Обратите внимание на чётность чисел. Как она меняется, если идти по кругу?

Подсказка 4:

Наверное, вы заметили, что если подряд идут два чётных числа, то и остальные числа чётные. А как чередуется чётность, если есть хотя бы одно нечётное число? Кстати, если все числа чётные, то можно разделить их на 2.

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

Рассмотрим числа в круге по модулю 2. Предположим, что все числа делятся на 2, тогда можно сократить. Итак, теперь в круге есть хотя бы одно нечётное число. Предположим, что в круге 2 чётных числа стоят подряд. Тогда и все остальные числа также будут чётными, противоречие. Рядом с нечётным числом обязательно стоит одно чётное и одно нечётное. Следовательно, все числа разбиваются на непересекающиеся тройки, в которых четное число стоит между двумя нечетными. Но тогда их количество делится на 3, что и требовалось доказать.

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

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

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

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

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

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

Подсказка 1.

Что часто помогает в задачах с процессом, где требуется доказать, что он конечен?

Подсказка 2.

Верно! Полуинварианты как раз помогают, ведь конкретная величина изменяется только в одну сторону. Что здесь им может быть?

Подсказка 3.

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

Подсказка 4.

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

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

Предположим, что в самой правой коробке никогда не появится шарик. Шариков — $n,$ а используемых коробок $n− 1,$ значит, по принципу Дирихле в какой-то коробке всегда будет хотя бы 2 шарика и операцию можно будет сделать. Дадим $i$ -й коробке вес $i 2$ и пусть в каждый момент времени шарик имеет вес коробки, в которой он лежит. Тогда общий вес шариков после операции увеличивается, причём хотя бы на 1, ведь или вес $k k 2 + 2$ заменяется на $k+1 k−1 2 + 2 ,$ или вес 1 заменяется на 2. Но суммарный вес, с другой стороны, всегда не больше $n−1 n ⋅2 .$ Отсюда получаем противоречие, ведь из рассуждений выше таких увеличений может быть не больше $n−1 n ⋅2 .$

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

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

В некоторых клетках клетчатой полосы $1×n$ стоят фишки. В первой клетке (самой левой) $x 1$ штук, во второй — $x, 2$ …, в $n$ -й клетке — $xn.$ Двое игроков играют в следующую игру: каждым ходом первый игрок выбирает некоторое подмножество фишек, а второй либо передвигает все фишки этого подмножества на 1 клетку влево, а остальные убирает с доски, либо делает то же самое с дополнением выбранного подмножества. Первый хочет, чтобы какая-то фишка оказалась в самой первой клетке, а второй хочет ему помешать. При каких $x1,x2,...,xn$ у первого игрока есть выигрышная стратегия?

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

Подсказка 1

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

Подсказка 2

Пусть вес wₖ = 1/2ᵏ⁻¹. Как изменяется вес фишки при её сдвиге на 1 влево?

Подсказка 3

Вес удваивается (wₖ → 2wₖ). Как реинтерпретировать ход в терминах суммарного веса W?

Подсказка 4

Первый делит все фишки на группы весов Wₐ и Wₛ, Wₐ+Wₛ=W, второй выбирает одну группу, удваивает её вес и убирает другую; новый суммарный вес = 2·min(Wₐ,Wₛ).

Подсказка 5

Вес фишки в первой клетке равен 1. Какой простой критерий гарантирует победу первому игроку?

Подсказка 6

Если начальный суммарный вес W ≥ 1, то первый может выиграть, для этого надо поддерживать инвариант W ≥ 1. Как делить фишки, чтобы сохранить инвариант W ≥ 1?

Подсказка 7

Нужно разбивать текущую массу на две части так, чтобы каждая имела вес ≥ 1/2, после второго хода вес удвоится. А можно ли всегда разделить мультимножество двоичных дробей (1/2,1/4,1/8, ...) с суммой W ≥ 1 на две части с массой ≥ 1/2?

Подсказка 8

Что делать, если W₀ < 1 — есть ли стратегия у второго игрока?

Подсказка 9

Второй игрок всегда выбирает группу меньшей массы; тогда новое W' = 2·min(Wₐ,Wₛ) ≤ W₀ < 1, следовательно, вес остаётся < 1, и победа первого невозможна.

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

Введем весовую функцию для каждой фишки. Фишке, находящейся в клетке с номером $k,$ присвоим вес $w = -1-. k 2k−1$ Суммарный вес всех фишек на полосе в начальный момент времени обозначим как

∑n x W0 = 2kk−1 k=1

Цель первого игрока — добиться появления на доске фишки с весом 1 (т. е. фишки в первой клетке). Когда фишка сдвигается из клетки $k$ в клетку $k − 1,$ ее вес удваивается.

Игра в терминах весов выглядит следующим образом:

1.: Первый игрок разделяет множество всех фишек с общим весом $W$ на два подмножества с весами $WA$ и $WB,$ где $WA + WB = W.$
2.: Второй игрок выбирает одно из подмножеств (например, $A$ ), удваивает его вес и убирает второе. Новый суммарный вес всех фишек на доске становится $2WA.$ Второй игрок стремится минимизировать эту величину.

Докажем критерий выигрыша в обе стороны.

Случай 1: $W0 ≥ 1.$ Докажем, что в этом случае первый игрок выигрывает. Стратегия первого игрока: на каждом ходу поддерживать инвариант — суммарный вес всех фишек на доске $W ≥ 1.$ Для этого на каждом шаге он должен делить текущее множество фишек с общим весом $W ≥1$ на два подмножества, $A$ и $B,$ так, чтобы их веса удовлетворяли условиям

WA ≥ 1∕2 и WB ≥ 1∕2.

______________________________________________________________________________________________________________________________________________________

Лемма. Любое мультимножество фишек с весами из набора

{1∕2,1∕4,1∕8,...}

и суммарным весом $W ≥ 1$ можно разбить на два подмножества, вес каждого из которых не менее $1∕2.$

Доказательство леммы. Будем последовательно заменять в мультимножестве пары одинаковых дробей $1∕2k$ (где $k≥ 2$ ) одной дробью $k− 1 1∕2 .$ Этот процесс не меняет общую сумму и в итоге приведет к мультимножеству, в котором каждая дробь вида $k 1∕2$ (при $k≥ 2$ ) встречается не более одного раза. Если после этого в наборе есть хотя бы две дроби $1∕2,$ то разбиение очевидно. В противном случае (не более одной дроби $1∕2$ ) сумма всех дробей, кроме, возможно, целых, строго меньше

∑∞ 21k =1. k=1

Это противоречит условию, что исходная сумма $W ≥ 1.$ Значит, после упрощения мы получим либо целую часть, либо достаточное количество дробей $1∕2$ для разбиения.

_________________________________________________________________________________________________________________________________________________________________________________

Следуя этой лемме, первый игрок делит фишки на две группы с весами $WA ≥1∕2$ и $WB ≥1∕2.$ Второй игрок вынужден выбрать одну из них, и новый суммарный вес станет

′ W =min(2WA, 2WB)≥ 2⋅(1∕2)= 1.

Таким образом, суммарный вес фишек никогда не опускается ниже 1. Поскольку на каждом ходу хотя бы одна фишка сдвигается влево, игра конечна. Она не может закончиться исчезновением всех фишек (так как это состояние с весом 0). Следовательно, игра должна закончиться появлением фишки в первой клетке (весом 1).

Случай 2: $W < 1. 0$ Докажем, что в этом случае выигрывает второй игрок.

Стратегия второго игрока: после того как первый разделит фишки на группы $A$ и $B,$ выбирать ту, у которой вес меньше. Пусть $WA ≤ WB.$ Тогда $WA < 1∕2,$ так как $WA + WB < 1.$

Второй игрок оставляет группу $A,$ и новый вес становится

′ W =2WA ≤ WA +WB =W0 < 1.

Так как суммарный вес всегда остается меньше 1, состояние победы для первого игрока (фишка с весом 1) недостижимо.

Ответ:

У первого игрока есть выигрышная стратегия при $∑n -xk-≥ 1 k=12k−1$

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

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

В квадрат $10× 10$ по порядку расставлены числа от $1$ до $100.$ За ход можно выбрать число, и прибавить к нему $2,$ а из двух соседей, лежащих с ним на одной прямой, вычесть по $1.$ Или, наоборот: отнять $2$ и прибавить к двум соседям по $1.$ В конце снова получилась расстановка чисел от $1$ до $100.$ Докажите, что она совпала с исходной.

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

Подсказка 1

Какие инварианты сохраняются при разрешённых операциях?

Подсказка 2

Рассмотрим S — сумму квадратов по всем клеткам.

Подсказка 3

Что происходит с S при горизонтальном ходе (центральная клетка +2, соседи по горизонтали −1)?

Подсказка 4

Что даёт равенство инварианта в начале и в конце?

Подсказка 5

Σ aᵢⱼ² = Σ aᵢⱼ bᵢⱼ (где aᵢⱼ, bᵢⱼ — числа в клетке (i, j) в начальной и конечной расстановке соотвественно), а так как bᵢⱼ — та же перестановка 1 ... 100, то Σ bᵢⱼ² = Σ aᵢⱼ².

Подсказка 6

Рассмотрите Σ (aᵢⱼ − bᵢⱼ)². Что вы получите?

Подсказка 7

Эта сумма равна нулю, откуда следует aᵢⱼ = bᵢⱼ для всех i,j — то есть финальная расстановка совпадает с начальной.

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

Пусть $a ij$ — число в клетке $(i,j)$ в начальный момент времени, где

aij = 10(i− 1)+j, i,j ∈{1,...,10}.

Пусть $b ij$ — число в клетке $(i,j)$ в конечный момент времени.

Рассмотрим в качестве инварианта взвешенную сумму всех чисел на доске

∑10 S = aijxij, i,j=1

где $x ij$ — текущее число в клетке.

Проверим, что при таком выборе весов сумма $S$ не меняется. Пусть мы совершаем ход в клетке $(i,j):$ число $x ij$ изменяется на $+2,$ а его соседи (например, по горизонтали) $x i,j−1$ и $x i,j+1$ изменяются на $− 1.$ Изменение суммы $S$ составит:

$pict$

Если ход совершается с вертикальными соседями $xi−1,j$ и $xi+1,j,$ изменение суммы будет:

$pict$

Аналогично, если от числа $xij$ отнимается 2, а к соседям прибавляется по 1, изменение суммы также будет равно нулю. Таким образом, величина $S = ∑i,jaijxij$ является инвариантом.

Теперь сравним значения инварианта в начале и в конце. В начальный момент времени $xij =aij,$ поэтому:

∑ ∑ 2 Sнач = i,j aijaij = i,j aij

В конечный момент времени $xij = bij,$ поэтому:

Sкон = ∑ aijbij i,j

Поскольку $S$ — инвариант, $Sнач = Sкон,$ откуда следует ключевое равенство:

∑ ∑ a2ij = aijbij (∗) i,j i,j

По условию задачи, конечная расстановка $b ij$ также является перестановкой чисел от 1 до 100. Это означает, что набор чисел ${b } ij$ совпадает с набором чисел ${a }. ij$ Следовательно, сумма квадратов чисел в этих наборах должна быть одинаковой:

∑ 2 ∑ 2 aij = bij (∗∗) i,j i,j

Теперь рассмотрим сумму квадратов разностей между начальной и конечной конфигурациями:

∑ 2 ∑ 2 2 ∑ 2 ∑ ∑ 2 i,j(aij − bij) = i,j(aij − 2aijbij + bij)= i,j aij − 2 i,j aijbij + i,j bij

Используя равенства $(∗)$ и $(∗∗),$ получаем:

( ) ( ) ( ) ∑ 2 ∑ 2 ∑ 2 ∑ 2 ∑ 2 ∑ 2 ∑ 2 i,j(aij − bij)= ( i,j bij) − 2(i,j aij) +( i,j bij) = i,j bij − 2 i,j bij + i,j bij = 0

Сумма квадратов действительных чисел равна нулю тогда и только тогда, когда каждый из членов суммы равен нулю. Следовательно, для всех $i,j:$

(a − b )2 = 0 =⇒ a = b . ij ij ij ij

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

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

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

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

Рассмотрим произвольные три подряд идущие комнаты (с номерами $k,$ $k+ 1,$ $k+ 2$ ). Если в одной из них когда-нибудь окажется пианист, то эта тройка комнат уже никогда не опустеет: чтобы покинуть эту тройку, пианист должен переселиться из $k$ -й комнаты в $(k− 1)$ -ю (или из $(k+ 2)$ -й в $(k +3)$ -ю, что рассматривается аналогично), но тогда кто-то переселяется из $(k +1)$ -й в $(k+ 2)$ -ю, и на этом шаге рассматриваемая тройка комнат непуста. Разобьём весь коридор на тройки (например, тройки вида ( $3m,$ $3m +1,$ $3m + 2$ ) для целых $m$ ). Количество «занятых» троек не превосходит количества пианистов, и «занятые» тройки не освобождаются, следовательно, пианисты никогда не покидают некоторую ограниченную часть коридора. С другой стороны, сумма квадратов номеров комнат, в которых живут пианисты (с учетом кратности) при каждом переселении возрастает, поскольку

k2+(k+ 1)2 <(k− 1)2+ (k+ 2)2.

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

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