Перестрелка

На поле стояли 777 гангстеров, и все они находились на разных расстояниях друг от друга. Гангстеры одновременно выхватили пистолеты и каждый выстрелил в ближайшего. Докажите, что хотя бы в одного гангстера никто не стрелял.

Ответ: Очевидно, пары возможны.
Докажем, что невозможны замкнутые цепочки (последний стреляет в первого) с количеством более 2. Представим цепочку где 1 стреляет в 2, 2 - в 3 и т.д. ... , n+1 стреляет в n, а n - в 1. И пусть n>2. По условию, расстояния должны все время убывать: 1-2 > 2-3 > .... > (n-1)-n > n-1 > 1-2. Что невозможно в случае строгих неравенств.
Дальше - все верно: только пары приводят к полному взаимоубийству, а в нечетном случае это невозможно.

 

Обсуждение задачи на форуме - Перестрелка

Ваша оценка: Нет Средняя: 3.3 (86 оценки)


Комментарии

Зачем такое сложное объяснение? Просто отсортируем гангстеров по расстоянию до ближайшего к нему гангстера. В последнего никто не стрелял.

Фсе это фигня, у этой задачи слишком много решений:
1) гангстеры - из мира CS6 и допустим умирают от одного выстрела, тогда, в связи с тем что одновременно там выстрелить не возможно то некоторые боты (гангстеры) не сумеют выстрелить и вместо 777 выстрелов прозвучит гораздо меньше.
Значит, чтобы остался к примеру 1 бот - остальным нужно выстрелить еще несколько раз.
2) если брать реальную жизнь, то здесь действительно все гангстеры могут выстрелить одновременно, но беда в том что несколько из них могут выстрелить в одном направлении (в одного и того же человека). + умирая каждый из них - если его только ранили может захватить с собой на тот свет несколько других.
Также нужно не забывать, что пуля может прошить 2 человек подряд.

Отсюда следует, что в первом варианте - если это будут боты (в упрощенном и логичном мире), то останется много живых, а если это будет происходить в реальном мире, то все могут погибнуть и с менее чем 777 выстрелов, так и остаться в живых или раненных тоже могут практически все, все зависит от оружия и снайперской подготовки стрелков...

чё париться один убежал вот и всё или как в особо опасен один выстрелит и всех убьёт

вообще-то в задаче четко сказано, что каждый выстрелил один раз и все одновременно
и нас вообще не интересует кто-то там умер, в кого попали и как изменились их взаимоотношения после этого. важно только В КОГО (прицельно)стреляли

тут только не объясняется ПОЧЕМУ в последнего не стреляли?
допустим вся толпа стоит на площади 1000 кв м., не подпуская к себе никого на расстояние вытянутой руки, а двое - в стороне на расстоянии 100 м. от края этой площади и на расстоянии 5 см друг от друга. следовательно отсортировав, последним получим одного из этих двоих, но эти двое, очевидно, стреляли в друг друга, т.к. были ближайшими друг к другу. Следовательно сортировка ничего не дает.

Решение:

Для каждого i-го гангстера среди всех расстояний до других гангстеров существует минимальное - назовем его min(i).
Среди всех i от 1 до 777 существует максимальное min(i) - обозначим его max{min(i)}.

Если это max{min(i)} является минимальным только для одного гангстера, то он и есть тот, в которого никто не стрелял, т.к. для всех остальных есть сосед с меньшим min(i).

Если же это max{min(i)} является минимальным для двух гангстеров (для большего количества это невозможно в силу того, что все расстояния попарно различны), то эти гангстеры стреляют в друг друга. При этом в них никто больше не стреляет, т.к. для всех остальных есть сосед с меньшим min(i). Такую самозамкнутую пару можно отбросить из рассмотрения и повторить все рассмотрение для 775 гангстеров.

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

Среди этих 3-х, очевидно, существует только один гангстер с max{min(i)} (оставшаяся пара имеет min{min(i)} и стреляет в друг друга). Этот оставшийся нам и нужен - в него никто не стреляет.

если они стояли цепочкой в кольцо с увеличивающимся растоянием в 1 мм. То последний убивает первого и все мертвы.Если стреляют одновременно.