Разбор задач
Задача 1
Условие:
Есть этаж N: с него (и выше) яйцо разбивается, ниже — нет. Два яйца. Нужно найти N, минимизируя гарантированное число бросков в худшем случае.
Разбор решения:
С двумя яйцами нельзя делать чистый “бинарный поиск”: если первое яйцо разобьётся, второе останется одно, и придётся идти по этажам по одному.
Идея оптимальной стратегии:
Мы выбираем этажи так, чтобы в худшем случае общее число бросков было одинаковым.
Пусть мы хотим уложиться в k бросков в худшем случае. Тогда:
- 1-й бросок делаем с некоторого этажа.
- Если яйцо разбилось — остаётся k−1 попытка вторым яйцом, значит можно проверить не больше k−1 этажей снизу (по одному).
- Если не разбилось — поднимаемся выше, но тогда высота следующего прыжка должна быть меньше, чтобы всё равно оставалось достаточно попыток.
Поэтому шаги делаем убывающими: k, затем (k−1), затем (k−2), …, затем 1.
Суммарно за k бросков мы сможем “покрыть”:
k + (k−1) + … + 1 = k(k+1)/2 этажей.
Нужно покрыть 100 этажей:
k(k+1)/2 ≥ 100.
Проверяем:
- 13×14/2 = 91 (мало)
- 14×15/2 = 105 (достаточно)
Значит минимальное k = 14.
Ответ: 14.
Задача 2
Условие:
Вероятность, что за 30 минут проедет хотя бы 1 авто, равна 95%.
Считаем поток стационарным и независимым во времени. Найти вероятность “хотя бы 1 авто” за 10 минут.
Разбор решения:
Удобнее считать событие “за время не проехало ни одной машины”.
Обозначим:
-
P0(30) — вероятность ноль машин за 30 минут.
Тогда: P(хотя бы 1 за 30) = 1 − P0(30) = 0.95
Значит: P0(30) = 0.05.
При постоянной интенсивности вероятность “ничего не произошло” за интервалы складывается мультипликативно:
30 минут = три независимых интервала по 10 минут, значит:
P0(30) = P0(10)^3.
Тогда:
P0(10)^3 = 0.05
P0(10) = 0.05^(1/3) ≈ 0.368.
Значит вероятность “хотя бы 1 авто за 10 минут”:
1 − 0.368 ≈ 0.632 → 63% (округляем).
Ответ: 63
Задача 3
Условие:
Каждый видит браслеты всех остальных, свой — нет.
Нельзя сообщать цвета.
Организатор говорит: “Есть хотя бы один синий”.
Если синих ровно 10 — через сколько дней все синие уедут?
Разбор решения:
Работает цепочка рассуждений “по уровням”.
Если бы синий был один
Он видит 0 синих. После объявления он понимает: “значит синий — я”.
Уедет в 1-й день.
Если синих двое
Каждый видит 1 синего и думает: “если я серый, то синий всего один, и он уедет в 1-й день”.
Но в 1-й день никто не уехал → значит “я тоже синий”.
Оба уедут во 2-й день.
Общий шаг
Если синих k, то каждый видит k−1 синих и рассуждает так же:
“Если я серый, то синих k−1, и они должны уехать на (k−1)-й день”.
Если этого не происходит, на следующий день становится ясно, что синих k, и все уезжают в k-й день.
При k = 10 все синие уедут на 10-й день после объявления.
Ответ: 10
Задача 4
Условие:
Номиналы 1, 5, 10, 25, 50, 100.
Нужно взять минимальное количество монет (с фиксированными штуками), чтобы можно было выдать любую сумму от 1 до 99.
Разбор решения:
Это задача про “покрытие диапазона сумм”.
Главное правило:
Если мы уже можем составить любую сумму от 1 до X, то добавив монету номинала v, мы сможем составить суммы до X+v, только если v ≤ X+1. Иначе появляется “дырка” — сумму X+1 не собрать.
Строим оптимально, начиная с 1: Чтобы собрать 1, нужна монета 1. Теперь X = 1.
Дальше выгодно брать монеты так, чтобы максимально расширять диапазон:
Берём ещё 1 (вторая монета 1), тогда можем собирать 1..2 → X = 2.
Берём ещё 1 (третья монета 1) → 1..3 → X = 3.
Берём ещё 1 (четвёртая монета 1) → 1..4 → X = 4.
Теперь можно добавлять 5 (потому что 5 ≤ X+1 = 5):
Берём 5 → теперь можем собирать 1..9 → X = 9.
Теперь можно 10 (10 ≤ 10):
Берём 10 → 1..19 → X = 19.
Теперь можно 25 (25 ≤ 20? нет, нельзя). Значит надо сначала добрать ещё 10:
Берём ещё 10 → 1..29 → X = 29.
Теперь можно 25 (25 ≤ 30):
Берём 25 → 1..54 → X = 54.
Теперь можно 50 (50 ≤ 55):
Берём 50 → 1..104 → X = 104, значит 1..99 покрыто.
Сколько монет взяли: четыре по 1 + один 5 + два 10 + один 25 + один 50 = 4+1+2+1+1 = 9.
Ответ: 9
Задача 5
Условие:
25 человек, забег по 5. В забеге известно только место 1..5. Найти 3 самых быстрых. Минимум раундов?
Разбор решения:
Сначала нужно “отсеять” до лучших. Делим 25 на 5 групп по 5 и проводим 5 забегов.
Победители групп — кандидаты в общий топ.
После 5 забегов у нас есть результаты внутри каждой группы.
Проводим 6-й забег: бегут 5 победителей групп.
Получаем их порядок, например:
A1 быстрее B1 быстрее C1 быстрее D1 быстрее E1.
Теперь ясно: группа E вообще не нужна, группа D почти не нужна, потому что её победитель уже 4-й среди победителей.
Кандидаты на топ-3 остаются:
- A1 (самый быстрый среди победителей)
- B1
- C1
и ещё те, кто мог быть вторым/третьим в группе A и B, потому что они могли быть быстрее C1.
Точный список кандидатов:
- A1, A2, A3
- B1, B2
- C1
Итого 6 человек на 3 места.
7-й забег: запускаем A2, A3, B1, B2, C1 (5 человек).
По его результатам можно однозначно определить 2-е и 3-е места в общем зачёте (1-е уже A1).
Итого раундов: 5 + 1 + 1 = 7.
Ответ: 7.
Задача 6
Условие:
В аквариуме плавает пустой пластиковый контейнер. Есть тяжёлый металлический брусок.
- Положить брусок в контейнер (контейнер плавает).
- Бросить брусок в воду (он тонет).
В каком случае уровень воды поднимется выше?
Разбор решения:
Ключевая идея: уровень воды зависит от того, какой объём воды вытесняется.
Вариант 1: брусок в контейнере
Контейнер с грузом должен вытеснить столько воды, чтобы сила Архимеда уравновесила вес: вытесненный объём воды соответствует массе бруска (и контейнера, но он был уже и так).
То есть добавка к вытеснению зависит от веса бруска: дополнительный вытесненный объём = масса бруска / плотность воды.
Вариант 2: брусок в воде (тонет)
Тонущий брусок вытесняет воду своим объёмом, потому что он просто занимает место в воде:
вытесненный объём = объём бруска.
А масса бруска = плотность металла × объём бруска.
Плотность металла больше плотности воды → значит: масса бруска / плотность воды > объём бруска.
То есть в контейнере вытеснение больше, чем когда он просто лежит на дне.
Вывод: уровень воды поднимется выше, если брусок положить в контейнер.
Ответ: в контейнере