Гангстерские войны

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеСпециалист по математике (разработчик контента для дистанционной системы обучения)31.03.2020 11:52
ОбъявлениеМатематик-алгоритмист (Vehicle Routing Problem) – удаленная работа03.06.2020 17:58
26.07.2020 01:16
Гангстерские войны
Условие

N гангстеров расположены на плоскости таким образом, что все попарные расстояния между ними различны.
В некоторый момент времени они одновременно стреляют - каждый в ближайшего к нему.
При каких N можно гарантировать, что, хотя бы один из гангстеров останется в живых?



Два гангстера, расстояние между которыми наименьшее, выстрелят друг в друга




Ответ: При нечетном N можно гарантировать, что, хотя бы один из гангстеров останется в живых; при четном N всегда существует расстановка, при которой все гангстеры перестреляют друг друга.

Рассмотрим двух гангстеров, расстояние между которыми наименьшее.
Очевидно, что они выстрелят друг в друга.
Предположим, что существует третий гангстер, стреляющий в одного из этих двоих.
Тогда имеем (N – 2) гангстера, в которых попало не более, чем (N – 3) выстрела – то есть хотя бы один из гангстеров останется в живых.
Если будем считать, что больше никто в первых двух не стрелял, то мы можем исключить этих двух гангстеров из рассмотрения.
Получаем точно такую же ситуацию, но число гангстеров уменьшилось на 2.
Опять же рассмотрим двух гангстеров, расстояние между которыми наименьшее и т.д.
При нечетном N в конце останется один гангстер, в которого никто не стрелял.
Наконец, при четном N всегда существует следующая расстановка: все гангстеры разбиты на пары с небольшим расстоянием в паре и большими расстояниями между парами (иллюстрация см. рисунок).

При этой расстановке все гангстеры перестреляют друг друга


Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти