Тема КФУ (олимпиада Казанского Федерального Университета)

Комбинаторика на КФУ

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

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

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

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

Подтемы раздела кфу (олимпиада казанского федерального университета)

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

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

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

На ферме по выращиванию жемчуга проводится акция: посетителю разрешают вскрыть несколько раковин, до тех пор, пока он не найдет 2 жемчужины. В каждой раковине может быть не более одной жемчужины, причем вероятность, что она там будет, равна $1∕3.$ Аделаида Ивановна участвует в акции. Какова вероятность того, что она вскроет: а) ровно 4 раковины; б) не менее 4 раковин?

Источники: КФУ - 2025, 10.5 (см. malun.kpfu.ru)

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

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

Давайте порассуждаем: в каком случае вскрыто ровно 4 раковины? В какой из раковин жемчужина при этом точно была, а в какой – не факт? Сколько у нас подходящих вариантов?

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

Каждая раковина – независима от другой. Что в таком случае надо делать с вероятностями?

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

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

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

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

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

По сути нам надо из 1 вычесть сумму вероятностей того, что вскрыто ровно 2 или ровно 3 раковины. Осталось лишь решить задачу, аналогичную пункту а) и внимательно всё вычислить!

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

а) Ясно, что А.И. найдёт жемчужину в 4-ой раковине, а также ровно в одной из предыдущих. Имеем три варианта события, вероятность каждого равна

1 ( 2)2 1 4 3 ⋅ 3 ⋅3 = 81

Искомая вероятность в 3 раза больше:

3 ⋅ 4-= 4 81 27

б) Противоположное событие — что А.И. вскроет 2 или 3 раковины. Вероятность вскрыть две равна

1⋅ 1 = 1, 3 3 9

три раковины —

1 2 1 4- 2⋅ 3 ⋅3 ⋅3 = 27

Значит, вероятность не менее 4 раковин равна

1− 1 − 4-= 20 9 27 27

Ответ:

а) $-4; 27$ б) $20- 27$

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

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

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

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

В каждую клетку таблицы $21×22$ вписано число $1$ или $− 1.$ Под каждым столбцом записано произведение всех чисел столбца, а рядом с каждой строкой — произведение чисел строки. Какое наименьшее неотрицательное значение может принимать сумма всех этих произведений?

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Трем. Осталось привести пример, когда полученная оценка достигается. Возможно, в этом вам помогут соображения уже построенного процесса.

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

Сначала рассмотрим “крайнюю” ситуацию. Если во всех клетках таблицы числа равны $+ 1,$ то и все произведения равны $+ 1,$ а их общая сумма равна $21+ 22=43.$

Если мы сменим знак в одной из клеток, то изменится знак в произведении чисел одной строки и одного столбца. Значит, сумма всех произведений изменится на величину $± 2±2,$ то есть это изменение может равняться $4,0$ или $− 4.$ Таким образом, после замены знаков в нескольких клетках таблицы значение суммы может измениться лишь на слагаемое, кратное $4.$

Взяв за основу таблицу, заполненную числами $+ 1,$ и меняя знаки в соответствующих клетках (чтобы придти к исходной таблице), мы получим значение суммы $43 − 4k.$ Наименьшее неотрицательное значение выражения $43 − 4k,$ очевидно, равно $3,$ и оно достигается при целом $k =10.$

Осталось привести пример таблицы, для которой указанное значение суммы произведений равно $3.$ Расставим сначала во всех клетках таблицы $21× 22$ числа $+ 1,$ а затем заменим знак $+$ на $−$ у $10$ чисел, стоящих, например, на диагонали, идущей из левого верхнего угла в нижний. Для полученной таблицы сумма всех произведений равна $43− 10⋅4 =3.$

Ответ:

$3$

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

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

Сеть дорог соединяет $n$ населенных пунктов. Из каждого пункта выходит не более $3$ дорог. Если между какими-либо двумя пунктами нет дороги, то есть третий пункт, соединенный с ними обоими. Каково максимальное возможное значение $n?$

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

Подсказка 1

Пусть пункты будут вершинами, а дороги - рëбрами. Степень каждой вершины не больше 3, и при этом между каждой парой вершин есть путь длиной не более 2. Это наводит на мысль, что в этом графе в принципе не может быть слишком много вершин. Попробуйте сделать какую-то очень грубую оценку сверху.

Подсказка 2

Попробуйте рассмотреть произвольную точку А и еë соседей.

Подсказка 3

Также рассмотрите точку B, не соединëнную с А. Связана ли B с кем-то из соседей A?

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

Будем называть населенные пункты точками. Возьмем любую точку $A.$ Она соединена не более, чем с тремя точками $B,C,D.$ Любая другая точка $X$ должна быть соединена с одной из точек $B,C,D$ (поскольку она не соединена с $A$ ). Но каждая из них уже соединена с $A,$ так что может быть соединена не более чем с двумя другими точками, Следовательно, общее число точек не более $1+ 3+ 3⋅2= 10.$

Пример, показывающий, что $10$ точек возможно можно построить, например, так. Обозначим точки $A,B,C,D,E,F,G,H,I,J.$ Проведем дороги $AB,AC,AD,BE,BF, CG,CH,DI,DJ,EH,EJ,FG,F I,GJ$ и $HI.$

Ответ:

$10$