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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На доске написано несколько натуральных чисел. Сумма любых двух из них — натуральная степень двойки. Какое наибольшее число различных может быть среди чисел на доске?

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

Подсказка 1

Сначала придумаем какой-нибудь пример для двух чисел. Самый простой - это 1 и 3. Можно ли сделать больше? Предположим, что у нас есть три числа. Как можно связать суммы этих чисел с учетом, что они являются степенями двойки?

Подсказка 2

Для того, чтобы ответить на вопрос из предыдущей подсказки, заметим, что любые две степени двойки отличаются хотя бы в 2 раза. Тогда если m и n - степени двойки и m < n, то 2m <= n. Какое неравенство тогда можно записать для наших чисел?

Подсказка 3

Пусть a, b, c - некоторые три имеющихся числа. Если b < c, то выйдет, что a + b < a + c, причем эти суммы - степени двойки. Таким образом, получаем 2(a+b) <= a + c. В этом неравенстве мы никак не использовали a. Можно ли наложить какое-нибудь условие на a так, чтобы получить противоречие?

Подсказка 4

Положим, что a - наибольшее число. Верно ли неравенство?

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

Предположим, что среди написанных чисел есть хотя бы 3 различных. Рассмотрим наибольшее из них (обозначим его через $a$ ), а также два других различных числа $b> c$ . По условию $a+ b$ и $a+ c$ различные степени двойки. Но тогда $2(a+c)≤ a+ b$ , что очевидно неверно — противоречие. Поэтому различных чисел не больше 2. Ровно два различных числа могут быть (например, 1 и 3).

Ответ: 2

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

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

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

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

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

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

Условие выполняется для произвольных девяти чисел, и нам ничего не мешает считать их упорядоченными по возрастанию: $a1 ≤ a2 ≤ ...≤ a9$ . Тогда нам достаточно доказать положительность $a1$ . Применим условие для тех четырёх чисел, для которых оно “наименее вероятно”, то есть для самых больших четырёх чисел — условие-то всё равно будет выполняться, но мы получим из этого самую классную информацию!

a6+a7+ a8+ a9 ≤a1+ a2+ a3+a4+ a5.

При этом $a6 ≥ a2$ , $a7 ≥a3$ , $a8 ≥ a4$ , $a9 ≥a5$ . Тогда при $a1 < 0$ мы ещё уменьшим правую часть, и она будет меньше левой — противоречие. Значит, всё-таки $a ≥ 0 1$ .

Ответ:

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

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

В 10 коробках лежат карандаши (пустых коробок нет). Известно, что в разных коробках разное число карандашей, причем в каждой коробке все карандаши разных цветов. Докажите, что из каждой коробки можно выбрать по карандашу так, что все они будут разных цветов.

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

Упорядочим коробки по количеству карандашей $b < b <⋅⋅⋅<b 1 2 10$ . Хочется начинать с коробки, где карандашей меньше всего. Почему? Если мы начнем с коробки, где карандашей много, то можем случайно взять тот цвет, который лежит в коробке, где карандашей мало. В коробке $b1$ есть хотя бы один карандаш, берем любой. В коробке $b2$ карандашей хотя бы два и все разного цвета, поэтому найдется карандаш, отличный от того, который мы взяли. Те же самые рассуждения работают и дальше: на $k$ -ом шаге в коробке $bk$ хотя бы $k$ карандашей разного цвета, мы взяли только $k− 1$ карандаш из предыдущих коробок, поэтому можем взять карандаш из коробки $bk$ , отличный по цвету от ранее взятых. Значит, из каждой коробки можно выбрать по карандашу так, что все они будут разных цветов.

Комментарий Старайтесь, когда пишите решение, избегать слов «и так далее», формализируйте свои рассуждения.

Ответ:

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

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

Есть $20$ различных натуральных чисел, не превосходящих $100.$ Докажите, что среди их попарных разностей есть три одинаковые.

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

Упорядочим числа по возрастанию. Рассмотрим все $19$ разностей соседних чисел (из большего вычитаем меньшее). Предположим, что среди них нет двух одинаковых. Заметим, что разность самого большого числа и самого маленького не превосходит $100− 1= 99,$ но она равна сумме наших $19$ разностей. При этом по нашему предположению у нас не более $2$ разностей равны $1,$ не более двух разностей равны $2,$ и так далее. Тогда сумма наших $19$ разностей не меньше, чем

9⋅10 2(1+ 2+...+9)+ 10= 2⋅-2--+ 10 =100> 99

откуда получаем противоречие.

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

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

(a) Числа от $1$ до $100$ выписаны по одному разу в клетки таблицы $10× 10.$ В каждой строке отмечено второе по величине число. Докажите, что сумма отмеченных чисел не меньше суммы в одной из строк.

(b) Числа от $1$ до $100$ выписаны по одному разу в клетки таблицы $10× 10.$ В каждой строке отмечено третье по величине число. Докажите, что сумма отмеченных чисел не меньше суммы в одной из строк.

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

Пункт а), подсказка 1

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

Пункт а), подсказка 2

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

Пункт а), подсказка 3

Получается, оно не меньше 9 чисел в своей строке, а ещё и не меньше 9 чисел в каждой из других строк, тогда это число ≥90! Давайте обозначим его за а₁₀. Остальные отмеченные можно не оценивать, а попробовать найти строку, где сумма чисел будет поменьше. Если наши отмеченные - вторые по величине в своих строках, то в строке с каким из отмеченных числа в среднем будут меньше?

Пункт а), подсказка 4

Конечно, это строка с наименьшим из отмеченных! Какая максимальная сумма чисел может быть в этой строке? Выразите её через а₁ - наименьшее отмеченное! Будет ли сумма отмеченных больше неё?

Пункт а), подсказка 5

Конечно будет, достаточно лишь вспомнить, что а₁₀ ≥ 90, а все остальные отмеченные ≥ a₁ и вы сразу увидите справедливость неравенства.

Пункт б), подсказка 1

Помните решение пункта а? Там мы возились с наибольшим и наименьшим из отмеченных чисел, здесь будем делать что-то похожее, но надо будет покруче оценивать суммы. Раз уж все числа различные, давайте отмеченные сразу упорядочим: а₁ < a₂ < … < a₁₀. И так же оценим наибольшие из отмеченных и сумму чисел в строке.

Пункт б), подсказка 2

а₁₀ и а₉ оцениваем просто из того, скольких чисел они точно больше. И строку берём такую же, как в пункте а)

Пункт б), подсказка 3

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

Пункт б), подсказка 4

То есть а₂ > a₁ ⇒ a₂ ≥ a₁ + 1; a₃ ≥ a₂ + 1 ≥ a₁ + 2 и т.д. Теперь всё должно получиться!

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

(a) Упорядочим отмеченные числа по возрастанию и обозначим их через $a1,a2,...,a10$ (в порядке возрастания). Заметим, что $a10$ не меньше как минимум $9$ чисел в каждой строке (поскольку $a10$ не меньше любого другого отмеченного числа, которое является вторым по величине в своей строке). Поэтому $a10 ≥90.$ Рассмотрим строку, в которой стоит $a1.$ Сумма чисел в этой строке не превосходит

8⋅9 a1 − 8+ a1− 7+...a1 − 1+ a1+ 100= 9a1+ 100−-2 =9a1+ 66

поскольку первое по величине число в этой строке не больше $100,$ остальные строго меньше $a1$ и все различны. С другой стороны, сумма отмеченных чисел больше, чем

9a1+a10 ≥ 9a1 +90> 9a1+66

поскольку $a2 >a1,...,a9 > a1,a10 ≥90.$ То есть мы получили, что сумма отмеченных чисел не меньше суммы чисел в строке, в которой стоит $a1.$

(b) Упорядочим отмеченные числа по возрастанию и обозначим их через $a1,a2,...,a10$ (в порядке возрастания). Заметим, что $a10$ не меньше как минимум $8$ чисел в каждой строке (поскольку $a10$ не меньше любого другого отмеченного числа, которое является третьим по величине в своей строке). Поэтому $a10 ≥ 80.$ Аналогично, $a9$ не меньше как минимум $8$ чисел в каждой строке, кроме строки с $a10.$ Тогда $a9 ≥ 72.$

Рассмотрим строку, в которой стоит $a1.$ Сумма чисел в этой строке не превосходит

a1− 7+ a1− 6 +...a1− 1+ a1+99+ 100= 8a1+ 199− 7⋅8= 8a1 +171 2

поскольку первое по величине число в этой строке не больше $100,$ второе не больше $99,$ остальные строго меньше $a1$ и все различны. С другой стороны, сумма отмеченных чисел равна

a1+a2 +...+ a8+ a9 +a10 ≥ a1+(a1+ 1)+ (a2 +1)...(a1+7)+ 72+80= 8a1+ 180 >8a1+ 171

поскольку $a1 <a2 <...<a8,a9 ≥72,a10 ≥80.$ То есть мы получили, что сумма отмеченных чисел не меньше суммы чисел в строке, в которой стоит $a1.$

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

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

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

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

Будем решать задачу от противного. Рассмотрим разложение чисел на простые множители, представив каждое число в виде $pα1pα2...pαk 1 2 k$ . Посмотрим, что происходит при переходе от одного числа к другому. У нас либо добавляется, либо пропадает один простой множитель, либо одна из $α$ изменяется на 1. В любом случае сумма $α1+ α2+ ...+ αk$ изменяется на 1, то есть меняет чётность. Значит, чётность этой суммы должна чередоваться — но это невозможно, если чисел всего 2021, то есть нечётное количество.

Ответ: Нет, нельзя

Курсы

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

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

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

У Ани есть шестерка и 7 девяток. Раз в минуту она может перевернуть какие-нибудь две цифры. Может ли у нее оказаться поровну шестерок и девяток? В ответ укажите “да” или “нет”.

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

Подсказка 1

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

Подсказка 2

Какие здесь вообще есть параметры? Сумма? Может быть. Произведение? Точно не не подходит. Сумма кол - ва 6
и 9? Ну оно всегда постоянно и ничего мы из этого не выведем. А вот разность между кол - вом 6 и 9, это интересно. Ведь, либо она меняется в какую - то из сторон на 4(либо +, либо - 4), либо не меняется вообще. Значит остаток при делении на какое число надо рассмотреть у разности кол-ва 6 и 9?

Подсказка 3

Верно, на число 4, так как если мы увеличиваем или уменьшаем на 4, то остаток не меняется, ровно как и если мы прибавляем 0. Тогда, выходит, что разность кол - ва 6 и 9 имеет константный остаток при делении на 4. Осталось посмотреть на остаток начального набора и того, который просят получить в задаче!

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

Посмотрим на разность между количеством шестёрок и девяток. После любой из операций она может либо измениться на $4$ в любую сторону, либо же не измениться совсем. Но это означает, что она не меняет свой остаток от деления на $4$ . Изначально он был равен $(7− 1) ≡2 (mod 4)$ , а должен стать равным $0$ — противоречие.

Ответ: нет

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

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

Есть три кучки камней: в первой $51$ камень во второй — $49$ , а в третьей — $5$ . Разрешается объединять любые кучки в одну, а также разделять кучку, состоящую из чётного числа камней, на две равные. Можно ли получить $105$ кучек по одному камню в каждой?

В ответ внесите “да” или “нет”.

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

Подсказка 1

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

Подсказка 2

Верно, это значит, что если у нас были кучки по одному камню, то до этого была кучка из двух. Аналогично до этого из четырёх. То есть в итоге получается у нас в какой-то момент не должно быть нечётных делителей. Но возможно ли такое?

Подсказка 3

Ага, такого не может быть. Если у нас кучки в какой-то момент делились на одно нечётное число, то после действий в условии они всё ещё делятся на него. А что можно сказать про кучки, которые получатся при первом действии? Посмотрите это и победа!

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

Заметим, что если в некоторый момент количество камней в каждой кучке делится на нечётное число $a$ , то и во всех получаемых разрешёнными действиями кучках количество камней будет делиться на $a$ . После первого хода можно получить три варианта размещения камней: кучки из $100$ камней и $5$ камней (общий делитель $5$ ), из $56$ камней и $49$ камней (общий делитель $7$ ), из $51$ камня и $54$ камней (общий делитель $3$ ). Поэтому не удастся получить ни одной кучки из одного камня.

Ответ: нет

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

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

Саша готовила пиццу с ананасами. Сначала она выложила в ряд несколько кружочков ананаса. После этого она решила, что между ними слишком большие расстояния, поэтому между каждыми двумя положила по одному новому кружочку. Саша сама не заметила, как увлеклась, так что описанная выше процедура повторилась еще дважды. В итоге она насчитала целых $49$ кружочков ананаса в ряду. А сколько кружочков она положила в самый первый раз (сначала)?

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

Если кружочков лежит $k$ , то Саша выкладывает $k − 1$ кружочек, то есть всего кружочков становится $2k− 1$ . То есть, если кружочков $x$ , то в последний раз Саша выкладывала $x−1 2$ кружочков. Тогда в последний раз она выложила $49−1 2 = 24$ кружочка, значит, до этого лежало $49− 24= 25$ кружочков. В предпоследний раз она выложила $25−1- 2 =12$ кружочков, то есть лежало $25− 12= 13$ . Во второй раз Саша выложила $13−1 2 = 6$ кружочков, значит, в самый первый раз (сначала) она выложила $13− 6= 7$ кружочков ананаса.

То есть сначала было 7. Она положила 6, стало 13. Потом ещё дважды повторила выкладывание: положила 12 - стало 25; положила 24 - стало 49.

Ответ: 7

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

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

Можно ли занумеровать рёбра куба натуральными числами от $1$ до $12$ так, чтобы для каждой вершины куба сумма номеров рёбер, которые в ней сходятся, была одинаковой?

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

Подсказка 1

Всего у куба 8 вершин. Значит, общая сумма во всех 8 вершинах должна делиться на 8. Как мы можем посчитать данную сумму, зная, что на ребрах расположены числа от 1 до 12?

Подсказка 2

Сумма чисел от 1 до 12 равна 12 * 13 / 2, но не стоит забывать, что каждое из ребер приходит в две вершины. Значит, сумму чисел от 1 до 12 нужно умножить на 2, тогда мы и получим искомую сумму. Что можно сказать про нее?

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

Предположим, что так занумеровать можно. Обозначим сумму номеров для одной вершины через $s.$ Тогда если рассмотреть сумму номеров соседних рёбер по всем вершинам, то с одной стороны она равна $8s,$ а с другой — $2⋅(1 +2+ ...+ 12)=12⋅13= 156$ (так как каждое ребро входит в сумму ровно $2$ раза). Но $156$ не делится на $8,$ следовательно, так занумеровать рёбра невозможно.

Ответ:

нет

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

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

Будем говорить, что набор чисел $a ,...,a 1 m$ сильнее набора чисел $b,...,b , 1 n$ если среди всех неравенств вида $a > b i j$ количество верных неравенств не менее чем в $2$ раза превосходит количество неверных. Докажите, что не существует трех наборов $A,B,C,$ таких, что $A$ сильнее $B,$ $B$ сильнее $C,$ $C$ сильнее $A.$

Источники: СпбОШ - 2022, задача 11.4(см. www.pdmi.ras.ru)

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

Подсказка 1

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

Подсказка 2

Давайте теперь зафиксируем произвольную тройку (A_i, B_j, C_t) и распишем для неё условие, что A сильнее B, B сильнее C, C сильнее A. А сколько вообще может быть верных неравенств при таком условии? Может попробовать оценить сверху и снизу количество верных неравенств?

Подсказка 3

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

Подсказка 4

Можно посмотреть на наборы A, B и поотвечать на вопросы. А сколько можно записать неравенств вида a_i > b_j? А сколько из них должны быть верными? А мы пользовались какими-либо особенностями множеств A и B или это можно сказать для любой пары множеств?

Подсказка 5

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

Подсказка 6

Верно, количество верных неравенств должно быть ровно в 2 раза больше количества неверных! Так как мы доказываем, что такого не бывает, то в какой-то из пар наборов количество верных больше, чем в 2 раза неверных, а для числа с каким свойством неравенство было бы выполнено для всех остальных чисел?

Подсказка 7

Верно, для наибольшего из всех чисел или для наименьшего, здесь мы пользовались принципом крайнего, который часто может встречаться в задачках, где что-то сравнивается. Вернёмся к условию, что A сильнее B, B сильнее C, C сильнее A, оно ведь тоже участвовало в оценке, тогда что должно быть верно, чтобы она достигалась? Как нам объединить это с прошлым фактом?

Подсказка 8

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

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

Предположим противное. Пусть наборы

A = (a1,...,al),B = (b1,...,bm ),C =(c1,...,cn)

таковы, что $A$ сильнее $B,B$ сильнее $C,C$ сильнее $A.$ Можно считать, что число $a1$ наибольшее среди всех чисел этих трёх наборов. Для каждой тройки индексов $i,j,k(1 ≤i≤ l,1≤ m,1≤ k≤ n)$ посчитаем, сколько верных увтерждений имеется среди неравенств $a > b,b >c ,c >a , i j j k k i$ просуммируем эти числа по всем $i,j,k$ и обозначим полученную сумму через $S.$ Тогда

S ≤ 2lmn, (∗)

поскольку всего имеется $lmn$ троек и в каждой тройке не больше двух верных неравенств. Далее заметим, что каждое неравенство $ai > bj$ присутствует в $n$ таких тройках, поэтому в сумме $S$ оно учтено $n$ раз. По предположению среди неравенств $ai > bj$ не меньше $2lm 3$ верных, поэтому вклад всех неравенств вида $ai >bj$ в сумму $S$ не меньше чем $2lmn. 3$ Аналогично вклад всех неравенств вида $b > c j k$ в сумму $S$ и вклад всех неравенств вида $c > a k i$ в сумму $S$ также не меньше чем $2lmn. 3$ Следовательно, суммарное количество верных неравенств не меньше чем $3⋅ 2lmn ≥S. 3$

Сопоставляя это с неравенством $(∗),$ заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности $2 3mn$ верных неравенств вида $bj > ck,$ а в каждой тройке $ai > bj,bj >ck,ck >ai$ ровно два верных неравенства.

Рассмотрим теперь тройку чисел $a1,bj,ck.$ Среди неравенств $a1 >bj,bj > ck,ck >a1$ должно быть ровно два верных. Поскольку $a1$ — наибольшее число неравенство $ck > a1$ неверно, т.е. выолняется неравенство $bj > ck.$ Значит, все неравенства вида $bj > ck$ верные и всего их $mn$ штук. Но это противоречит тому, что их $2 3mn.$ Стало быть, наше предположение неверно.

Интенсивы

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

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

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

Перестановка чисел $1,2,3,...,n$ в некотором порядке называется забавной, если в ней каждое число, начиная со второго слева, либо больше всех чисел, стоящих левее него, либо меньше всех чисел, стоящих левее него. Например, перестановка $3,2,1,4,5,6$ является забавной, а перестановка $3,1,2,4,5,6$ — нет. Найти количество всех различных забавных перестановок чисел $1,2,3,..,n.$

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

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

Подсказка 1

Если собирать последовательности с первого элемента, то будет трудно...но можно пойти с конца! Сколько есть вариантов для последней позиции?

Подсказка 2

Всего 2!(какие?). Теперь мы можем выбирать предпоследнюю цифру, но ведь она связана с последней? Какие тогда комбинации последних двух цифр могут быть?

Подсказка 3

(n-1, n), (1, n), (2, 1), (n, 1). Интересно, было 2 варианта, стало 4...попробуем обобщить наши рассуждения. Подумаем, как выглядят первые k чисел при любом k от 1 до n.

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

Пойдём с конца. Последнее число $a n$ забавной перестановки либо больше, либо меньше всех чисел множества $1,2,3,..,n,$ следовательно, оно равно 1 или $n.$ Предпоследнее число $an−1$ забавной перестановки либо больше, либо меньше всех чисел множества $1,2,3,...,n,$ кроме $an,$ то есть это наименьший или наибольший элемент во множестве $1,2,3,...,n− 1$ или во множестве $2,3,...,n.$ В каждом из случаев есть ровно две возможности выбора, варианты для двух последних чисел перестановки выглядят так $(n − 1,n),(1,n),(2,1),(n,1).$ Несложно убедиться, что при любом $k =n,n− 1,...,2,1$ первые $k$ чисел $a1,a2,...,ak$ перестановки образуют интервал из $k$ подряд идущих чисел из множества $1,2,3,...,n,$ а число $ak$ является в этом интервале минимальным или максимальным — всего две возможности, кроме самого первого числа $a1,$ для которого остаётся единственная возможность. Всего получаем ровно $n−1 2$ возможностей выбора.

Ответ:

$2n−1$

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

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

В школьном спортзале один стол для армрестлинга. Учитель физкультуры организовал школьный турнир. Он вызывает на схватку любых двух участников турнира, еще не встречавшихся друг с другом. Ничьих не бывает. Если участник схватки терпит второе поражение, то он выбывает из турнира. После того, как было проведено $29$ схваток, из турнира выбыли все участники, кроме двух. Сколько школьников участвовало в турнире?

Источники: Муницип - 2022, Московская область, 7.2

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

Подсказка 1

Подумаем, а сколько проигрышей было всего? А сколько проигрышей было среди тех, кто выбыл?

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

Каждый участник выбывает, потерпев ровно два поражения. В ситуации, когда остались двое “финалистов”, общее количество поражений равно $29$ .

Если из турнира выбыло $n$ человек, то они суммарно потерпели $2n$ поражений, а на счету “финалистов” поражений могло быть $0$ (у обоих “финалистов” не было поражений), $1$ (у одно из “финалистов” было поражение) или $2$ (у обоих “финалистов” было по одному поражению).

Учитывая, что $2n$ и $2n+ 2$ — чётные числа, уравнения $2n= 29$ и $2n+ 2= 29$ не имеют решений.

Приходим к уравнению $2n +1 =29$ , откуда $n= 14$ , а общее количество участников равно $16.$

Ответ: 16

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

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

На межпланетный фестиваль “Радуга” прибыли $107$ зелёных и фиолетовых человечков. Зелёные человечки правильно воспринимают цвета, а фиолетовым, к сожалению, зелёный кажется фиолетовым, и наоборот. Посмотрев вокруг, каждый участник фестиваля подошёл к кому-то, сказал “Какой вы фиолетовый!” и подарил кактус. Докажите, что хотя бы один человек на фестивале не получил такого подарка.

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

Подсказка 1

Подумаем со стороны зеленого человечка, а какому он дарил подарок? Точно так же подумаем и про фиолетового.

Подсказка 2

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

Подсказка 3

Обратите внимание на четность общего количество человечков

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

Из условия следует, что зелёные дарили кактусы фиолетовым, а фиолетовые — зелёным. Так как общее количество человечков нечетно, то какого-то вида больше, чем другого. Допустим, что зелёных больше, тогда какому-то зелёному человечку кактуса не досталось.

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

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

Существуют ли целые числа $x,y,z,$ удовлетворяющие равенству:

(x+ y)(y+ z)(z+ x)=2023

Источники: Муницип - 2022, Брянская область, 8.1

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

Подсказка 1

Что можно сказать про число 2023? Четное ли оно?

Подсказка 2

Да, 2023 - нечетное! А что можно сказать про три множителя в левой части уравнения? Какую четность они имеют?

Подсказка 3

Верно, поскольку чисел 3(x, y, z). То среди них будут либо 2 четных, либо 2 нечетных! А что мы знаем про сумму чисел одной четности? Каким по четности будет произведение трёх этих множителей?

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

Если бы такие три числа $x,y и z$ существовали, по крайней мере два из них имели бы одинаковую четность. Предположим, что это пара чисел $x$ и $y$ . Тогда сумма $x+ y$ четная, а значит, четным должно быть и произведение $(x+ y)(y+ z)(z+ x).$ Число же $2023,$ которому это произведение должно равняться, — нечетное. Полученное противоречие показывает, что целых чисел, удовлетворяющих условию, не существует.

Варианты правильных ответов:

нет
Нет

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

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

Датчик случайных чисел за одно действие уменьшает или увеличивает на 1 коэффициент перед $x$ или свободный член в квадратном трёхчлене. После некоторого числа таких операций он преобразовал трёхчлен $2 x − 20x+22$ в трехчлен $2 x − 202x +2$ . Верно ли, что среди полученных в процессе квадратных трёхчленов есть такой, у которого целые корни? Ответ обоснуйте.

Источники: Звезда - 2022 (см. zv.susu.ru)

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

Подсказка 1

Следить сразу за двумя целыми корнями как-то сложновато. Давайте для начала попробуем доказать, что в какой-то момент будет один целый корень. Может возьмем какой-нибудь конкретный?

Подсказка 2

А чего мелочится, давайте посмотрим на 1! Если у нашего трехчлена есть корень 1, то сумма его коэффициентов равна 0. Как меняется сумма наших коэффициентов после одной операции?

Подсказка 3

Верно, она меняется на 1! Изначально сумма была 3, а в конце -199. Значит в какой-то момент она станет равной 0. Итак, в какой-то момент у нашего трехчлена будет корень 1. Докажите, что тогда у него есть второй целый корень (возможно кратный)!

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

Давайте попробуем доказать, что в какой-то момент у квадратного трёхчлена будут целые корни. Для этого угадаем один из них. Если сумма коэффициентов многочлена равна 0, то есть корень $x =1.$ У начального многочлена $2 f1(x)= x − 20x+ 22$ сумма коэффициентов равна 3, а у конечного $2 f2(x)=x − 202x +2$ сумма коэффициентов равна -199, при этом за одно действие ровно один из коэффициентов меняется на 1, значит, сумма коэффициентов меняется на 1. Но если она была положительной, а потом стала отрицательной, то в какой-то момент обязательно была равна 0. То есть в какой-то момент у нас был трёхчлен $2 f(x)= x +bx+ c$ , один из корней которого равен 1! А по теореме Виета второй корень равен $c$ — тоже целому числу $=⇒$ у трёхчлена 2 целых корня!

Ответ: да

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

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

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

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

Двое играют в карточную игру. У каждого есть колода из 30 карт. Каждая карта красная, зелёная или синяя. По правилам красная карта сильнее зелёной, зелёная сильнее синей, а синяя сильнее красной. Карты одного цвета равны. Колода каждого игрока перед началом партии перемешивается и кладётся перед ним рубашкой вверх. После этого оба открывают по верхней карте своей колоды. Если карты разного цвета, то выигрывает тот, чья карта сильнее. Если карты одинаковые, то они уходят в сброс, а игроки открывают ещё по одной карте - и так до тех пор, пока карты не окажутся различными. Если же обе колоды кончились, а победитель не выявлен, объявляется ничья.

Известно, что у первого игрока в колоде по 10 карт каждого цвета. Второй игрок имеет право взять любую колоду из 30 карт. Может ли он подобрать колоду так, чтобы вероятность его выигрыша была больше 1/2?

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

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

Подсказка 1

Разберемся с ответом. Если мы хотим доказывать, что нет, то нам надо доказывать, что для всевозможных колод у второго вероятность будет меньше 1/2. Это вообще непонятно как делать. А вот если же мы хотим доказывать, что ответ - да, то нам надо привести всего одну «хорошую» колоду. Давайте подумаем, если у нас дано количество синих, красных и зеленых карт каждого человека, то как бы для нас удобно было бы выражать вероятность, ведь наши переменные никак друг от друга не зависят(мы хотим выразить в общем случае вероятность и подставить одну и ту же переменную вместо всех для первого игрока в конце).

Подсказка 2

Наверное было бы удобно делать это рекуррентой, поскольку игра идет по шагам. Мы хотим как-то зафиксировать нашу конструкцию. Давайте подумаем как это можно было бы сделать не вводя кучи переменных. Пусть у нас r, g, b — количество соответственно красных, зеленых и синих карт у первого. Тогда, если мы хотим доказать, что при какой-то колоде все хорошо, то либо нам опять рассматривать все колоды и как-то усреднять (что то же самое, что и доказывать, что ответ «нет», в смысле рассмотрения всевозможных колод), либо брать какую-то конкретную колоду, методом крайнего. Какие колоды при этом кажутся интуитивными в таком случае?

Подсказка 3

Во-первых, интуитивной кажется колода копирующая первого игрока, но чисто навскидку, ситуации симметричны и вряд ли там будет строго больше 1/2 вероятность. Давайте также поймем, что скорее всего число 30 здесь просто так, кроме разве что того, что оно кратно 3. А это значит, что по нашему предположению, мы можем масштабировать колоду, при этом не меняя кардинально конструкцию взятия колоды второму, чтобы было выполнено условие. Но тогда это значит, что мы либо берём какую-то фиксированную долю от колоды для каждого цвета, а если так, то нужны еще согласованности с делимостью на эту долю и это как-то все очень шатко, если мы предполагаем, что можно масштабировать. Это наталкивает нас на мысль, что по хорошему бы брать какое то маленькое (чтобы и для маленьких размеров колод, скажем, меньших 30 условие было выполнено) фиксированное число карт одного цвета, тоже самое с другим, и все остальное - третьего цвета.

Подсказка 4

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

Подсказка 5

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

Подсказка 6

Если вероятность победы второго, когда только красные это v(r, g, b), где r, g, b - кол-во красных, зеленых и синих у первого соответственно, то v(r, g, b) = (g * 1 + r * v(r - 1, g, b)) / (r + g + b) - просто перебираем исходы и варианты, когда победим.

Подсказка 7

Напишите такую же рекурренту для u(r, g, b), где это вероятность когда одна синяя и остальные красные(очевидно, она будет выражаться через себя и v(r, g, b)), после чего попробуйте и для v, и для u найти общий вид реккуренты (очевидно, сначала для v, так как она проще и в итоге, искать надо u), перебирая маленькие значения, после чего задача будет решена.

Подсказка 8

Не забудьте доказать эти формулы по индукции, найдя базу и сделав переход (быть может сам переход натолкнет вас на вид, как должны выглядеть v и u).

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

Рассмотрим колоду, в которой одна синяя карта, а все остальные красного цвета. Найдём в этом случае вероятность выигрыша второго игрока. Пусть $u(r,g,b)−$ вероятность выигрыша, когда у первого игрока $r$ красных карт, $g$ зелёных, $b$ синих, а у второго одна синяя и все остальные красные (при условии $r+ g+ b>0$ ). Также пусть $v(r,g,b)$ - вероятность выигрыша, когда у второго игрока все карты красные.

Легко видеть, что

g⋅1+ r⋅v(r− 1,g,b) v(r,g,b)= ----r+-g+-b-----

при $r+ g+b> 0$ (если у первого выпала зелёная, то второй выиграл, если синяя, то проиграл, если красная, то игроки потратили по одной красной карте и продолжили игру). Ясно также, что $v(0,0,0)= 0$ (в этом случае будет ничья). Отсюда по индукции получаем, что $v(r,g,b)= gg+b$ при $g+ b> 0$ и $v(r,0,0)= 0$ .

Аналогично

u(r,g,b)= g(r+g+-b−-1)+r(1+(r+-g+-b− 1)u(r−-1,g,b))+-bv(r,g,b−-1)) (r+ g+ b)2

(Здесь мы рассматриваем всевозможные пары ходов: одна из $r+ g+b$ карт первого и одна из такого же количества карт второго. Если у первого выпала зелёная, то второй выиграет во всех случаях, кроме одного; если красная, то второй либо выкладывает синюю и побеждает, либо выкладывает красную и попадает в аналогичную игру с меньшим числом карт; если у первого синяя, то второй имеет шанс на выигрыш, только если выложит синюю и попадёт в новую игру со всеми красными). Кроме этого, $u(1,0,0)=1,$ $u(0,1,0)= u(0,0,1)= 0$ .

Легко проверить (догадаться сложнее... можно, например, угадать формулу, вручную посчитав вероятности для малых $r,g,b$ ), что эти равенства задают формулу

(r⋅(g+1) g⋅b g⋅(g− 1)) 1 u(r,g,b)= g-+b+-1 +g-+b−-1 +--g+-b- ⋅r+-g+b-

при $g+ b>1$ . Тогда

u(n,n,n)= 1 +----12--- > 1 2 6n(4n − 1) 2

при всех $n > 0$ , в том числе и при $n = 10$ .

Ответ: да

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

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

Клетки кубической таблицы $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

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

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

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

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

Подсказка 1

Попробуем воспроизвести процесс и начать красить. Провели прямую - покрасили 2 зоны. Теперь проведем вторую прямую - что нужно сделать, чтобы условие снова выполнялось?

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

Докажем индукцией по $n$ . База очевидна. Рассмотрим $n+ 1$ прямую и выкинем одну из них. Теперь по предположению все области можно раскрасить в два цвета так, как нам нужно. Вернём выкинутую прямую. Некоторые области она поделила на две. Раскрасим все области по одну сторону от неё в противоположный цвет. Заметим, что по-прежнему условие выполняется, а значит утверждение доказано.

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

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

$2n$ конфет как-то разложены по $n$ коробкам. Девочка и мальчик по очереди берут по конфете: первой выбирает девочка. Докажите индукцией по $n$ , что мальчик может выбирать конфеты так, чтобы две последние конфеты были из одной коробки, как бы ни действовала девочка.

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

Подсказка 1

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

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

База при $n= 1$ очевидна. Переход: понятно, что есть коробка, в которой не более двух конфет.

Если есть коробка без конфет, забудем про неё и после двух первых произвольных ходов применим предположение.

Если её нет, но есть коробка с одной конфетой, то поступим так: если девочка возьмёт конфету из этой коробки, то мальчик сделает произвольный ход и далее можно применить предположение. Если же девочка не возьмёт оттуда конфету, то это сделает вторым ходом мальчик, и тогда снова можно применить предположение.

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

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