?

Log in

No account? Create an account

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

#тестзадачиквантика
Публикуем решения тест-задачек «Квантика» за ноябрь!

После подведения итогов конкурса, победителем становится Вадим Ретинский.
Поздравляем! Вас ждут призы от нашего интернет-магазина :)

Остальным участникам конкурса желаем удачи в решении декабрьских задач!

Скачать решения в формате PDF можно, перейдя по ссылке: https://vk.com/wall-35904602?w=wall-35904602_5415%2Fall.

1. «Ловушка»
Когда преступник прошёл 3/8 моста, он заметил приближающийся со скоростью 60 км/ч полицейский автомобиль. Если преступник побежит назад, то встретит автомобиль у начала моста. Если преступник побежит вперед, то автомобиль нагонит его у конца моста. С какой скоростью бегает преступник?

Решение.
Пусть s – длина моста. Преступник находился в точке O моста AB (см. рисунок), для которой AO = 3/8·s, OB = 5/8·s. Отметим точку C на участке OB, для которой OC = OA = 3/8·s. По условию, если преступник побежит назад, то встретит автомобиль у начала моста. Это означает, что если преступник побежит вперёд, то он окажется в точке C в тот момент, когда автомобиль будет у начала моста. При этом преступнику останется преодолеть четверть длины моста, а автомобилю всю длину моста. Но по условию автомобиль и преступник окажутся у конца моста (в точке B) одновременно. Значит, скорость преступника ровно в 4 раза меньше скорости автомобиля, т.е. равна 15 км/ч.

Комментарий: мы предполагали, что автомобиль будет двигаться по мосту с той же постоянной скоростью 60км/ч. Подумайте, как изменится ответ, если автомобиль не может двигаться по мосту со скоростью более v км/ч?

2. «Странные продавцы»
- Сколько стоят эти часы? – спросил Дима у продавца-консультанта.
- 12 тысяч рублей, - ответил продавец-консультант. К нему тут же подошёл второй.
- Знаете, мой напарник называет все числа в 3 раза больше, чем они есть на самом деле. А в остальном он совершенно прав, - сказал второй продавец.
- Так часы стоят 4 тысячи рублей? – переспросил Дима.
- Знаете, мой напарник все числа преуменьшает в 12 раз. А в остальном он совершенно прав, - сказал первый продавец.
Так сколько же стоят часы?

Решение.
Пусть первый продавец завышает все числа в x раз, а второй – в y раз (x и y могут быть и меньше 1, в этом случае цену занижают). Тогда по условию получаем, что должны выполняться два равенства для x и y:
x = 3 / y
y = 1 / (12/x) = x / 12

Подставляя выражение для y из второго равенства в первое, получаем: x·x = 36. Отсюда, x = 6, так как x > 0. Итак, на самом деле первый продавец завышает все числа в 6 раз, т.е. часы стоят 2 тысячи рублей.

3. «Схема города»
На рисунке изображена схема автодорог некоторого города: всего есть 2 кольцевые автодороги (две окружности с общим центром) и 6 дорог, которые сходятся в этом центре под равными углами. Вася думает, как ему проехать из A в B: по внешней кольцевой автодороге или по внутренней. Какой из этих двух маршрутов короче?

Решение.
Пусть радиусы малой и большой кольцевых автодорог равны r и R соответственно. Тогда длина пути из A в B по внешней кольцевой автодороге равна 2πR/3, а длина пути из A в B по внутренней кольцевой равна 2·(R-r) + 2πr/3. Первое слагаемое получается, поскольку часть пути проходит по двум дорогам, которые сходятся в центре города. Итак, нужно сравнить 2πR/3 и (2·(R-r) + 2πr/3). Ясно, что 2π(R-r)/3 > 2·(R-r), так как π > 3. Поэтому путь из A в B по внутренней кольцевой автодороге будет короче.

4. «Футбольный турнир»
Турнир по футболу, в котором участвовало 16 команд, проходил в один круг (каждая команда играет с каждой ровно один раз). Оказалось, что к некоторому моменту каждая команда сыграла не менее k матчей, но нет четырех команд, попарно сыгравших между собой. Чему равно наибольшее возможное значение k?

Решение.
Обозначим команды точками на плоскости. Соединим между собой две точки отрезком, если соответствующие команды сыграли между собой. Получаем так называемый граф. Точки – вершины этого графа, а отрезки – рёбра графа. Сначала ответим на следующий вопрос: какое наибольшее число рёбер может быть в графе, у которого n вершин и нет трёх вершин, попарно соединенных рёбрами (“граф без треугольников”)? Ответ на этот вопрос даёт теорема Турана.

Теорема Турана
В графе с n вершинами, не содержащем треугольников, не более n²/4 рёбер. Причём равенство достигается для двудольного графа, когда n чётно.

Комментарий: Двудольный граф получается так: все вершины разбиваются на два множества A и B, после чего любые две вершины из разных множеств и только они соединяются ребром. Ясно, что если n чётное и в каждом из множеств A и B по n/2 вершин, то в построенном графе будет ровно (n/2)·(n/2) = n²/4 рёбер и не будет треугольников.

Доказательство.
Пронумеруем вершины графа с n вершинами числами от 1 до n. Пусть rk – число рёбер, выходящих из вершины k, а R – общее число рёбер в графе. Пусть V0 – наибольшее “независимое” множество вершин (никакие две вершины из V0 не соединены ребром), а V1 – множество остальных вершин. Количество вершин в этих множествах обозначим n0 и n1 соответственно. При этом n0 + n1 = n. Заметим, что для любого k выполнено неравенство rk ≤ n0, так как в противном случае концы рёбер, выходящих из вершины k, образуют большее независимое множество (никакие две вершины этого множества не будут соединены ребром, так как в исходном графе нет треугольников).
Заметим также, что для любого ребра нашего графа хотя бы один из его концов принадлежит V1, ведь никакие две вершины из V0 не соединены ребром. Поэтому всего рёбер в графе R ≤ сумма rk по всем k из V1 ≤ сумма n0 по всем k из V1 = n0 · n1 ≤ (n0 + n1)² / 4 = n²/4 и теорема доказана.

Вернёмся теперь к исходной задаче. Легко построить пример, в котором каждая команда сыграла по крайней мере 10 матчей, но нет четырёх команд, попарно сыгравших между собой. Примером служит так называемый трёхдольный граф. Для этого разделим множество из 16 вершин графа (команд) на 3 примерно равные группы (5, 5 и 6 команд) и соединим ребрами вершины из разных групп и только их. В таком графе из каждой вершины выходит 10 или 11 рёбер и нет четырех вершин, попарно соединенных ребрами (иначе 2 вершины из этих четырех должны оказаться в одной группе, но тогда мы получаем противоречие, так как любые две вершины из одной группы не соединены ребром по построению). Докажем теперь, что если из каждой вершины выходит 11 или более рёбер, то найдутся четыре вершины, попарно соединенные рёбрами. Рассмотрим какую-нибудь вершину A нашего графа. Концы 11 рёбер, которые выходят из этой вершины, служат вершинами подграфа (две вершины этого подграфа соединены ребром тогда и только тогда, когда они соединены ребром в исходном графе). Из условия задачи получаем, что из каждой вершины подграфа выходит по крайней мере 11 – 5 = 6 рёбер, т.е. всего рёбер в подграфе не менее 6*11/2 = 33. Поэтому по теореме Турана в таком графе обязательно есть треугольник (три вершины B, C и D, попарно соединенных рёбрами), ведь если бы таких трех вершин не было, то в подграфе было бы не более 11²/4 < 33 рёбер. Итак, мы нашли четыре вершины A, B, C и D в исходном графе, которые попарно соединены рёбрами. Поэтому k не может быть больше 10. Ответ: k = 10.


Календарь

August 2018
S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 
Powered by LiveJournal.com
Designed by Tiffany Chow