Два пирата делят добычу, состоящую из двух мешков монет и алмаза, действуя по следующим правилам. Вначале первый пират забирает себе из любого мешка несколько монет и перекладывает из этого мешка в другой такое же количество монет. Затем также поступает второй пират (выбирая мешок, из которого он берет монеты, по своему усмотрению) и т.д. до тех пор, пока можно брать монеты по этим правилам. Пирату, взявшему монеты последним, достается алмаз. Кому достанется алмаз, если каждый из пиратов старается получить его? Дайте ответ в зависимости от первоначального количества монет в мешках.

   Решение

Тема:    [ Покрытия ]

Сложность: 6+ Классы: 8,9

Прислать комментарий

Условие

Докажите, что любые n точек на плоскости всегда можно накрыть несколькими непересекающимися кругами так, что сумма их диаметров меньше n и расстояние между любыми двумя из них больше 1.

Решение

Построим круги с центрами в данных точках радиуса a = 1/2 + 1/2n. Ясно, что пересекающиеся круги радиусов R₁ и R₂ можно заключить в круг радиуса не более R₁ + R₂. Будем так делать до тех пор, пока не получатся непересекающиеся круги. Все данные точки расположены на расстоянии не меньше a от границ этих кругов, поэтому их радиусы можно уменьшить на b < a, и при этом они по-прежнему будут покрывать все данные точки. Если кругов k штук, то сумма их диаметров не больше n ^. 2a - k ^. 2b2na - 2b. Нам нужно, чтобы выполнялись следующие условия: 2na - 2b < n и 2b > 1. Они выполняются, если a = 1/2 + 1/2n и b = 1/2 + 1/4n.

Источники и прецеденты использования