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

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

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

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

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

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

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

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

Взвешивания и количество информации

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

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

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

Двум мудрецам сообщили по натуральному числу и сказали, что эти числа отличаются на $1.$ После этого они по очереди задают друг другу один и тот же вопрос: “Знаешь ли ты мое число?”. Отвечают мудрецы честно. Докажите, что рано или поздно один из них ответит “Да”.

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

Если число одного из мудрецов равно $m,$ то он знает, что число другого мудреца равно либо $m +1,$ либо $m − 1;$ ему остаётся определить только то, какая из этих двух возможностей имеет место. Когда мудрец $A$ отвечает на вопрос "Знаешь ли ты моё число?"в первый раз, он может ответить положительно только если его число равно $1$ (в этом случае число второго однозначно равно $2$ ). Если ответ был отрицательный, то второй мудрец $B$ узнает, что число $A$ не равно $1$ (хотя он это и так знает, если его число больше $2$ ). Далее, если при втором задании вопроса $B$ отвечает отрицательно, то $A$ узнает, что число $B$ не равно $1$ и $2$ (если число $B$ равно $2,$ он наверняка знал бы, что число $A$ равно $3,$ поскольку после первого вопроса он знает, что оно не равно $1$ ).

Пусть перед очередным вопросом одного из мудрецов (для определенности, $A$ ) обоим мудрецам известно, что число $A$ не равно $1,2,...,k,$ а число $B$ не равно $1,2,...,k− 1.$ Если $B$ ответил отрицательно, то его число не равно $k$ (иначе он бы знал, что число $A$ равно $k+ 1,$ также его число не равно $k +1$ (иначе он бы знал, что число $A$ равно $k+ 2,$ поскольку оно не может быть равно $k$ ). Итак, в случае отрицательного ответа $B$ мы приходим к ситуации, аналогичной только что рассмотренной: перед вопросом B обоим мудрецам известно, что число $B$ не равно $1,2,...,k+ 1,$ а число $A$ не равно $1,2,...,k.$

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

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

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

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

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

На доске написаны $100$ чисел из интервала $(0,1).$ Разрешается выбрать два числа $a$ и $b$ и заменить их на два различных корня квадратного трехчлена $2 x − ax+b$ (если этот трехчлен имеет два различных корня). Докажите, что этот процесс не может продолжаться бесконечно долго.

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

Решение 1. Сначала докажем, что все числа на доске всегда будут принадлежать интервалу $(0,1).$ Для этого достаточно проверить, что корни трехчлена вида $2 x − ax+ b,$ где $a,b∈ (0,1),$ тоже принадлежат интервалу $(0,1).$ Пусть $x1$ и $x2$ — эти корни, тогда $x1x2 =b >0,$ поэтому $x1$ и $x2$ числа одного знака. При этом $x1+ x2 =a >0,$ поэтому $x1$ и $x2$ положительны. Кроме того, $x1+x2 =a <1,$ поэтому $x1$ и $x2$ меньше $1.$ Таким образом, $x1$ и $x2$ тоже принадлежат интервалу $(0,1).$

Рассмотрим сумму обратных величин к числам на доске и исследуем, как она изменяется при указанных операциях. Заменяя пару чисел $a$ и $b$ на корни $x1$ и $x2$ трехчлена $2 x − ax+ b,$ мы заменяем в этой сумме слагаемое $1 1 S = a + b$ на

1 1 x + x a S′ = x1 + x2 =-1x1x22= b

Так как $a$ и $b$ —- числа из интервала $(0,1),$ имеем $1b > ab$ и $1a > 1,$ откуда

S− S′ = 1+ 1 − a > 1 >1 a b b a

Таким образом, рассматриваемая сумма обратных величин на каждом шагу уменьшается более чем на $1.$ Поскольку она останется положительной, такое уменьшение не может происходить бесконечно много раз. Точнее, количество действий не может быть больше, чем $[S0],$ где $S0$ — сумма обратных величин исходных чисел, а квадратные скобки обозначают целую часть числа.

Решение 2. Как и в первом решении, отметим, что все числа на доске всегда принадлежат интервалу $(0,1).$ Кроме того, заметим, что корни трехчлена $x2 − ax+ b,$ где $a,b∈ (0,1).$ лежат между числами $a$ и $b$ на числовой оси. Действительно, из равенства $x1+ x2 = a$ и ранее доказанной положительности корней следует, что $x1 <a$ и $x2 < a.$ А из равенства $x1x2 = b$ и ранее доказанных неравенств $x1 < 1$ и $x2 < 1$ следует, что $b< x1$ и $b <x2$ . Таким образом, если у трехчлена $x2− ax+ b$ есть два корня, то $b <a$ и корни лежат в интервале $(b,a).$ Следовательно, минимум из чисел на доске не уменьшается, значит, все числа будут не меньше некоторого положительного числа $c$ (равного минимуму из исходных чисел).

Теперь исследуем, как изменится сумма всех чисел на доске. При замене чисел $a$ и $b$ на корни трехчлена $2 x − ax+ b$ из этой суммы вычитается $b.$ Действительно, исходные числа вносили в сумму вклад $a+ b,$ а заменившие их корни $x1$ и $x2−$ вклад $x1+x2 =a.$ Таким образом, сумма всех чисел на каждом шаге уменьшается на величину, не меньшую, фиксированного положительного числа $c.$ Поскольку сумма всегда остается положительной и в начале она не превосходит $100,$ таких действий будет не больше, чем $[100∕c],$ где квадратные скобки обозначают целую часть числа.

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

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

Натуральные числа от 1 до 8 расставили по кругу так, что каждое число делится на разность своих соседей. Известно, что числа 2 и 5 стоят рядом. Докажите, что числа 4 и 6 стоят рядом.

Источники: Изумруд-2024, 11 (см. izumrud.urfu.ru)

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

Подсказка 1

Будем отталкиваться от того, что нам уже дано. Какие числа можно поставить рядом с 2? Какие - рядом с 5?

Подсказка 2

Рядом с 2 может стоять одно из чисел 3, 4 ,6, 7. Рядом с пятеркой - 1, 3, 7. Переберем случаи! От какого еще числа удобно отталкиваться?

Подсказка 3

Помним, что соседями единицы могут быть только последовательные числа.

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

Рядом с $2$ может стоять одно из чисел $3,4,6,7$ . Рядом с пятеркой — $1,3,7$ . Заметим также, что соседями единицы могут быть только два последовательных числа. Переберем всевозможные варианты для соседа двойки:

1) Рядом с 2 стоит 3. Тогда рядом с 3 может стоять только 1. Ее сосед — это только 4 и рядом с 4 может встать только 6.

2) Рядом с 2 стоит 4. Тогда рядом с 4 может стоять $1,3$ или $6$ .

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

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

100 человек пришли на представление в шляпах. Фокусник поменял местами их шляпы. После этого каждую минуту каждый человек находил свою шляпу и передавал тому, у кого эта шляпа в данный момент находилась, ту шляпу, которая в этот момент была у него самого. (Если на каком-то шаге у человека $A$ оказывается шляпа, принадлежащая человеку $B$ , а у человека $C$ оказывается шляпа, принадлежащая человеку самому $A$ , то на следующем шаге у $C$ оказывается шляпа, принадлежащая $B$ ).

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

Источники: ИТМО-2024, 11.8 (см. olymp.itmo.ru)

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

Подсказка 1

Условие про то, как передвигаются шляпы достаточно сложное, поэтому, чтобы хорошо его понять, нужно самому подвигать шляпы на каком-то количестве человек. Давайте рассмотрим какого-то человека А₀, так как мы сами вводим обозначения, то давайте изначально его шляпа была у А₁. Тогда человека, держащего шляпу А₁, назовём А₂ и так далее. В какой момент цепочка А₀- А₁-А₂ остановится? Обязательно поймите, почему это точно произойдёт.

Подсказка 2

Цепочка остановится в момент, когда шляпа какого-то Аₙ₋₁ окажется у Aₖ, которого мы уже записывала в нее. Тогда чему может быть равно k?
Только 0, так как для всех людей в цепочке А₀- А₁-А₂-...- Аₙ₋₁ кроме А₀ определена шляпа, которую этот человек держит. Таким образом, мы получили цикл.
Цепочка обязательно замкнётся, просто потому что на представление пришло конечное число человек.
Для удобства будем считать, что Аₙ = А₀, тогда Аₙ₊ₖ = Aₖ.
А теперь попробуйте посмотреть, как перемещаются шляпы через 1 минуту, 2 минуты и так далее. Обратите внимание, как связаны номер человека Aₖ, у которых останавливается шляпа человека Aᵢ, со временем, в которое это произошло. Попробуйте найти инвариант.

Подсказка 3

Через минуту шляпа А₀ окажется у того, кто держал раньше шляпу А₁, то есть у А₂, шляпа А₁ будет у А₃. Тогда можно сделать вывод, что для каждого k шляпа Aₖ через минуту окажется у Aₖ₊₂.
Тогда где будет шляпа А₀ через две минуты? После первой минуты она у А₂, а он на второй минуте передаст её А₂₊₂=А₄, так как именно у А₄ оказалась шляпа А₂ после первой передачи. Тогда можно сделать вывод, что для каждого k шляпа Aₖ через две минуты окажется у Aₖ₊₄.
Значит, рассуждая так дальше, можно определите у кого будет шляпа Aₖ через m минут.

Подсказка 4

Через m минут шляпа Aₖ будет находиться у человека с номером k + 2ᵐ. Тогда при каком количестве человек шляпа сможет вернутся к исходному владельцу? Воспользуйтесь тем, что Aₖ = Аₙ₊ₖ.

Подсказка 5

Шляпа может вернуться к исходном владельцу только в случае, если количество человек в цикле является степенью двойки! По условию фокусник изначально раздал шляпы так, чтобы в итоге они вернулись к своим настоящим хозяевам. Это значит, что все 100 человек разобьются на некоторое количество циклов (цикл из одного человека тоже может быть). Но мы уже получили условие на длины циклов. Тогда какая может быть наибольшая, учитывая ограничение в 100 человек?
Подумайте, почему в циклах меньшей длины шляпы будут у своих владельцев точно не позже, чем тоже самое произойдёт в цикле наибольшей длины. Это Вам и поможет привести пример к полученному ответу.

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

Рассмотрим некоторого человека, назовём его $A 0$ . Пусть его шляпа изначально оказалась у какого-то $A 1$ , шляпа $A 1$ оказалась у $A 2$ , и т.д. Рассмотренный нами процесс нумерации рано или поздно закончится тем, что для какого-то $An−1$ его шляпа окажется у какого-то $Ak$ , который был уже нами пронумерован ранее. При этом это может быть только $A0$ , т.к. про всех остальных мы уже знаем, откуда взялись находящиеся у них шляпы.

Значит, шляпа $An−1$ в начале представления оказалась у $A0$ и мы получили так называемый цикл из $n$ человек. Для удобства будем считать, что $An =A0,An+1 =A1$ и т.д., чтобы иметь возможность говорить, что каждый человек с номером $k$ передал свою шляпу человеку с номером $k+1$ (то есть, мы на самом деле нумеруем людей остатками (классами вычетов) при делении на $n$ ).

После того, как джентльмены передадут свои шляпы, шляпа $A0$ окажется у того, у кого раньше была шляпа $A1$ , то есть у $A2$ , шляпа $A1$ окажется у $A3$ и т.д. Шляпа каждого $Ak$ окажется у $Ak+2$ . После второй передачи шляпа каждого $Ak$ окажется у $Ak+4$ и т.д. Через $m$ минут шляпа $Ak$ окажется у $Ak+2m$ .

Если это тот же человек, что и $Ak$ , разность их номеров, то есть $2m$ , должна делится на $n$ . Значит, шляпа может вернуться к исходном владельцу, только если количество человек в цикле является степенью двойки. При этом фокусник хочет, чтобы был цикл как можно большей длины.

Самая большая степень двойки, не превосходящая 100, это $64= 26$ . Фокусник в начале должен разбить пришедших на представление на циклы, длины одного из которых равна 64, а длины остальных — меньшие степени двойки, не важно какие. Тогда через 6 минут все шляпы окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех сразу).

Ответ: 6

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

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

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

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

Во-первых, специальным образом пронумеруем монеты: присвоим им трехзначные номера $001,010,011,012,112,120,121,122,200,201,202,220.$ Для первого взвешивания положим на одну чашу весов те монеты, у которых старший разряд равен $0$ (то есть $001,010,011,012$ ), а на другую — те монеты, у которых он равен $2(200,201,202,220).$ Если перетянет чашка с $0,$ запишем на бумажке цифру $0.$ Если перетянет $2$ — запишем $2.$ Если чаши весов останутся в равновесии запишем $1.$

Для второго взвешивания на одну чашу выложим монеты $001,200,201,202$ (то есть все те монеты, у которых второй разряд равен $0$ ), а на другую — $120,121,122,220$ (то есть те монеты, у которых средний разряд равен $2$ ). Запишем результат взвешивания таким же образом, что и при первом взвешивании.

Третьим взвешиванием сравниваем $010,020,200,220$ с $012,112,122,202$ (соответственно, нули и двойки в младшем разряде) и записываем третью цифру.

Мы получили три цифры — иначе говоря, трехзначное число. Далее определяем фальшивую монету по следующему рецепту:

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

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

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

Есть $100$ камней, выложенных в порядке возрастания весов. За какое наименьшее число взвешиваний на чашечных весах без гирь можно проверить или опровергнуть утверждение: “Любые пять камней вместе тяжелее любых трех”?

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Предъявим конкретное взвешивание: на первую чашу весов кладём пять самых лёгких гирь, на вторую три самые тяжёлые. Действительно, если утверждение “любые пять камней вместе тяжелее любых трех” верно, то весы очевидно покажут перевес на первой чаше. Если же утверждение неверно, то есть можно выбрать пятёрку камней и тройку камней, что суммарный вес пятёрки не больше веса тройки. А поскольку суммарный вес любых пяти камней как минимум вес пяти самых лёгких, а суммарный вес любых трёх камней не больше веса трёх самых лёгких, весы гарантированно покажут не перевес первой чаши. Соответственно мы различим исходы и сделаем верный вывод.

Ответ:

одно взвешивание

Курсы

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

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

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

Назовём словом любую последовательность букв. Со словами разрешается проделывать следующие операции: 1) удалить первую букву слова; 2) удалить последнюю букву слова; 3) добавить копию слова после него. Например, если исходное слово $ABC$ , применение операций даст $BC,AB$ и $ABCABC$ соответственно. Верно ли, что с помощью таких операций можно в любом слове переставить буквы в любом порядке?

Источники: Турнир Ломоносова - 2024, 11.4 (см. turlom.olimpiada.ru)

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

Подсказка 1

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

Подсказка 2

Как получить циклический сдвиг?

Подсказка 3

Достаточно просто удвоить слово и удалить всё лишнее! Теперь попробуйте перейти от этого к произвольной перестановке.

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

Сначала заметим, что мы можем сделать циклический сдвиг букв в слове. Действительно, пусть у нас есть слово $A A ...A 1 2 n$ . Удвоим его и удалим буквы $A1A2 ...An−1$ слева. Получили слово $AnA1A2...An −1$ .

Теперь приведём алгоритм. Пусть у нас имеется слово $X$ , имеющее вид $A1A2...An$ . Сделаем копию $n$ раз, получим слово $Y$ , состоящее из $n 2$ копий $X$ , идущих подряд. Рассмотрим самое крайнее слово $X$ справа, из него будем делать нужную перестановку. Пусть мы хотим получить некоторую перестановку $B1B2...Bn$ . Пусть $i$ — минимальный индекс такой, что $Ai ⁄=Bi$ . Уберём в самом правом слове $X$ все буквы от $Ai$ до $An$ . Теперь сделаем циклический сдвиг, переместим $Bi$ в конец слова $Y$ . Далее будем следовать аналогичному алгоритму, найдём в слове $Y$ букву $Bi+1$ (она будет среди $n$ первых слева букв), удалим все буквы перед ней и сдвинем её в конец слова $Y$ и так дальше.

Спустя не более $n$ циклических сдвигов $n$ последних букв слова $Y$ будут нужной перестановкой, останется только удалить лишние буквы слева и мы получим требуемое.

Осталось объяснить, почему длины слова $Y$ хватит. На первом шаге мы удаляем не более $n$ букв справа и менее $n$ букв слева, а на остальных шагах — менее $n$ букв слева. Таким образом, всего будет удалено не более $2n +n(n− 1)=n2 +n$ букв. Длина слова $Y$ равна $n ⋅2n$ . Неравенство $n⋅2n ≥ n2+ n$ вытекает из неравенства $2n >n +1$ , которое можно доказать индукцией по $n$ . Таким образом, мы сможем выполнить $n$ циклических сдвигов и при этом точно останутся $n$ букв, составляющих нужную перестановку.

Ответ: да

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

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

В одиннадцатом классе учится $30$ школьников. В их учебный план включены $15$ дисциплин. Для каждой дисциплины можно выбрать $5$ сильнейших школьников — тех, которые наиболее хорошо разбираются в ней. Всегда ли можно рассадить всех школьников по двум аудиториям так, чтобы в каждой аудитории сидел хотя бы один школьник из каждой пятёрки сильнейших?

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Всего 2*2²⁵ способов. Сколько способов рассадить школьников по двум аудиториям так, чтобы существовала дисциплина пятерка сильнейших по одному которому сидела в одной из аудиторий?

Подсказка

Всего 15*2²⁶. Покажите, что это число меньше, чем общее количество способов рассадки школьников по двум аудиториям и завершите доказательство.

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

Всего способов рассадить школьников по двум разным аудиториям $230$ (каждого из $30$ школьников можно посадить в одну из двух аудиторий). Способов рассадить школьников по аудиториям, при которых по конкретному предмету в какой-то из аудиторий нет сильнейших $25 26 2⋅2 = 2 ,$ ведь можно двумя способами выбрать аудиторию, в которой не будет сильнейших по предмету, а остальных в любую из двух. Тогда способов рассадки, при которых в одной из аудиторий нет сильнейших хотя бы по одному из предметов не более $26 15⋅2 .$ Отметим, что $26 26 30 15⋅2 <16⋅2 = 2 ,$ а значит, в каком-то из способов не нашлось аудитории, в которой нет сильнейших ни по одному предмету.

Ответ:

Да, всегда

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

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

Из квадрата $2n× 2n$ вырезали угловую клетку. Докажите, что полученную фигуру можно разрезать на уголки из трёх клеток.

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

База для $n = 1$ : Квадрат $2× 2$ без угловой клетки является уголком из трёх клеток, поэтому база очевидна.

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

Заметим, что $n+1 n n 2 = 2 +2$ , значит, квадрат $n+1 n+1 2 ×2$ состоит из четырёх квадратов $n n 2 ×2$ . По предположению индукции квадрат $n n 2 ×2$ без угловой клетки мы умеем заполнять. Тогда $n+1 n+1 2 × 2$ можно заполнить следующим образом:

$PIC$

Три квадрата $2n× 2n$ заполняем без угловой клетки так, чтобы эти три клетки образовали уголок в центре квадрата со стороной $2n+1$ . Оставшийся квадрат $2n× 2n$ заполняем так, чтобы его незаполненная угловая клетка совпала с незаполненной угловой клеткой большого квадрата. Переход доказан.

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

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

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

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

Подсказка 1

Давайте сначала закинем все бочки в одну кучку. И будем перекидывать по одной бочке в другую кучку. В какой момент лучше остановить этот процесс?

Подсказка 2

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

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

Давайте обозначим веса бочек меда за $a ,a,...,a . 1 2 n$ Давайте все бочки закинем в первую кучку и будем по одной бочке перекладывать во вторую кучку, пока в первой кучке не станет меньше по весу. Пусть в каждый момент веса кучек отличаются больше, чем на $1.$ Тогда посмотрим на момент перед последним шагом процесса. Пусть в этот момент в первой кучке общий вес $X,$ а в второй общий вес $Y.$ Тогда $X > Y +1.$ А в конце нашего процесса верно

Y + ai > X− ai+1 ⇐ ⇒ 2ai > X − Y +1 =⇒ 2ai >2

Последнее неравенство неверно по условию. Противоречие.

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

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

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

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

Подсказка 1

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

Подсказка 2

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

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

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

$PIC$

Интенсивы

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Правильно, если треугольник содержит часть, то он содержит и соседнюю, а если не содержит, то и не содержит соседнюю. А значит, на количество треугольников влияют треугольники со стороной PQ. На сколько меняется количество треугольников содержащих синюю точку?

Подсказка 6

Верно, на модуль разности количества точек с одной стороны и другой стороны относительно прямой PQ. Нам интересна только четность этой разности. Поэтому достаточно узнать четность суммы. А чему же равна сумма?

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

Проведем всевозможные отрезки между красными точками. Они в пересечение образовали несколько частей. Будем называть соседними части, если они имеют общую сторону. Внешнюю часть будем тоже считать частью. Заметим, что если синяя точка лежит в внешней части, то она лежит в четном количестве треугольников, а именно в $0.$ Будем доказывать, что если передвинуть точку в соседнюю часть, то количество треугольников, в которых она содержится, изменится на четное число. Пусть общая сторона соседних частей лежит на отрезке $P Q.$ Тогда если рассмотреть все треугольники, которые не содержат сторону $P Q,$ то они либо содержат обе эти соседние части, либо не содержат. Поэтому нам интересны только треугольники с стороной $P Q.$ При переходе из одной части в другую количество треугольников содержащих точку меняется на $|s1 − s2|,$ где $s1$ количество вершин с одной стороны от $PQ,$ а $s2$ по другую. Учитывая, что $s1+ s2 = 2020$ мы получаем, что $s1− s2$ тоже четное.

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

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

По кругу расставлены $2n$ натуральных чисел, причём соседние отличаются ровно на $1.$ Назовём число, которое больше обоих соседей, горой, а которое меньше — долиной. Докажите, что сумма чисел-гор на $n$ больше суммы чисел-долин.

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

Подсказка 1

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

Подсказка 2

Верно! Попробуем начать уменьшать самые большие числа на 2. Как при этом изменяется разность между горами и долинами?

Подсказка 3

Точно, она не меняется! А какие числа остались в конце и как они располагаются?

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

Запустим процесс, когда мы из одного самого большого числа вычитаем $2.$ Останавливаем процесс, когда все числа становятся равными $0$ и $1.$ Рассмотрим, как при такой замене меняется разница между суммой гор и суммой долин. Пусть мы вычитаем $2$ из наибольшей горы $y.$ Есть три случая: либо два соседа становятся горами, либо только один сосед, либо никто. В первом случае сумма гор увеличилась на $− y+2(y− 1)=y − 2,$ а сумма долин увеличилась на $(y− 2).$ Во втором случае сумма гор уменьшилась на $y− (y − 1)= 1,$ а сумма долин тоже уменьшилась на $(y− 1)− (y− 2)= 1.$ В третьем случае сумма гор уменьшилась на $y,$ а сумма долин тоже уменьшилась на $2(y− 1)− (y− 2)= y.$ То есть при наших действиях требуемая величина не изменяется. Процесс когда-нибудь закончится, так как каждым ходом сумма всех чисел уменьшается, но отрицательных чисел мы не могли получить. Когда все числа либо $0,$ либо $1,$ у нас $n$ гор и $n$ долин с разницей $n.$

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

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

В клубе “Что? Где? Когда?” провели анкетирование, в котором требовалось назвать своего любимого писателя, художника и композитора. Оказалось, что каждый упомянутый хоть раз деятель искусств является любимым для не более чем $k$ человек. Докажите, что всех проанкетированных можно разделить на не более чем $3k− 2$ группы, чтобы в каждой группе любые два человека имели абсолютно разные вкусы.

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

Подсказка 1

Попробуем представить условие в более удобном в виде, то есть в виде графа! Что стоит считать его вершинами и ребрами?

Подсказка 2

Верно! Деятели искусства будут вершинами, а симпатии ребрами. Тогда граф будет двудольным. А что можно сказать о степенях его вершин?

Подсказка 3

Точно! В одной из долей все степени равны 3, а в другой все степени не превосходят k. Попробуем в первой доле, где степени 3, удалить все вершины, а затем возвращать их, параллельно распределяя в группы. Можно ли оценить сверху число соседних вершин к соседям очередной возвращаемой вершины?

Подсказка 4

Верно! Поскольку, включая возвращаемую вершину, у каждого из ее соседей не более k своих соседей, то в графе будет не более 3(k-1) ее соседей. Какой вывод можно сделать?

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

Давайте переформулируем задачу на язык графов. Будем считать людей из клуба вершинами первой доли графа, а деятелей искусства вершинами второй доли. Ребра будут обозначать симпатии. Заметим, что в первой доле у каждой вершины степень ровно $3,$ а во второй доле у каждой вершины степень не более $k.$ Для начала удалим все вершины первой доли и будет добавлять по одной, к тому же крася вершины в $3k− 2$ цвета. Возьмем любую добавленную вершину из первой доли и посмотрим на соседей её соседей. Этих вершин (включая саму вершину) максимум $(3k− 3)+1 =3k− 2,$ а, значит, мы сможем покрасить добавленную в свободный цвет от цвета соседей. По построению вершины одного цвета из первой доли не имеют общих соседей. Теперь вершины одного цвета объединим в группу и получим то, что хотели по условию.

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

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

Дано натуральное число $n< 1022.$ Докажите, что число $n$ может быть представлено в виде произведения десяти натуральных чисел таких, что среди них нет ни одного составного числа, большего $10000.$

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

Подсказка 1

Для начала давайте разложим хоть как-нибудь на 10 множителей. Придумайте какой-нибудь способ разложения.

Подсказка 2

Например такой: 1 * 1 * 1 ... * n. Попробуйте придумать процесс, который будет уменьшать делитель, который больше чем 10⁴, но при этом не будет увеличивать количество делителей больших, чем 10^4.

Подсказка 3

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

Подсказка 4

Процесс такой. Если есть множитель больший 10⁴ и произведение каких-то двух меньше 10⁴, их объединяем, а делитель больший 10⁴ раскладываем на два не единичных множителя так, чтобы один из них был меньше 10⁴ (считаем, что у n нет простого делителя >10⁴). Может ли после окончания нашего процесса остаться делитель, который больше 10⁴?

—

Подсказка 5
Правильно, не может! А что надо сделать, если у n есть простые делители, которые >10⁴?

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

Давайте рассмотрим тривиальное ( $1⋅1...1⋅n$ ) разложение на $10$ множителей. Пусть у $n$ нет простых множителей больших $104.$ И будем делать следующее: если есть множитель больший $4 10$ и произведение каких-нибудь двух множителей $4 ≤ 10,$ то объединяем их в один, а потом раскладываем множитель больший $4 10$ на два не единичных (один из которых меньше $4 10 ).$ Очевидно, что этот алгоритм закончится в силу того, что у $n$ конечное количество множителей. Теперь докажем, что когда алгоритм закончится, у нас все множители меньше $4 10 .$ Пусть не так. Тогда есть множитель больший $4 10$ при этом произведение любых двух больше, чем $4 10,$ следовательно, все произведение хотя бы $4 18 22 10 ⋅10 = 10$ ( $18 10$ берется из того, что у нас есть $9$ множителей, попарные произведения которых больше $4 10,$ а, значит, их произведение хотя бы $9⋅2 18 10 = 10 ).$ Противоречие. Если же число $n$ имеет простой делители, которые хотя бы $4 10 ,$ то поделим на них и будем действовать абсолютно аналогично, но для меньшего количества множителей. Пусть их было $k.$ Тогда финальная оценка превращается в $4 (9−k)⋅2 10 ⋅10 ,$ что легко понять больше, чем $1022−4k.$

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

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

Квартал представляет собой клетчатый квадрат $10× 10.$ В новогоднюю ночь внезапно впервые пошёл снег, и с тех пор каждую ночь на каждую клетку выпадало ровно по 10 см снега; снег падал только по ночам. Каждое утро дворник выбирает один ряд (строку или столбец) и сгребает весь снег оттуда на один из соседних рядов (с каждой клетки — на соседнюю по стороне). Например, он может выбрать седьмой столбец и из каждой его клетки сгрести снег в клетку слева от неё. Сгребать снег за пределы квартала нельзя. Вечером сотого дня года в город приедет инспектор и найдёт клетку, на которой лежит сугроб наибольшей высоты. Цель дворника — добиться, чтобы эта высота была минимальна. Сугроб какой высоты найдёт инспектор?

Источники: ВСОШ, ЗЭ, 2024, 9.5 (см. olympiads.mccme.ru)

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

Подсказка 1.

Хочется верить, что в оптимальном примере во всех непустых ячейках почти поровну снега.

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

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

Докажем, что после сотого утра найдется сугроб высотой не менее $112$ дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгреб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся $90$ клеток, по нашему предположению, не более $111$ $3 дм$ снега, то есть всего снега не больше, чем $9990$ $3 дм .$ Однако за $100$ ночей суммарно выпало $10000$ $3 дм$ снега. Противоречие.

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

Способ 1. Первые $11$ дней дворник сгребает снег из второго столбца в первый, следующие $11$ дней дворник сгребает снег из третьего столбца во второй, затем $11$ дней из четвёртого в третий, и т. д. Через $99$ дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце $i≤ 9$ через $99$ дней. Вечером $11(i− 1)$ -го дня в столбце номер $i$ не было снега, а в столбце $i+ 1$ в каждой клетке было по $11(i− 1)$ $дм3$ снега. На следующий вечер в столбце $i$ станет по $11(i− 1)+ 2$ $дм3$ снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке $i$ -го столбца будет увеличиваться на $2,$ а затем $11(9− i)$ дней — на $1.$ Итого, через $99$ дней в каждой клетке столбца $i$ будет по

11(i− 1)+22+ 11(9− i) =110 дм3 снега.

В сотую ночь выпадет ещё по $1$ $дм3$ в каждую клетку. А сотым утром дворник сгребёт снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более $112$ $дм3$ снега.

_________________________________________________________________________________________________________________________________________________________________________________

Способ 2. Пусть дворник сгребёт снег из $2$ -го столбца в $1$ -ый, из $3$ -го во $2$ -й, …, из $10$ -го в $9$ -ый. Тогда вечером девятого дня в первых девяти столбцах будет по $10$ дм $3$ снега в каждой клетке, а в десятом столбце снега не будем. Затем дворник проделывает аналогичный процесс в обратном порядке: из $9$ -го в $10$ -ый, из $8$ -го в $9$ -ый, …, из $2$ -го в первой. Тогда вечером $18$ -го дня в клетках последних девяти столбцов будет по $20$ $дм3$ снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится $9$ дней) ещё $9$ раз (всего $11$ сдвигов), и через $99$ дней получим в клетках девяти столбцов по $110$ $дм3$ снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более $112$ $дм3$ снега в каждой клетке.

Ответ:

1120 см

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

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

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

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

Даша выложила в ряд $n$ карточек $(5≤ n ≤100),$ на которых по порядку написаны натуральные числа от 1 до $n.$ После этого она перевернула две карточки чистой стороной вверх так, что произведение чисел между ними оказалось равным произведению всех остальных видимых чисел. Какому же числу равно каждое из этих произведений?

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

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

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

Подсказка 1

Подумайте, что будет, если не переворачивать карточку, содержащую достаточно большое простое число.

Подсказка 2

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

Подсказка 3

Нет, не всегда, потому что простых чисел может быть больше двух. Рассмотрите n ≥ 61.

Подсказка 4

А теперь разбивайте карточки на группы и думайте, какие карточки надо перевернуть и подходит ли нам такое n.

Подсказка 5

Для достаточно малых n придется рассматривать их точечно и оценивать состоятельность таких вариантов на основании делимости.

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

Заметим, что если на какой-то карточке встречается простое число $p> n, 2$ то её надо перевернуть, поскольку иначе это число попадёт в одно из произведений, а во втором произведении множителя $p$ не будет. Если таких числа хотя бы три, то придётся перевернуть три карточки, что противоречит условию. Если же их два, то обязательно надо перевернуть именно эти две карточки.

Отбросим некоторые значения $n:$

если $61≤ n≤ 100,$ то надо перевернуть карточки 53, 59, 61;
если $41≤ n≤ 60,$ то надо перевернуть карточки 31, 37, 41;
если $31≤ n≤ 40,$ то надо перевернуть карточки 23, 29, 31;
если $19≤ n≤ 30,$ то надо перевернуть карточки 17 и 19, но между ними лишь число 18, что меньше, чем 16!;
если $13≤ n≤ 18,$ то надо перевернуть карточки 11 и 13, но между ними лишь число 12, что меньше, чем 10!.

Далее, при $n =11$ и $n= 12$ нужно перевернуть карточки 7 и 11. Заметим, что $8⋅9⋅10= 720$ и $6!= 720,$ поэтому при $n= 11$ условие выполняется (произведение равно 720), а при $n= 12$ не выполняется $(6!⋅12⁄=$ $8⋅9⋅10= 720).$

Если $n= 10,$ то одна из перевернутых карточек — 7. Пусть число на второй карточке равно $a.$ Заметим, что если $a =1,$ то каждое из произведений вновь равно 720. Это второй подходящий вариант, но ответ тот же. Если $2≤ a≤ 6,$ то «внутреннее» произведение меньше 720, а «внешнее» не меньше 720. То же верно в случае, когда $a> 7.$

Если $n∈ {7;8;9},$ то надо перевернуть карточки 5 и 7, но между ними число 6, а «внешнее» произведение не меньше 4!.

Если $n= 5,$ то перевернуты карточки 3 и 5, но $4⁄= 1⋅2.$

Если $n= 6,$ то одним из перевёрнутых чисел будет 5. Второе перевёрнутое число может быть только 1 или 2, иначе «внешнее» произведение делится на 3, а «внутреннее» — нет, но $1⋅6< 3⋅4$ и тем более $6 <2 ⋅3 ⋅4.$

Ответ: 720

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

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

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

Источники: СПбОШ - 2024, 10.2 (см. pdmi.ras.ru)

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

Если за $k ≤$ 6 ходов мы сможем определить тип хотя бы $k+ 1$ монет, то можно сравнивать монеты с известными, и за $6$ взвешиваний узнаем тип $7$ монет. Такую ситуацию назовём победой.

Сначала сравним две монеты, если они разные, то мы знаем тип $2$ монет и это победа. Если они одинаковые, сравним эту пару с любой парой оставшихся монет. Если они одинаковые, то мы знаем тип первых двух монет, поменяем пару монет при взвешивании и тогда узнаем, по результату взвешивания мы узнаём тип четырёх монет, это победа. Если весы показали равенство, то мы знаем что у $4$ монет одинаковый тип.

Потом взвесим эту четверку с другой четвёркой, если неравенство, то за три взвешивания опередили тип четырёх монет, это победа. Если равенство, то знаем что у $8$ монет одинаковый тип. Действуя таким образом еще три раза, мы либо победим, либо найдём $64$ одинаковых монет, но это противоречит условию.

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

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

Есть несколько карт. Зритель загадывает одну из них. Фокусник раскладывает все карты на $4$ стопки и узнает у зрителя, в какой стопке оказалась задуманная карта. При каком наибольшем количестве карт можно наверняка определить задуманную карту за $3$ вопроса?

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

Каждый раз нам указывают на одну из четырёх стопок, значит, за три вопроса мы получим максимум $43 =64$ различных последовательностей ответов. Если карт больше $64,$ то не получится однозначного соответствия возможных загаданных карт и последовательностей ответов, значит, гарантированно отгадать задуманную карту не получится.

Приведём также пример, что одну из $64$ карт угадать всегда получится. Разобьем первым действием карты на стопки по $16.$ Нам укажут на одну из этих стопок. $16$ карт выбранной стопки разобьем на стопки по $4,$ остальные — как угодно. Нам снова укажут на одну из стопок, значит, загаданная карта — одна из четырёх. Эти карты снова разбиваем на четыре стопки, теперь по одной, остальные как угодно. Нам укажут на одну из стопок, а значит и на одну из этих четырёх карт, и мы однозначно определим, какая карта загадана.

Ответ:

$43 = 64$ карты

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

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

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

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

Каждый раз дозиметр либо пищит, либо нет, а значит за три проверки мы получим максимум $23 = 8$ различных последовательностей ответов. Возможных вариантов, когда два шара из пяти радиоактивны, — $2 C5 = 10.$ Если мы сделали всего три проверки, то не получится однозначного соответствия возможных исходов и последовательностей ответов, значит, за $3$ проверки гарантированно определить радиоактивные шары не получится.

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

Ответ:

$4$ проверки

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