Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Комбинаторика на МВ (Финашке): графы, турниры, множества, способы

Тема МВ / Финашка (Миссия выполнима. Твоё признание — финансист)

Комбинаторика на МВ (Финашке): графы, турниры, множества, способы

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

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

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

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

Подтемы раздела мв / финашка (миссия выполнима. твоё признание — финансист)

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

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

Задача 1#81381

Про натуральные числа $X,Y$ и $Z$ известно, что они различны и не превосходят 100. Мы можем выписать любую последовательность ${a1,...,a100}$ , содержащую все натуральные числа от 1 до 100. Какое наименьшее число последовательностей нужно выписать, чтобы среди них наверняка имелась такая, в которой два или три подряд идущих члена принадлежат множеству ${X;Y ;Z}?$

Источники: Миссия выполнима - 2024, 11.8 (см. www.fa.ru)

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

Подсказка 1

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

Подсказка 2

Это графы! Пусть у нас есть какое-то количество последовательностей. Вершины графа - это числа от 1 до 100, а рёбра между вершинами x и у проводятся, если в одной из последовательностей числа х и у были подряд идущими членами. Теперь надо понять, при каком наименьшем числе последовательностей обязательно не найдется тройки, внутри которой нет рёбер.

Подсказка 3

Если сложно угадать число, попробуйте рассмотреть ситуацию, когда у нас n последовательностей. Как тогда можно оценить степени вершин?

Подсказка 4

В каждой последовательности число соседствует не более чем с двумя другими числами, то есть степень каждой вершины не превосходит 2n. Подумайте, при каком наименьшем n в любой тройке вершин будет хотя бы одно ребро. Это и будет ответом на задачу. И не забудьте про пример!

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

Сначала покажем, что $24$ последовательностей не хватит.

Построим граф, вершины которого это числа от $1$ до $100$ , а рёбра между вершинами $a$ и $b$ проводятся, если в одной из последовательностей числа $a$ и $b$ были подряд идущими членами.

Так как суммарно во всех $24$ -x последовательностях каждое число будет соседом не более $2 ⋅24 =48$ других чисел, степень каждой вершины в этом графе не превосходит $48$ .

Тогда выберем в графе две несмежные вершины $x,y.$ Так как степень каждой из них не более $48$ , а всего вершин $100$ , то найдется хотя бы $1$ вершина $z$ , которая не соседствует с обеими вершинами $x,y$ . Тогда множество чисел ${x,y,z}$ не будет удовлетворять условию задачи (ни в одна последовательности нет двух или трех подряд идущих членов, которые содержатся в ${x,y,z}$ )

_________________________________________________________________________________________________________________________________________________________________________________

Пример на $25$ последовательностей опишем пример в терминах графа.

Разделим $100$ чисел на две равные группы: например, $1,2,3,...,50$ и $51,52,...,100$ .

Отдельно расставим первые $50$ чисел в $25$ последовательностей длиной $50$ , чтобы любые $2$ числа были соседями в хотя бы одной из $25$ последовательностей. (То есть на языке графов: нужно покрыть $25$ путями полный граф на $50$ вершинах). И аналогично поступим со второй группой $50$ чисел, а потом просто “склеим” последовательности. Например, если первая последовательность в первой группе это $1,2,...,50$ , а первая последовательность во второй - это $51,52,...,100$ , то склеиваем и получаем $1,2,...,50,51,52,...,100$ .

Опишем построение $25$ последовательностей длиной $50$ . Поместим вершины в правильный многоугольник и покроем полный граф на этом подмножестве вершин $25$ последовательностями (то есть путями проходящими по всем вершинам), идущими зигзагом через многоугольник с поворотом каждого пути на кратный $-π-- n− 1$ угол. На картинке пример построения $4$ последовательностей, для $8$ чисел:

$PIC$

Теперь поясним, почему после "склейки"полученные $25$ последовательностей будут удовлетворять условию. Какие бы числа $X,Y,Z$ , мы ни взяли, либо два из них будут среди чисел от $1$ до $50$ , либо среди чисел от $50$ до $100$ . Тогда два числа из одно группы соединены ребром, то есть являются соседями в одной из $25$ последовательностей. Этого мы и добивались.

Ответ: 25

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

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

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

Задача 2#63952

На плоскости отмечено 9 различных точек, среди которых есть красные, синие и зеленые. Точек других цветов нет. Известно, что сумма всех попарных расстояний между красными и синими точками равна 13, между красными и зелеными равна 11, а между синими и зелеными равна 1. Каким может быть количество красных отмеченных точек?

Источники: Миссия выполнима - 2023, 11.8 (см. mission.fa.ru)

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

Подсказка 1

Пупупу…давайте подумаем, а что можно сказать про тройку из трех точек различных цветов?

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Конечно, иными словами: 13r ≤ 11q + p, где r- количество красных точек, q – синих точек, p – зеленых точек! Аналогично можно сказать, что 11q ≤ 13r+p(опять же в силу неравенства треугольника) А также не забываем про условие, что p+q+r=9. Осталось найти возможные значения p, q, r и привести пример, что каждый случай достигается!

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

Пусть отмечены красные точки $A ,...A 1 p$ , синие точки $B ,...B 1 q$ , и зеленые точки $C ,...C 1 r$ .

Поскольку для каждой точки $(AiBjCk)$ выполняется неравенство треугольника $AiBj ≤ AiCk+ BjCk$ , то

∑p q∑ ∑r ∑p q∑ ∑r AiBj ≤ (AiCk +BjCk) i=1j=1k=1 i=1j=1k=1

Откуда $13r≤ 11q+p$ .

Аналогично, просуммировав неравенства $A C ≤ AB +B C i k i j j k$ , получим $11q ≤ 13r +p$ .

Далее перебором можно установить, что найденным соотношениям и равенству $p+q +r= 9$ удовлетворяют ровно две тройки натуральных чисел

p= 5,q = 2,r= 2 и p= 7,q =1,r= 1.

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

Первый вариант: $A = 3-,A = 1,A = 3,A =2,A = 17B = 0,B = 1,C = 1,C = 3 1 16 2 3 2 4 5 16 1 2 8 1 4 2 8$

Второй вариант: $A = 1,A = 1,A = 1,A = 2,A = 5,A = 5,A =7 B = 0,C = 1 1 6 2 3 3 2 4 3 5 6 6 7 1 1$ .

Ответ:

5 или 7

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

Задача 3#73683

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

Источники: Миссия выполнима - 2022, 11.8 (см. mission.fa.ru)

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

Через $|A|,$ где $A$ — произвольный город, обозначим число городов, соединённых беспосадочными авиалиниями с $A.$ Будем рассматривать авиамаршрут, который проходит последовательно через города $A1,A2,...,Am$ и все перелёты на котором централизующие. Ясно, что тогда

1≤ |A1|< |A2|<...<|Am|

Равенство $m= 19$ невозможно, поскольку имело бы своими следствиями взаимоисключающие равенства $|A |= 19 19$ и $|A |= 1, 1$ так как $A 1$ еще соединена с $A . 2$

Допустим, что $m =18$ и $|A18|= 19.$ Тогда $|A1|= 2,|A2|= 3,...,|A17|=18$ то есть город $A17$ соединён либо с $A1,$ либо с $A2.$ Но $A1$ соединён с $A2$ и $A18,$ а $A2$ — с $A1,A3$ и $A18.$

Наконец, предположим, что $m = 18$ и $|A18|= 18$ Тогда $|A1|= 1,A1$ соединён с $A2;|A2|=2,A2$ соединён с $A1$ и $A3.$ Получается, что город $A18$ не соединён ни с $A1,$ ни с $A2,$ а тогда равенство $|A18|= 18$ невозможно. Итак, $m≤ 17.$ Приведём пример системы авиалиний, для которой все перелёты на маршруте, проходящем последовательно через города $A1,A2,...,A17,$ централизующие. Пусть города $Ai$ и $Aj$ ( $1≤ i,j ≤ 20$ ) соединены, если выполнено хотя бы одно из следующих трёх условий:

1)i+ 1= j;2)i+ j ≥ 20,11≤ j ≤ 17;3)j =10,j ∈19,20

Ответ:

$17$

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

Задача 4#67079

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

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

Подсказка 1

Давайте зафиксируем 1 человека на первом месте и посмотрим, как зависит количество способов от посадки 2-го и 3-го людей. Понятно, что если место 1 занято, то людей на местах 2, 3, 17 и 18 уже не выбрать.

Подсказка 2

Да, если 2 человека возьмем с места 4, то, чтобы выбрать 3 человека, есть места с 7 по 16, т.е. 10 способов. Если же 2 человек с места 5, то способов - 9. Продолжая в том же духе, получим, что для сидящего на первом месте человека есть определенное количество способов (которое равно сумме чисел от 1 до 10).

Подсказка 3

Так как мест 18, то и способов выбрать 1 человека тоже 18, значит 55 будем умножать на 18. Остается только заметить, что для первого человека мы посчитали все возможные расположения 2 и 3 людей, значит, нужно взять в 3 раза меньше способов (столько возможностей выбрать первого человека).

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

Первое решение.

Первого человека в тройку возьмём любого из 18. Дальше нужно выбрать второго и третьего. Пусть между первым и вторым при подсчёте по часовой стрелке сидит $x$ человек, между вторым и третьим — $y,$ между третьим и первым — $z.$

По условию должно выполняться $x ≥2,y ≥ 2,z ≥ 2.$ При этом $x +y +z = 15$ (если 3 человека выбрано, то 15 не выбраны). Если уменьшить каждую из переменных на единицу, то получаем уже уравнение в натуральных числах $X + Y +Z = 12.$ По методу шаров и перегородок оно имеет $2 11⋅10- C11 = 2 =55$ решений.

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

55⋅318-= 11⋅53⋅2⋅9= 330

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Пронумеруем места за столом по часовой стрелке от $1$ до $18.$

Посчитаем, сколько троек мы можем создать, если один из людей сидит на первом месте.

В этом случае мы не сможем взять людей, сидящих на $2,3,17$ и $18$ местах. То есть следующего мы сможем выбрать только $13$ способами. Если следующим мы выбираем человека, сидящего на $4$ месте, то следующего можно выбрать с $7$ по $16$ место, то есть $10$ способами; если вторым выбираем человека на $5$ месте, то третьего можно выбрать $9$ способами и т.д.

В итоге, если один из выбранных людей сидит на первом месте, то существует $10+ 9+8 +...+ 2+ 1= 55$ способов подобного выбора.

Общее количество выбора троих людей указанным в условии способом равно:

55⋅18= 330 3

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

Ответ:

$330$

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

Задача 5#70796

В алфавите языка альфов три буквы А, Л и Ф. Все слова этого языка можно построить, применяя последовательно следующие правила к любому слову из этого языка:

(1) поменять порядок букв в слове на противоположный;

(2) заменить две последовательные буквы так: ЛА $→$ ФФ, АФ $→$ ЛЛ, ФЛ $→$ АА, ЛЛ $→$ АФ, ФФ $→$ ЛА или АА $→$ ФЛ. Известно, что ЛЛАФАЛАФФАЛАФФФАЛАФФФФАЛЛ — это слово из языка альфов. Есть ли в языке альфов слово ЛФАЛФАЛФАЛФАЛАФЛАФЛАФЛАФЛ?

Источники: Миссия выполнима - 2018, 11.8 (см. mission.fa.ru)

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

Подсказка 1

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

Подсказка 2

Самое простое — обратить внимание на количество каждой из букв. Очевидно, что количество каждой буквы меняется. Помним, что часто при доказательстве неизменности свойства используют какой-то модуль. Чтобы что-то заметить, можно попробовать выписать короткие строки и записать количество каждой буквы, постепенно преобразовывая строку.

Подсказка 3

Обратим внимание на разность количества букв А и Л!

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

Пусть $a(w),ℓ(w)$ определяют по слову $w$ языка альфов количество в нём букв А и Л соответственно. Заметим, что все операции не меняют значения величины $a(w)− ℓ(w)$ по модулю $3.$ Действительно, порядок букв на это свойство не влияет. Остальные же операции либо просто не меняют эту разность (ЛА $→$ ФФ, ФФ $→$ ЛА), либо изменяют ровно на $3$ (АФ $→$ ЛЛ, ФЛ $→$ АА, ЛЛ $→$ АФ, АА $→$ ФЛ). Но тогда значение $a(w)− ℓ(w)$ должно совпадать по модулю $3$ для двух рассмотренных слов. Для ЛЛАФАЛАФФАЛАФФФАЛАФФФФАЛЛ оно равно $8− 7 =1,$ а для ЛФАЛФАЛФАЛФАЛАФЛАФЛАФЛАФЛ равняется $8− 9= −1.$ Эти числа не равны по модулю $3.$

Ответ:

Нет

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

Задача 6#74606

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

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

Подсказка 1

Давайте скорее перейдём от этих длинных условий к красивому математическому уравнению. Нам понадобятся всего 3 переменные: n - кол-во игроков, k - кол-во игроков в первой группе, m - партии между разными группами. Если внутри группы были сыграны все игры, то у нас получился полный граф на k вершинах. А сколько рёбер в полном графе на k вершинах?

Подсказка 2

Верно k*(k-1)/2. Теперь у нас есть все знания, чтобы составить уравнение на кол-во партий.

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Ура, мы получили понятные выражения на n и можем воспользоваться тем, что 0 < m <= 4, к сожалению, нам теперь остаётся только оценить большее из них и пытаться найти пример или доказывать, что такого не бывает.

Подсказка 6

Из наших выражений следует, что n <= 20, не бойтесь перебирать каждое из них с конца и подставлять в исходное квадратное уравнение. Так же помните, что k - целое, да ещё и в силу того, что в другой команде n-k игроков, то не имеет особого смысла рассматривать k < n/2, это такой же случай, просто мы поменяли местами номера команд.

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

Пусть число участников турника равно $n,$ а число попавших в $1$ -ю группу равно $k$ . Тогда число сыгранных партий равно:

k(k− 1) (n − k)((n− k)− 1) ---2-- + ------2-------+ m = 99,

где $0 <m ≤ 4$

k2− k+ (n − k)2− (n − k)+ m − 198= 0

k2 − k+ k2− 2kn +n2− n+ k+ 2m− 198= 0

2 2 2k − 2kn+ (n − n +2m − 198)= 0;

D-=n2 − 2(n2− n +2m − 198)≥ 0 4

(n− 1)2− (397− 4m)≤ 0

откуда $√------- nmax =1+ 397− 4m≤ 20.$

Если $n= 20,$ то:

2k2− 40k+(400− 20+ 2m − 198)= 0⇔

⇔ k2− 20k +91+ m = 0,

тогда $k= 10,n− k = 10,m =9$ - противоречие;
$k =11,n− k= 9,m = 8$ - противоречие;
$k =12,n− k= 8,m = 5$ - противоречие;
$k =13,n− k= 7,m = 0$ - противоречие;
при $k > 13$ и $m < 0.$

Если $n= 19,$ то:

2k2− 38k+(361− 19+ 2m − 198)= 0⇔

⇔ k2− 19k +72+ m = 0,

тогда $k= 10,n− k = 9,m = 18$ - противоречие;
$k =11,n− k= 8,m = 16$ - противоречие;
$k =12,n− k= 7,m = 12$ - противоречие;
$k =13,n− k= 6,m = 6$ - противоречие;
при $k > 13$ и $m < 0.$

Если $n= 18,$ то:

2k2− 36+ (324− 18+ 2m − 198)= 0⇔

⇔ k2− 18+ 54+ m= 0,

тогда $k= 9,n− k= 9,m = 27$ - противоречие;
$k =10,n− k= 8,m = 26$ - противоречие;
$k =11,n− k= 7,m = 23$ - противоречие;
$k =12,n− k= 6,m = 18$ - противоречие;
$k =13,n− k= 5,m = 11$ - противоречие;
$k =14,n− k= 4,m = 2$ - решение.
при $k > 13$ и $m < 0.$

Итак, наибольшее возможное число участников равно $18$ , группы участников насчитывают $4$ и $14$ человек, количество «межгрупповых» партий равно $2$ .

Ответ: 18

Курсы

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

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

Задача 7#77822

В некоторой компании ни у каких двух сотрудников нет работы одинаковой сложности, и никакие двое не получают одинаковую зарплату. 1 апреля каждый сотрудник сделал два утверждения:

(a) Не найдется 12 сотрудников с более сложной работой.

(b) По меньшей мере 30 сотрудников имеют большую зарплату.

Сколько сотрудников в компании, если часть сотрудников дважды сказали правду, а остальные дважды солгали?

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

Подсказка 1

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

Подсказка 2

Понятно, что такие случаи приводят к противоречию, а значит хотя бы 1 солгал и хотя бы 1 сказал правду. Часто бывает, что в задачах, в которых каждый элемент группы обладает количественным свойством, полезно взять самого сильного или самого слабого из них, потому что он потенциально несёт в себе намного больше полезной информации. А у нас как раз образовалось 2 группы: с правдивыми сотрудниками и лжецами.

Подсказка 3

Попробуйте порассуждать о самом богатом правдивом сотруднике и самом бедном лжеце. Нам хотелось бы как-то оценить кол-во каких-то сотрудников, очень удобно, что одна и та же фраза для лжеца и правдивого сотрудника даёт оценки сверху и снизу, поэтому в теории могла бы дать точное число каких-то сотрудников. (P.S. из численных данных о сотрудниках у нас есть только 2 числа, поэтому очень велика вероятность, что ответ - это сумма или разность этих чисел, что тоже стоит держать в уме при решении подобных задач, но это не означает, что так происходит всегда!)

Подсказка 4

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

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

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

Возьмем сотрудника, сказавшего правду с наибольшей зарплатой из всех правдивых сотрудников. Поскольку из его второго утверждения следует, что по меньшей мере $30$ «лжецов» имеют большую зарплату, чем он. Второе утверждение солгавшего сотрудника, имеющего наименьшую зарплату среди «лжецов» ложно, таким образом, не более $29$ «лжецов» имеют большую зарплату и не более $30$ «лжецов» всего. То есть лжецов всего $30.$

Первое утверждение для «лжеца» с наиболее трудной работой среди всех «лжецов» ложно, поэтому существуют по меньшей мере $12$ правдивых сотрудников, имеющих более трудную работу.

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

Ответ: 42

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

Задача 8#88674

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

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

Подсказка 1

По условию двое игроков у нас выкладывают по 2 или 3 монеты. Но тогда за два хода суммарно какое число монет удобно выложить? Попробуйте перебрать хорошо известные стратегии.

Подсказка 2

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

Подсказка 3

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

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

Пусть первый игрок своим первым ходом положит $2$ монеты, а следующими ходами класть столько монет, чтобы сумма его монет и монет, положенных перед этим вторым игроком была равна $5.$ В этом случае после третьего хода первого игрока в ряду будут лежать $12$ монет. Далее, как бы не сходил второй игрок своим третьим ходом и как бы после этого не сходил первый игрок $16$ монета будет положена первым игроком.

Ответ:

Первый игрок

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

Задача 9#94875

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

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

По принципу Дирихле как минимум в одном филиале как минимум 41 участник и как минимум 21 из них одного пола. Требуется доказать, что по меньшей мере 5 из этих 21 участника одного возраста.

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

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

Задача 10#77815

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

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

Подсказка 1

Так, нам надо посчитать, сколько всего вариантов кода. Что делать с тем условием, что у нас есть числа 21 и 16? Хочется понять, как они вообще могут быть расположены в коде друг относительно друга.

Подсказка 2

Ага, есть 3 варианта взаимного расположения чисел 21 и 16… Осталось только посчитать, сколько способов заполнить остальные места в коде!

Подсказка 3

И не забыть, что что-то мы случайно могли посчитать дважды!

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

Рассмотрим случаи.

1) Код содержит комбинацию цифр $216$ . Ее можно расположить в коде тремя способами: $∗∗216$ , $∗216∗$ или $216∗∗$ . В каждом из этих возможных кодов каждую из остальных цифр можно выбрать $10$ способами. Таким образом, получается $3⋅100 =300$ вариантов.

2) Код содержит комбинации $21$ и $16$ , причем комбинация $21$ расположена левее. Тогда оставшуюся цифру можно выбрать $10$ способами и поставить ее на одно из трех мест: перед $21$ , между $21$ и $16$ , после $16$ . То есть $30$ вариантов.

3) Код содержит комбинации $21$ и $16$ , причем комбинация $21$ расположена правее. Аналогично - $30$ вариантов. Заметим, что числа $21616$ , $21621$ , $21216$ , $16216$ мы посчитали дважды. Таким образом, чтобы открыть сейф достаточно перебрать $300 +30+ 30− 4 =356$ номеров.

Ответ: 356

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

Задача 11#94455

Бухгалтеры, менеджеры и экономисты банка сидят за круглым столом. Когда директор попросил поднять руку бухгалтеров, рядом с которыми сидит экономист, руку подняли $20$ человек. А когда директор попросил поднять руку менеджеров, рядом с которыми сидит экономист, руку подняли $25$ человек. Докажите, что рядом с кем-то из поднимавших руку сидит сразу два экономиста.

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

Подсказка 1

Давайте пойдём от противного. Сколько раз каждый человек поднимал руку? А если смотреть со стороны экономистов: сколько раз с каждым могли поднять руку?

Подсказка 2

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

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

Назовем группой экономистов несколько (возможно, одного) экономиста, сидящих подряд, слева и справа от которых сидят представители других профессий. При этом если нет менеджера или бухгалтера, рядом с которым сидят два экономиста, то каждый человек поднял руку не более одного раза, а тогда общее количество поднявших руку людей равно удвоенному количеству групп, т.е. четно. А по условию их $45.$ Противоречие.

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

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