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

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

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

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

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

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

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

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

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

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

Задача 1#104131

Неизвестный 100-значный код $X$ составлен из цифр 1 и 2. Характеристикой произвольного 100-значного числа $Y$ , также составленного из единиц и двоек, назовём количество разрядов, в которых цифры числа $Y$ совпадают с цифрами кода. Докажите, что, узнав характеристики некоторых фиксированных 80 чисел $Y1,...,Y80$ , можно определить $X$ .

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

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

Подсказка 1

Давайте для начала подумаем, как найти количество единиц и двоек в Х? Характеристику какого числа Y нужно узнать?

Подсказка 2

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

Подсказка 3

Разбейте все числа на пятёрки, и найдите количество единиц в каждой пятёрке. Как теперь за несколько действий определить, из каких цифр состоит эта пятерка?

Подсказка 4

Пятёрки так же можно поделить на кусочки поменьше! Например, нам может помочь, что если в паре 0 или 2 единицы, то их позиции определяются однозначно!

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

Сначала подставим число, состоящее из всех единиц, чтобы узнать их количество в $X.$

Далее будем рассматривать пятерку чисел, о которой мы будем знать количество единиц в ней, подставив число, состоящее из 5 двоек на позициях рассматриваемой пятерки. Далее в нашей пятерке зафиксируем число на произвольной позиции, относительно которого будем рассматривать пары чисел, подставляя на их позиции число 2. Таким образом, проведя 3 таких операции, мы определим число единиц в каждой такой паре. Значит, если в какой-то паре мы получили ответ, что в ней 0 или 2 единицы, то их позиции определяются однозначно. Зная, какая цифра находится на фиксированной позиции, мы однозначно определяем позиции остальных чисел. Если на все три пары мы получили ответ, что в них находится одна единица, то у нас возможны 2 варианта: либо на фиксированной позиции стоит цифра 2, а в остальных 1, либо наоборот, на фиксированной позиции стоит цифра 1. Зная количество единиц в этой пятерке, мы можем однозначно определить, какой из этих случаев выполняется.

Разбив число $X$ на 20 таких пятерок, получим, что мы определяем его за $1+ 20⋅4 =81$ ход, но зная общее количество единиц в числе $X$ и число единиц в каждой из 19 пятерок, мы можем определить количество единиц в последней пятерке, не тратя на это ход. Следовательно, узнав характеристики 80 чисел $Y,$ можно однозначно определить число $X.$

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

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

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

Задача 2#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

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

Задача 3#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

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

Задача 4#73683

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

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

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

Подсказка 1

Рассмотрите маршрут, проходящий через города A₁, A₂, ... , Aₘ. Воспользуйтесь тем, что каждый перелет — централизующий.

Подсказка 2

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

Подсказка 3

При некотором значении m между A₁ и Aₘ будет маршрут, что даст противоречие. Получится оценка сверху на m, останется подобрать пример.

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

Через $|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$

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

Задача 5#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$

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

Задача 6#108627

Каждый из 25 учеников 11 «А» класса дружит ровно с двумя учениками 11 «Б», а все ученики 11 «Б» имеют разные наборы друзей в 11 «А». Каким наибольшим может быть число учеников в 11 «Б»?

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

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

Подсказка 1

Будем рассуждать только о парах друзей из разных классов. Какую информацию нам дает первое предложение условия?

Подсказка 2

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

Подсказка 3

Пусть k человек из Б дружат ровно с 1 человеком. Что можно сказать про k? Что можно сказать про остальных?

Подсказка 4

На самом деле, k может быть не таким уж большим! А все остальные n-k человек (n - размер класса Б), быть может, кроме одного, дружат уже как минимум с двумя ребятами!

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

Каждых двух учеников, которые учатся в разных классах и дружат между собой, назовём смешанной парой. Поскольку каждый из 25 учеников 11 «А» входит ровно в две такие пары, то всего имеется 50 смешанных пар.

Пусть в 11 «Б» учится $n$ человек, причем ровно $k$ из них имеют ровно по одному другу в 11 «А». Из условия задачи следует, что $k ≤25.$

Кроме того, в этом классе может найтись не более одного ученика, не имеющий друзей в 11 «А».

Каждый из остальных $n− k− 1$ (если такой ученик один) или $n− k$ (если таких учеников нет) учеников 11 «Б» входит по меньшей мере в две смешанные пары. Значит, общее число смешанных пар больше или равно $k+ 2(n − k − 1)= 2n− k− 2.$

Сложив неравенства $2n − k− 2≤ 50$ и $k≤ 25,$ получим $2n− 2≤ 75,$ откуда $n ≤38.$

С другой стороны, построим пример, показывающий, что равенство $n= 38$ возможно. Так как $n= 38,$ то, подставив в неравенство, найдем ограничение на $k$ снизу:

2⋅38− k− 2 ≤50

Совмещая с ограничением сверху, получаем, что $24≤ k≤ 25.$ Возьмем $k =25.$ Пусть ученики класса «А» — это $a1,a2,...a25,$ а класса «Б» — $b1,b2,...b38.$ Тогда распределение следующее:

1.: $b1$ не дружит ни с кем.
2.: Каждый ученик $b2,b3,...b26$ дружит с одним из $a1,a2,...a25$ соответственно.
3.: Ученики с $b27$ по $b38$ (их ровно 12) дружат так: $b27$ — с $a1$ и $a2,$ $b28$ — с $a3$ и $a4,$ и так далее. А так как в таком распределении $a25$ останется без второго друга, то просто сделаем $a25$ и $b38$ дружественной парой. Тогда у $b38$ будет три друга, но это не нарушает условие.

Ответ: 38

Курсы

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

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

Задача 7#105720

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

Источники: Миссия выполнима 2019

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

Подсказка 1:

Попробуйте решить задачу для какой-то значительно более маленькой таблицы. Затем, используя результат, сделайте оценку для 20×19.

Подсказка 2:

В качестве меньшей таблицы попробуйте взять квадрат 2×2

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

Рассмотрим квадраты $2 ×2.$ В каждом из них в зеленый цвет может быть окрашено не более $2$ клеток. Следовательно, в квадрате $20× 18,$ который можно разбить на $90$ квадратов $2×2$ может быть не более $180$ окрашенных клеток. Таким образом, всего может быть окрашено не более $180 +20$ клеток. Ниже представлен вариант, при котором этих покрашенных клеток будет ровно $200.$

$PIC$

Ответ:

$200$

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

Задача 8#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.$

Ответ:

Нет

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

Задача 9#74606

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

Источники: Миссия выполнима 2018

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

Подсказка 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

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

Задача 10#104671

Иван и Петр играют в следующую игру. Из кучки, которая содержит $2018$ камней, они по очереди берут некоторое количество камней. Если перед ходом в кучке имеется $N$ камней, то игрок может взять $k$ камней, только если $k$ является делителем числа $N.$ Проигрывает тот игрок, который возьмет последний камень. Кто из игроков имеет выигрышную стратегию, если первым берет камни Иван?

Источники: Миссия выполнима 2018

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

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

Ответ:

Иван

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

Задача 11#77822

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

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

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

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

Источники: Миссия выполнима 2017

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

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

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

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

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

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

Ответ: 42

Интенсивы

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

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

Задача 12#88674

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

Источники: Миссия выполнима 2017

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

Ответ:

Первый игрок

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

Задача 13#88675

Петя и Вася играют в игру. На доске написано число $11223334445555666677777.$ За один ход разрешается стереть любое число одинаковых цифр. Выигрывает тот, кто сотрет последнюю цифру. Петя ходит первым. Может ли он ходить так, чтобы гарантированно выиграть?

Источники: Миссия выполнима 2017

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Первым ходом Петя может, например, стереть все цифры $7.$ Оставшиеся группы одинаковых цифр можно разбить на пары:

| 11 | 22 333 | 444 5555|6666

После этого Петя (относительно средней черты) повторяет ходы Васи: стирает цифры “парные” ходу Васи и в таком же количестве.

Ответ:

Да, может.

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

Задача 14#94875

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

Источники: Миссия выполнима 2017

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

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

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

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

Задача 15#77815

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

Источники: Миссия выполнима 2016

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

Подсказка 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

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

Задача 16#94455

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

Источники: Миссия выполнима 2016

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

Подсказка 1

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

Подсказка 2

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

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

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