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

Двойной подсчёт

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

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

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

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

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

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

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

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

На окружности расположены черные и белые точки, всего $40$ точек. Известно, что ровно у $22$ точек есть по крайней мере одна соседняя черная точка, а ровно у $30$ точек есть по крайней мере одна соседняя белая точка. Сколько всего белых точек расположено на окружности?

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

Подсказка 1

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

Подсказка 2

Можно найти, у скольких точек оба соседа белые, у скольких оба чёрные, у скольких разных цветов. Тогда можно найти количество "соседств" с белыми точками.

Подсказка 3

Каждая белая точка является соседом ровно для двух других, что позволяет провести подсчёт двумя способами(или же уменьшить ответ в нужное число раз).

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

Из первого условия следует, что ровно у $18$ точек оба соседа белые, а из второго — что ровно у $10$ точек оба соседа черные. Это означает, что у оставшихся $40− 18− 10= 12$ точек соседи разного цвета.

Посчитаем всех белых соседей: $18⋅2+ 12 =48$ раз считаются белые соседи, при этом каждая точка учитывается дважды, так как у нее два соседа. Значит, белых точек $48∕2= 24.$

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

Ответ:

$24$

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

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

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

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

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

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

$PIC$

Отметим на одном циферблате положения часовых стрелок всех часов. Циферблат разобьется на $5$ секторов. Занумеруем их по кругу. Пусть часовая стрелка проходит секторы за время $x1,x2,x3,x4,x5$ соответственно (некоторые из этих чисел, возможно, нулевые). Заметим, что если мы станем устанавливать на всех часах время, соответствующее положению внутри сектора, то каждая часовая стрелка пройдет через начало сектора. Это значит, что суммарное время перевода окажется заведомо больше, чем если бы мы устанавливали все часы на начало сектора. Обозначим через $Si$ суммарное время, необходимое для установки всех часов на начало $i$ -го сектора. Ясно, что время перевода отдельной стрелки является суммой некоторых $xj.$ Например, время перевода на начало первого сектора равно $x5$ для пятых часов и $x2+ x3+x4+ x5$ для вторых. Тогда $S1 = (x2+ x3 +x4+ x5)+(x3+x4 +x5)+(x4+ x5)+x5 = x2+ 2x3 +3x4+ 4x5.$

Остальные $Si$ выражаются аналогично. Тогда $S1+ S2+S3+ S4+ S5 = (1 +2+ 3+ 4)(x1+x2 +x3+ x4+ x5)= 10⋅12= 120$ часов.

Поэтому наименьшая сумма не превосходит $120-= 24 5$ часа. С другой стороны, если все секторы одинаковы (например, часы показывают $12$ ч, $2$ ч $24$ мин, $4$ ч $48$ мин, $7$ ч $12$ мин и $9$ ч $36$ мин), то все $Si$ равны $24$ часам, поэтому менее, чем $24$ часами не обойтись.

Ответ:

За $24$ часа

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

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

В кружке $n$ ребят, причём любые двое ребят либо дружат, либо враждуют. Оказалось, что у каждого из ребят ровно 10 врагов в этом же кружке, причём если $A$ дружит с $B,$ но враждует с $C,$ то $B$ и $C$ враждуют. Найдите все возможные значения $n.$

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

Ясно, что у каждого есть одинаковое количество друзей, обозначим его через $x.$ Рассмотрим ребёнка $A$ и его $x$ друзей.

Ясно, что эти $x+ 1$ человек попарно дружат между собой и враждуют со всеми остальными. Удалим из кружка $A$ и его друзей. Найдём в среди оставшихся человека $A1$ и его $x$ друзей и также их удалим. Продолжая этот процесс далее, замечаем, что если в компании есть хотя бы один человек, то в ней есть компания из $x+1$ друзей, которую мы можем удалить. Значит, процесс закончится тогда, когда мы удалим всех детей из кружка. Отсюда заключаем, что $n$ кратно $x+ 1$ (пусть $n =k(x+ 1)$ ).

Теперь рассмотрим любого ребёнка. Он состоит в одной из компаний друзей, а с ребятами из остальных $k − 1$ компаний враждует. Значит, у него $(k− 1)(x+ 1)= 10$ врагов. Это уравнение имеет решения $x= 0,k =11;x= 1,k =6;x= 4,k =3;x= 9,k= 2.$

Этим решениям соответствуют $n =11,12,15$ и $20.$ Примеры строятся в соответствии с решением: $k$ групп по $x+ 1$ ребят. Внутри групп ребята дружат, а ребята из разных групп враждуют.

Ответ:

$n =11,12,15$ и $20$

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

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

Докажите тождество

1 2 3 n n− 1 Cn+ 2Cn+ 3C n+ ...+nC n = n2

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

Подсказка 1

Нетрудно понять, какое множество хотим рассматривать (из скольки элементов). Вопрос в том, что за объекты будем считать.

Подсказка 2

Справа непонятно совсем, поэтому давайте думать что за цешка из n по k, умноженная на k.

Подсказка 3

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

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

Пусть имеется $n$ школьников, из которых требуется выбрать дежурного и группу помощников для уборки (в группе помимо дежурного как ни странно может никого не быть).

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

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

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

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

Взяли несколько одинаковых равносторонних треугольников. Вершины каждого из них пометили цифрами $1,$ $2$ и $3.$ Затем их сложили в стопку. Могло ли оказаться, что сумма чисел, находящихся в каждом углу, равна $55?$

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

Подсказка 1

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

Подсказка 2

Посмотрите, на что делится сумма чисел во всех углах!

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

Сумма чисел в вершинах каждого треугольника равняется $6.$ Поэтому сумма чисел во всех углах стопки должна делиться на $6.$ Но если в каждом углу стопки сумма чисел равна $55,$ то сумма всех чисел равна $55 ⋅3$ — не делится на $6.$

Ответ:

Нет

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

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

В зачете принимали участие $n$ учеников и $m ≥ 3$ преподавателей. Известно, что $m$ нечетно. Каждый преподаватель ставил “зачет” или “незачет” каждому ученику. Оказалось, что любые два преподавателя поставили одинаковые оценки не более, чем $k$ ученикам. Докажите, что $nm-−n- k ≥ 2m .$

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

Подсказка 1

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

Подсказка 2

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

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

Обозначим за $S$ сумму по всем парам преподавателей числа совпавших оценок. Рассмотрим какого-то ученика. Пусть он $x$ раз получил зачёт, $m − x$ — незачет. Тогда посмотрим, сколько пар преподавателей выставили ему одну и ту же оценку. Это число равно

x(x− 1) (m − x)(m − x − 1) ---2-- + ------2-------

Заметим, что минимум этого выражения достигается при $m−1 x = -2--$ или $m+1 x= -2-,$ поскольку $m$ нечётно, а $x$ — целое. Тогда просуммируем по ученикам эту величину. Получим

S ≥n ⋅ ((m-+1)(m-−-1)+8(m-− 1)(m-−-3))

С другой стороны, для каждой из $m(m2−1)$ пар преподавателей таких совпадений не более чем $k.$ Значит, $S ≤ km(m2−1).$ Получаем, что

n ⋅ ((m-+1)(m−-1)+(m-− 1)(m-−-3))-≤km-(m-−-1) 8 2

Тогда $n ⋅ 2m4−2≤ km.$ То есть $k ≥ n(m2−m1),$ ЧТД.

Курсы

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

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

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

У Олега есть набор из 2024 различных клетчатых прямоугольников размеров $1× 1,$ $1 ×2,$ $1× 3,$ …, $1 ×2024$ (по одному прямоугольнику каждого размера). Может ли он, выбрав некоторые из них, составить какой-нибудь клетчатый квадрат площадью больше 1?

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

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

Подсказка 1:

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

Подсказка 2:

Например, ясно, что его площадь не меньше n², поскольку сторона не меньше n. Возможно, можно найти какое-то противоречие с этим?

Подсказка 3:

Какой может быть наибольшая площадь выбранных прямоугольников?

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

Предположим противное, и пусть $n> 1$ — наибольшая из длин выбранных прямоугольников. Тогда составлен клетчатый квадрат $k× k,$ где $k≥ n >1.$ Значит, его площадь не менее $2 n .$ С другой стороны, его площадь не больше, чем суммарная площадь всех прямоугольников

1× 1, 1×2, ..., 1× n,

то есть не больше

n(n+-1)- 2 1 +2+ 3+ ⋅⋅⋅+ n= 2 <n .

Противоречие.

Ответ:

не сможет

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

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

Пусть даны натуральные числа $x 1$ и $x . 2$ На прямой даны $y 1$ белых отрезков и $y 2$ чёрных отрезков, при этом $y ≥ x 1 1$ и $y ≥x . 2 2$ Известно, что никакие два отрезка одного цвета не пересекаются (даже не имеют общих концов). Также известно, что при любом выборе $x1$ белых отрезков и $x2$ чёрных отрезков обязательно какая-то пара выбранных отрезков будет пересекаться. Докажите, что

(y1 − x1)(y2− x2)< x1x2.

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

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

Первое решение. Пронумеруем белые отрезки слева направо как $w , 1$ $w , 2$ …, $w , y1$ а чёрные — как $b , 1$ $b, 2$ …, $b . y2$ Для каждого чёрного отрезка $bj$ назовём его силой $S(bj)$ количество индексов $i≤y1− 1$ таких, что $bj$ пересекается как с $wi,$ так и с $wi+1.$ Если с какой-то парой $(wi,wi+1)$ пересекаются два чёрных отрезка, то они имеют общую точку, что невозможно по условию. Поэтому каждая такая пара учтена в силе не более, чем одного чёрного отрезка, а значит,

y∑2 S (bj)≤y1− 1. j=1

Рассмотрим следующие $y1$ групп, состоящих из $x1$ белых отрезков каждая: при $0≤ i≤y1− x1$ группа $Gi$ состоит из отрезков $wi+1,$ $wi+2,$ …, $wi+x1,$ а при

y1− x1 +1≤ i≤ y1 − 1

группа $G i$ состоит из отрезков $w , i+1$ $w , i+2$ …, $w , y1$ а также из $w , 1$ $w , 2$ …, $w i+x1−y1$ (иначе говоря, каждая группа состоит из $x 1$ последовательных отрезков в циклическом порядке). Для группы $G i$ обозначим через $N(G) i$ количество чёрных отрезков, не пересекающихся ни с одним из отрезков в $G . i$ По условию, $N(G )≤x − 1; i 2$ поэтому

y1∑−1 N(Gi)≤ y1(x2− 1). i=0

С другой стороны, каждый чёрный отрезок $b j$ пересекается максимум $1 +S(b) j$ белыми отрезками, и все эти белые отрезки расположены подряд. Тогда количество групп, содержащих хотя бы один из этих белых отрезков, не превосходит

1+ S(bj)+ (x1 − 1)= S(bj)+x1.

Поэтому отрезок $bj$ учтён хотя бы в $y1 − (S(bj)+ x1)$ числах вида $N(Gi).$ Поэтому

y1∑−1N (Gi)≥ y∑2(y1− S(bj)− x1)= y2(y1− x1)− y∑2S(bj)≥y2(y1− x1)− (y1− 1). i=0 j=1 j=1

Из полученных двух оценок на сумму $N (Gi)$ вытекает, что

y1(x2− 1)≥ y2(y1− x1)− (y1− 1) ⇐⇒ (y1− x1)(y2− x2)≤ x1x2− 1,

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что утверждение задачи для некоторых $x1,$ $x2,$ $y1,$ $y2$ неверно:

(y1 − x1)(y2− x2)≥ x1x2,

и при этом условии сумма $y1 +y2$ — минимальная возможная.

Без ограничения общности тогда $y1 − x1 ≥ x1.$ Возьмём $x1$ -й слева белый отрезок $W$ и $(y2− x2)$ -й слева чёрный отрезок $B.$ У какого-то из них правый конец левее.

1) Пусть правый конец $W$ левее (или концы совпадают). Тогда правые $x2$ чёрных отрезков не пересекаются с левыми $x1$ белыми. Противоречие.

2) Пусть правый конец $B$ левее. Выкинем все белые отрезки слева от $W$ (включая его) и все чёрные отрезки слева от $B$ (включая его). Оставшиеся белые отрезки (их хотя бы $x 1$ ) не пересекаются с выкинутыми $y − x 2 2$ чёрными; отсюда уже следует, что $y2− x2 < x2.$

Положим

′ ′ ′ ′ x1 = x1, y1 = y1 − x1 ≥ x1, x2 =x2 − (y2− x2)

′ ′ y2 =y2− (y2− x2)= x2 ≥x2;

тогда осталось $y′ 1$ белых и $y′ 2$ чёрных отрезков. Рассмотрим любые $x′ 1$ оставшихся белых и $x′ 2$ оставшихся чёрных отрезков. Если среди них нет пересекающихся, то, добавив к ним все выкинутые чёрные отрезки, получим набор из $x1 = x′ 1$ белых и

′ x2 =x2+ (y2 − x2)

чёрных отрезков исходного набора, среди которых нет пересекающихся; это невозможно. Значит, оставшийся набор удовлетворяет условию для новых чисел $x′1,y′1,x′2$ и $y′2,$ при этом в нём меньше отрезков, чем в исходном, поэтому

0< x′x′ − (y′− x′)(y′− x′)= 12 1 1 2 2

= x1(2x2− y2)− (y1 − 2x1)(y2− x2)=

=x1x2− (y1− x1)(y2− x2)≤ 0.

Противоречие.

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

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

В классе $n$ мальчиков и $n$ девочек ( $n ≥3).$ Они расселись за круглым столом так, что никакие два мальчика и никакие две девочки не сидят рядом. У учителя есть $2n$ карточек, на них написаны числа $1,2,3,...,2n,$ каждое по одному разу. Он так раздал каждому школьнику по одной карточке, что число у любой девочки больше числа у любого мальчика. Затем каждая девочка написала на листочке сумму чисел на трех карточках: ее собственной и сидящих рядом с ней мальчиков. При каких $n$ все полученные $n$ чисел могли оказаться равными?

Источники: СПБГУ-23, 11.5 (см. olympiada.spbu.ru)

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

Подсказка 1

По условию понятно, что у мальчиков карточки от 1 до n, а у девочек - от n+1 до 2n. Вот пусть у девочек все суммы вышли равными какому-то m. Тогда можно ли понять, чему равно m?

Подсказка 2

Например, сумма всех чисел, полученных у девочек, будет равна mn. А с другой стороны, это сумма чисел девочек + удвоенная сумма чисел мальчиков) Посчитайте, чему тогда будет равно m.

Подсказка 3

Выйдет, что m = 2n+1 + (n+1)/2, откуда уже понятно, что n - нечетное. Можно ли для любого нечетного n подобрать пример?

Подсказка 4

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

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

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

Следовательно,

∑n 2∑n ∑2n ∑n mn =2 j+ j = j+ j = 2n(2n+-1)+ n(n-+1)= n(2n +1)+ n⋅ n-+1 j=1 j=n+1 j=1 j=1 2 2 2

Стало быть, $n+1- m = 2n+1 + 2$ и $n$ — нечетно. Пусть $n =2k− 1,$ тогда $m = 5k− 1.$ Для примера надо последовательно раздать карточки мальчикам от 1 до $2k− 1$ идя через одного. Если теперь для каждой девочки посмотреть на сумму чисел, на карточках соседних с ней мальчиков, то по одному разу получатся все суммы от $k+ 1$ до $3k− 1.$ Дальше нужно дополнить их числами от $2k$ до $4k − 2$ (раздав соответствующие карточки девочкам) так, чтобы все суммы стали равны $5k − 1.$ Пример раздачи карточек для $n = 9$ и $k =5$ показан на рисунке.

$PIC$

Ответ:

при нечетных $n$

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

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

На листе клетчатой бумаги с размером клетки $1×1$ изображен прямоугольник. Прямоугольник разбит прямыми, параллельными его сторонам на некоторое количество маленьких прямоугольников. У каждого маленького прямоугольника длины сторон выражаются целыми числами, при этом длина хотя бы одной его стороны чётна. Докажите, что длина хотя бы одной стороны исходного прямоугольника также является чётным числом.

Источники: Межвед-2023, 11.4 (см. www.academy.fsb.ru)

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

Подсказка 1

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

Подсказка 2

Площадь маленьких прямоугольников - чётная, значит, и большого - чётная)

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

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

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

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

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

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

Рассмотрим фиксированную арифметическую прогрессию длины $n$ . Заметим, что она присутствует ровно в $2n ⋅2 =2n+1$ различных раскрасках. Заметим, что всего таких прогрессий с разностью $1$ не больше $n 2 − n+ 1$ , с разностью $2$ ещё меньше и так далее. Максимальная разность меньше $n n−1 2 ∕2 =2$ . Итого всего прогрессии “портят” менее $n−1 n+1 2n 2 ⋅2 = 2$ раскрасок. Значит, есть хотя бы одна не испорченная раскраска (поскольку всего раскрасок как раз $2n 2$ ).

Интенсивы

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

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

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

Во взводе $10$ человек. В каждый из $100$ дней какие-то четверо назначались дежурными. Докажите, что какие-то двое были вместе на дежурстве не менее $14$ раз.

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

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

Предположим противное, пусть любые два студента пересекались на дежурстве не более $13$ раз. Посчитаем количество пар студентов, которые были на дежурстве за все $100$ дней. C одной стороны, оно не превосходит $2 13⋅C10 = 585,$ так как каждая пара была на дежурстве не более $13$ раз. С другой стороны, оно равно $2 100 ⋅C 4 = 600 >585.$ Пришли к противоречию.

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

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

В классе некоторые ученики дружат, некоторые нет. Известно, что у любых двух друзей есть ровно $5$ общих друзей. Докажите, что количество пар друзей делится на $3.$

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Учитывая, что каждое ребро входит ровно в 5 треугольников, удобно просто следить за тем, сколько треугольников «накручивается» на рёбра. Подумайте, как это поможет выразить общее число треугольников.

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

Будем считать учеников вершинами, а дружбу — ребром. Обозначим количество рёбер через $x,$ а количество треугольников в графе через $y.$ По условию каждое ребро является стороной ровно пяти треугольников. Следовательно, $5x- y = 3$ (поделили на три, потому что у каждого треугольника три стороны). Таким образом, $3y =5x.$ Теперь видно, что $x$ делится на $3.$

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

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

В думе $1600$ депутатов образовали $16000$ фракций по $80$ человек в каждой. Докажите, что найдутся $4$ депутата, состоящие вместе хотя бы в двух фракциях.

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

Подсказка 1

Обозначим n=16000. Предположим, что каждые две фракции имеют не более трёх общих членов. Пусть двое секретарей A и B составляют списки всевозможных председателей на три заседания Думы. A считает, что любой депутат может быть председателем на каждом из этих заседаний. Какое количество списков он получит?

Подсказка 2

Правильно, 1600³! B считает, что на каждом заседании могут председательствовать только члены одной(не важно, какой именно) фракции, поэтому сначала он запросил соответствующие списки от каждой фракции. Сколько B получит списков?

Подсказка 3

Верно! B получил получил 80³ ⋅n списков. После этого B выбросил из списков, поданных i-ой фракцией, те тройки, которые уже вошли в списки одной из предыдущих i− 1 фракций. Сколько максимум B выбросил списков?

Подсказка 4

Точно! Так как каждые две фракции(а таких пар n(n-1)/2) выдвинули всех своих общих членов, то B при формировании своих списков выбросил не более, чем n(n-1)/2 * 3³ списков. Осталось заметить, что A точно составил не меньше списков, чем B, и записать это неравенство, получить противоречие.

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

Обозначим $n= 16000.$ Предположим, что каждые две фракции имеют не более трёх общих членов.

Пусть двое секретарей $A$ и $B$ составляют списки всевозможных председателей на три заседания Думы. $A$ считает, что любой депутат может быть председателем на каждом из этих заседаний, поэтому у него получилось $3 1600$ списков. $B$ считает, что на каждом заседании могут председательствовать только члены одной (не важно, какой именно) фракции, поэтому сначала он запросил соответствующие списки от каждой фракции и получил $3 80 ⋅n$ списков. После этого $B$ выбросил из списков, поданных $i$ -ой фракцией, те тройки, которые уже вошли в списки одной из предыдущих $i− 1$ фракций. Так как каждые две фракции (а таких пар $2 C n$ ) выдвинули всех своих общих членов, то $B$ при формировании своих списков выбросил не более, чем $2 3 Cn ⋅3$ списков.

Очевидно, что списков, которые составил $A,$ не меньше, чем списков, которые составил $B,$ то есть

1 16003 ≥803⋅n− 2n(n− 1)⋅33 >803⋅n− 16n2 =(803− 16n)n= (29⋅103− 28 ⋅103)= 16003

Противоречие.

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

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

Даны натуральные числа $n> 1,m.$ Пусть $S ={1,2,3,...,mn}. m$ Выбрали $2n$ различных подмножеств $A ,A ,A ,...,A 1 2 3 2n$ множества $Sm$ так, что каждые два подмножества имеют не более одного общего элемента. Оказалось, что любой элемент входит ровно в два выбранных подмножества. Докажите, что $m ≤ 2n− 1.$

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

Посчитаем различными способами общее количество троек $(k, A , i$ $A ) j$ , где $k∈ A i$ , $k∈ A j$ и $i⁄=j.$ С одной стороны, каждый из $mn$ элементов $S$ принадлежит ровно двум выбранным подмножествам. А, значит, таких троек ровно $mn.$ С другой стороны, для любой пары различных выбранных подмножеств мы можем сопоставить не более одной тройки. Т.е. их точно не больше, чем $2n(2n−-1)- 2 = n(2n− 1).$ В итоге мы получаем неравенство на $m$ и $n:mn ≤ n(2n − 1),$ откуда и получается искомое неравенство.

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

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

Даны натуральные $k,n$ такие, что $n >2k − 1.$ В $n$ -элементном подмножестве выбрано $l$ $k$ -элементных подмножеств, любые два из которых имеют общий элемент. Оказалось, что для любого не выбранного $k$ -элементного подмножества существует не пересекающееся с ним выбранное $k$ -элементное подмножество. Докажите, что $--Ckn-- l≥ Ckn−k+1.$

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

Посчитаем количество пар $(C,N ),$ где $|C|= |M |=k,C ∩N = ∅,C$ — выбранное подмножество, $N$ — невыбранное. С одной стороны, таких пар ровно $k lC n− k,$ т.к. для каждого из $l$ выбранных подмножеств есть ровно $k Cn−k k$ -элементных подмножеств, не пересекающихся с ним. И каждое из них точно не выбрано, иначе противоречие с условием, что любые выбранные подмножества пересекаются хотя бы по одному элементу. С другой стороны, по условию каждое невыбранное $k$ -элементное множество имеет непересекающееся с ним $k$ -элементное выбранное множество. Т.е. искомых пар как минимум столько же, сколько самих невыбранных $k$ -элементных множеств, т.е. $k Cn − l.$ В итоге получаем неравенство:

lCkn− k ≥Ckn− l

откуда и следует искомое.

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

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

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

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

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

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

Подсказка 1

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

Подсказка 2

Верно! Можно сказать, что это (n-1)k. Пусть конкретный человек состоит в A парламентах. Как тогда можно еще выразить такое число пар?

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

Пусть $n$ — количество людей в парламенте, $k$ — количество общих комитетов для любой пары парламентёров, а в каждом комитете по $t$ человек.

Зафиксируем одного из людей парламента (назовем его Фёдор). Рассмотрим для Фёдора всевозможные пары из человека и комитета такие, что этот человек и Фёдор находятся в одном комитете. С одной стороны, количество таких пар равно $(n− 1)k$ (с каждым из оставшихся $n − 1$ человеком Фёдор имеет $k$ общих комитета). С другой, оно равно $AФёдор(t− 1)$ (в каждом из $AФёдор$ комитетов имеется $t− 1$ оставшихся парламентёров), где $A Фёдор$ — количество комитетов, в которых состоит Фёдор. Получаем, что $(n− 1)k =A Фёдор(t− 1).$ Откуда следует, что $(n−1)k AФёдор = t− 1 .$ Но заметим, что для любого другого парламентёра, проведя аналогичные рассуждения, получим то же самое число в правой части. Значит $Aимя$ константное для любого парламентёра.

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

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

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

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

Подсказка 1

Что можно сказать о сумме попарных расстояний между фишками?

Подсказка 2

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

Подсказка 3

Сумма попарных расстояний между фишками равна сумме попарных расстояний между клетками доски и не зависит от перестановки фишек.

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

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

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

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

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

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

Источники: ВСОШ, РЭ, 2023, 10.9 (см. olympiads.mccme.ru)

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

Подсказка 1:

Для удобства расстояние между соседними столбами примем за единичное. Также пронумеруем их от 1 до n. Пусть nᵢ — количество столбов i-го цвета. Сколько всего будет искомых пар?

Подсказка 2:

Несложно догадаться, что для одного цвета таких пар nᵢ − 1 (количество промежутков). Значит, всего n₁ − 1 + ... + nₖ − 1 = n − k. Задача на оценку + пример, однако по условию нам дана только различность всех расстояний. Для примера, как мы можем оценить сумму 2-ух различных натуральных чисел, зная, что они от 1 до 5?

Подсказка 3:

Очевидно, что она ≥ 1 + 2 и ≤ 4 + 5. Применим аналогичную идею, только сумму чего будем оценивать?

Подсказка 4:

Кажется, хорошей идеей будет оценить сумму всех расстояний S. S ≥ 1 + 2 + ... + (n − k) = (n − k)(n − k − 1)/2. Да, мы получили какое-то неравенство, но оценку на количество из него пока что не вывести. Какое неравенство мы хотим получить для итоговой оценки?

Подсказка 5:

То, где с обеих сторон участвуют только переменные n и k. С правой частью мы справились, что же делать с левой?

Подсказка 6:

Необходимо выразить или оценить сверху S с помощью n и k (идея двойного подсчёта). Зайдём из далека. Как можно посчитать (не оценить) сумму расстояний для конкретного цвета?

Подсказка 7:

Попробуем сначала самым честным и пробивным способом. Пусть d₁, ..., dₚ — номера столбов первого цвета (НУО). Тогда искомая величина равна d₂ − d₁ + d₃ − d₂ + ... + dₚ − dₚ₋₁. А если покороче?

Подсказка 8:

Сумма расстояний для первого цвета = dₚ − d₁ (в целом, это интуитивно). Может обобщим эту идею?

Подсказка 9:

Пусть aᵢ — номер первого столбца i-го цвета, bᵢ — последнего. Тогда чему же равно S?

Подсказка 10:

S = b₁ − a₁ + ... + bₖ − aₖ = b₁ + ... + bₖ − (a₁ + ... + aₖ). Однако переменных k и n мы пока что не наблюдаем. Как бы их привязать к этому выражению?

Подсказка 11:

Разумеется, в явном виде выразить через n и k мы не сможем (ибо сумма может быть разной), значит, нужно вновь оценить сверху (чтоб нам на руку сыграла транзитивность в неравенствах). Посмотрим, что мы имеем: две суммы различных чисел. Кажется, мы где-то это уже видели...

Подсказка 12:

Поскольку мы хотим получить оценку сверху на S, то сумму b₁ + ... + bₖ нужно оценить снизу, а a₁ + ... + aₖ сверху. Метод нам известен, а что же получается в итоге?

Подсказка 13:

S ≤ k(n − k) (получите данный вид самостоятельно). Что же мы имеем? (n − k)(n − k − 1)/2 ≤ S ≤ k(n − k). Какая оценка на n у нас получилась?

Подсказка 14:

n ≤ 3k − 1. Осталось придумать пример. Он строится из оценки, всего лишь необходимо гарантировать равенства во всех выше написанных неравенствах. Успехов!

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

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

Оценка. Пусть $n$ столбов покрашено так, что условие задачи выполнено. Пусть $ni$ — количество столбов $i$ -го цвета (далее считаем, что $ni ≥ 1,$ т.е. все цвета присутствуют, иначе можно увеличить $n,$ добавив столб нового цвета в конец). Пусть $ai$ и $bi$ — номера первого и последнего столбов $i$ -го цвета.

Всего у нас есть

t=(n1− 1)+(n2− 1)+ ...+ (nk − 1)= (n1+n2+ ...+ nk)− k =n − k

хороших пар столбов. Поскольку все расстояния между столбами в хороших парах различны, наименьшее из этих расстояний не меньше 1, следующее — не меньше 2, и т.д. Итак, для суммы $S$ расстояний во всех хороших парах получаем оценку

S ≥ 1+2+ ...+ t= t(t+ 1)∕2

С другой стороны, сумма всех расстояний для $i$ -го цвета равна $b − a. i i$ Поэтому

S = (b1+ ...+ bk)− (a1 +...+ ak)

Сумма $b1+ ...+bk$ не превышает суммы $k$ самых больших среди номеров 1, 2, …, $n,$ а сумма $a1+ ...+ ak$ не меньше, чем сумма $k$ наименьших среди номеров 1, 2, …, $n,$ поэтому

S ≤ (n+ (n− 1)+ ...+(n− k+ 1))− (1+2+ ...+ k)=

= (n− 1)+ ...+ (n− k+1)− (1 +2+ ...+ k)= k(n− k)

Итак,

t(t+1)∕2≤S ≤ kt,

откуда $t≤ 2k− 1$ и

n= k+ t≤3k− 1.

Пример. Годится, например, покраска

1,2,...,k− 1,k,k,k− 1,...,2,1,2,3,...,k

Здесь для цвета 1 единственная хорошая пара, и расстояние между столбами в ней равно $2k− 1.$ Для всех остальных цветов есть две хорошие пары, при этом для цвета 2 имеем расстояния $2k− 3$ и 2, для цвета 3 — расстояния $2k− 5$ и 4, и т.д., для цвета $k$ — расстояния 1 и $2k− 2.$

Ответ:

$3k− 1$

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

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

Изначально в строку выписывают 250 букв — 125 букв A и 125 букв B в некотором порядке. Затем за одну операцию можно взять любой кусок из нескольких подряд стоящих букв, среди которых поровну букв A и B, и переставить буквы в этом куске в обратном порядке, поменяв в этом куске все буквы A на буквы B и буквы B на буквы A. (Например, из строки ABABBAB можно одной операцией получить строку ABBAABAB.) Можно ли выписать исходную строку и совершить несколько операций так, чтобы в результате на доске оказалась та же строка, буквы которой записаны в обратном порядке?

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

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

Обратите внимание на количество букв А на нечётных позициях. Как оно меняется при проведении операции?

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

Первое решение. Пронумеруем позиции в строке слева направо числами от 1 до 250. Пусть в исходной строке $x$ букв A стоят на нечётных местах (т. е. местах с нечётными номерами). Покажем, что в полученных строках это количество не изменится.

Действительно, пусть для некоторой операции выбран кусок, в котором по $y$ букв A и B, причём $t$ из этих букв A стоят на нечётных местах. Тогда на чётных местах в куске стоят $y− t$ букв A и, следовательно, $y− (y− t)= t$ букв B. После операции именно из этих $t$ букв B возникнут буквы A, стоящие на нечётных местах куска — значит, количество таких букв A не поменяется.

Итак, в любой полученной строке будет ровно $x$ букв A на нечётных местах. Однако, если строка развернётся задом наперёд, то на нечётных местах должны оказаться ровно те буквы, которые раньше были на чётных местах, а там было ровно $125− x$ букв A. Поскольку $125− x⁄= x,$ требуемое невозможно.

_________________________________________________________________________________________________________________________________________________________________________________

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

Рассмотрим одну операцию с куском длины $2y.$ При этой операции пары из букв, не лежащих в куске, сохраняют свой тип. Далее, для каждой буквы вне куска было ровно $y$ пар, содержащих её и букву из куска; столько же таких пар осталось, и все эти пары были и стали одного и того же типа.

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

Ответ:

нельзя