Олимпиадная задача: дуэль двух магов и стратегия победы (теория алгоритмов, 10-11 класс)
Задача
Два мага сражаются друг с другом. Вначале они оба парят над морем на высоте 100 метров. Маги по очереди применяют заклинания вида "уменьшить высоту парения над морем на a метров у себя и на b метров у соперника", где a, b – действительные числа, 0 < a < b. Набор заклинаний у магов один и тот же, их можно использовать в любом порядке и неоднократно. Маг выигрывает дуэль, если после чьего-либо хода его высота над морем будет положительна, а у соперника – нет. Существует ли такой набор заклинаний, что второй маг может гарантированно выиграть (как бы ни действовал первый), если при этом число заклинаний в наборе
а) конечно; б) бесконечно?
Решение
а) Пусть первый маг всегда применяет заклинание с наибольшей разностью b – a. Тогда после ответного хода разность высот первого и второго как минимум 0. В результате после нескольких ходов разность всегда неотрицательна и, значит, второй не выигрывает.б) Рассмотрим произвольную убывающую последовательность положительных чисел {an}, где an < 50, и пусть в n-м заклинании a = an, b = 100 – an. Ответив на n-е заклинание заклинанием с номером m > n, второй выиграет: высота первого станет равной am – an < 0, а высота второго an – am > 0.
Ответ
a) Не существует; б) существует.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь