?

Log in

No account? Create an account

Предыдущая запись | Следующая запись

Публикуем февральские решения тест-задачек «Квантика»!
После подведения итогов конкурса, победителем становится Максим Орлов. Поздравляем! Остальным участникам конкурса желаем удачи в решении мартовских задач :)
Скачать решения в формате PDF: https://yadi.sk/i/5F3DWSEg3FUZAY.
1. «Переправа»
Ночь. Мальчик, папа, мама и бабушка находятся на одном берегу реки и хотят перейти по мосту на другой берег. Они имеют при себе один фонарик. По мосту могут идти максимум двое (обязательно с фонариком). Папа способен преодолеть мост за 1 минуту, мальчик — за 2, мама — за 5, бабушка — за 10 минут. За какое наименьшее время все они смогут переправиться на другой берег?
Решение:
Кажется, что оптимальным способом является способ, при котором самый быстрый (папа) по очереди переводит всех остальных, каждый раз возвращаясь назад с фонариком. При этом затраченное время будет равно 10 + 1 + 5 + 1 + 2 = 19 минут. Однако можно быстрее! Основная идея заключается в том, чтобы двое самых медленных (мама и бабушка) шли по мосту вместе. При этом на другом берегу уже должен быть кто-то более быстрый, чтобы вернуться назад с фонариком. Итак, сначала идет папа и мальчик, мальчик остается, а папа возвращается назад с фонариком. Затем идут мама и бабушка вместе, а мальчик возвращается назад с фонариком. Наконец, папа и мальчик вместе переходят на другой берег. Всего получаем 2 + 1 + 10 + 2 + 2 = 17 минут.
2. «100 боксёров»
В турнире по олимпийской системе (проигравший выбывает) участвует 100 боксёров. Была составлена какая-то сетка турнира (расписание боёв). Сколько боёв нужно будет провести, чтобы выявить победителя?
Решение:
После каждого боя из соревнований выбывает один боксер — проигравший в этом бою. Поскольку всего к концу соревнований должны выбыть все, кроме победителя, всего должно быть 99 боев, независимо от того, как составляется расписание!
3. «Яндекс.Пробки»
Сервис Яндекс.Пробки показал загруженность улиц города (см. рисунок). Зелёный, жёлтый или красный участок между двумя соседними перекрестками показывает, что время движения на автомобиле по этому участку равно 1, 2 или 3 минуты соответственно. А за какое наименьшее время можно проехать из точки A в точку B?
Решение:
Будем решать задачу «с конца». Так сначала определим наименьшее время, которое требуется, чтобы доехать от каждого из перекрестков на прямой 7 до B (последний шаг), затем от каждого из перекрестков на прямой 6 до B (предпоследний шаг) и т.д. (см. рисунок). При этом в каждом узле записываем наименьшее время от этого узла до B и стрелочкой указываем, в каком направлении нужно двигаться из этого узла, чтобы путь до B был оптимальным.
Теперь можно, двигаясь от A до B по стрелочкам, получить оптимальный маршрут (всего будет ровно два оптимальных маршрута). При этом, наименьшее затраченное время будет равно 14 минут.
4. «Дни рождения»
Какова вероятность того, что в классе из 30 учеников хотя бы у двоих дни рождения совпадают?
Решение:
Интуитивно кажется, что такая вероятность должна быть мала, но здесь интуиция нас обманывает! Давайте посчитаем. Пусть у нас есть случайная выборка школьников одного года рождения. Ей соответствует набор (x1, x2, x3, …, x30), где х_i – целое число от 1 до 365 (номер дня в году, когда родился i-й школьник; считаем, что год не является високосным).
По правилу комбинаторики: число всех возможных наборов равно 365 в степени 30; а число наборов, в которых нет повторений, равно 365*364*363*….*(365-29) (первый элемент можно выбрать 365-ю способами, второй – 364-мя, третий – 363-мя, ….).
Поэтому вероятность того, что в случайной выборке у каких-то двух школьников совпадут дни рождения равна
1 - (365/365)*(364/365)*(363/365)*….*((365-29)/365) = 0.706...
Это выражение можно очень быстро вычислить, например, в программе Excel.
Видим, что вероятность получилась достаточно большой!

Comments

( 1 коммент — Оставить коммент )
user_ami
Mar. 11th, 2017 01:25 pm (UTC)
3) Не поняла только, зачем решать задачу "с конца". Наименьшее время для каждого из перекрёстков можно выписать и начиная с ближайших к точке А.
( 1 коммент — Оставить коммент )

Календарь

November 2018
S M T W T F S
    123
45678910
11121314151617
18192021222324
252627282930 
Powered by LiveJournal.com
Designed by Tiffany Chow