Software & Systems

Решение первой задачи [1] приписывается Полю Дираку (1902—1984). Знаменитый английский физик предсказал, оказывается, существование не только античастиц, но и антирыб, оригинально решив такую задачу:

Задача. Три рыбака легли спать, не разделив улова. Проснувшийся первым решил взять свою долю и уйти по-английски. Но число рыб не делилось на три, и для этого он выбросил одну, а от остатка забрал треть. Второй и третий сделали то же самое. Найти наименьшее число рыб, допускающее такую ситуацию.

Ответ, который дал П. Дирак, — минус две рыбы (две антирыбы). Выбрасываем одну, получаем минус три, забирая из них треть, оставляем минус две. Такое можно проделывать вновь и вновь.

Решение оригинальное, достойное гения Дирака, но, тем не менее, неверное. Это доказывается простой БЕЙСИК-программой 1, В нее заложен алгоритм научного тыка — задается начальное число рыб (строка 20), от которого отнимается по единице (строка 50) до тех пор (цикл «до» на строках 50-НЗО), пока не выполнится условие честного дележа улова. При начальном числе рыб, равном 30, например, компьютер выдаст (строка 140) «нормальный» ответ: 25 рыб. При начальном числе рыб, равном 20, предположим, мы получим «дираковский» ответ: -2 рыбы. Если воодушевиться этим ответом и пойти дальше, памятуя о том, что компьютер может «проглотить» даже самые

невероятные исходные данные, и задать начальное число рыб, равное минус трем, то ответ машины будет похлеще «дира-ковского»: -29. Но и это не предел, условию задачи (без слова «наименьшее») удовлетворяет бесконечный ряд исходных количеств рыб: ..., 79, 52, 25, -2, -29, -56, -83, ...

У этого ряда (назовем его рыбным рядом Дирака) есть симметрия относительно -2 и период, равный 27. Последний рыбак при этом должен будет забрать

..., 11,7,3, -1, -5, -9, -13, ...рыб.

Если бы рыбаков было не трое, а четверо, то перед отходом ко сну им нужно было бы выловить ..., 509, 253, -3, -259, -515, ... рыб (период 256). У пятерых рыбаков план улова был бы еще сложнее: ..., 6246, 3121, -4, -3129, -6254, ...рыб (период 3125).

Если очередной рыбак перед своим уходом не выбрасывал бы рыбу, а подлавливал, то в приведенных бесконечных рядах Дирака числа поменяли бы свой знак на противоположный.

 Итак, задача в приведенной формулировке решения не имеет. Чтобы ответ все-таки равнялся -2 рыбам (двум антирыбам), условие задачи нужно уточнить, а именно: «Найти наименьшее по абсолютному значению число рыб». Но тогда оно будет содержать подсказку, сводящую на нет всю заковырку задачи.

Алгоритм определения рыбного ряда Дирака, заложенный в программу 1, отнюдь не оптимальный. Намного проще и быстрее идти не от начального числа рыб, отнимая от него по единице, а от остатка, забираемого последним рыбаком, прибавляя к нему по единице. Но ... «иная простота хуже воровства». В этом случае антирыбы у нас вряд ли получились бы: Поль Дирак перешагнул нуль на числовой оси по своей гениальности, а компьютер, работающий по программе 1, — по своей наивности. Неполное решение задачи о рыбаках и рыбке Дираком можно объяснить, наверное, только тем, что у него не было компьютера.

Вторая задача о трехсторонней дуэли несколько «кровожадная», но тем не менее она часто приводится в книгах [2,3].

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

Описание такой необычной дуэли возьмем из [2]:

«Сэм, Билл и Джон договорились сразиться на дуэли втроем по следующим правилам: они тянут жребий, кому стрелять первому, кому — второму, а кому —: третьему; далее они располагаются на вершинах равностороннего треугольника; обмениваются выстрелами в порядке вытянутых номеров, пока двое не будут убиты; очередной стреляющий может стрелять в любого из остальных.

Сэм — снайпер и никогда не промахивается на данной дистанции. Билл поражает мишень в 80, а Джон в 50 случаях из 100. Какова наилучшая стратегия для каждого из участников и каковы их вероятности выживания, если они следуют оптимальным стратегиям?»

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

Джон может выбрать еще одну (третью, «хитрую») стратегию. Чтобы получить наивысшие шансы выйти победителем из дуэли, он должен нарушить дуэльный кодекс [4] и намеренно стрелять в воздух, пока живы оба его соперника. Ведь очередной стреляющий будет бить не в него, а в более меткого соперника (вторая стратегия). После того, как Сэм и Билл будут убиты, Джону нужно показать все, на что он способен. При такой стратегии у Джона шансы выжить составляют 50%, если он останется наедине с Сэмом, и еще выше, если с Биллом.

Во всех книгах, где описывается трехсторонняя дуэль, делается вывод о том, что «Джон, немного подумав, может гарантировать себе максимальные шансы на выживание в ситуации, которая на первый взгляд для него крайне невыгодна». Но это неверно. И при второй тактике, когда все бьют в самого меткого, у Джона наивысшие шансы выйти победителем из дуэли. Нарушение дуэльных правил (выстрел в воздух допустим только в том случае, если он последний) повышает шансы Джона только на несколько процентов.

Все это легко доказать с помощью компьютера. БЕЙСИК-программа 2 позволяет провести на машине статистические испытания (метод Монте-Карло) математической модели трехсторонней дуэли. В программе 2 задействовано пять одномерных массивов с индексом-номером дуэлянта: N — имя дуэлянта, М — его меткость (от 1 до 0); Т — номер стратегии, которой он придерживается (1, 2 или 3); Р — статус дуэлянта («Ж» — еще жив, «у» — уЖе убит); F — число побед дуэлянта в проведенных дуэлях. Генератор псевдослучайных чисел (встроенная функция БЕЙСИК, возвращающая вещественное число в интервале от 0 до 1) позволяет провести жеребьевку участников перед очередной дуэлью (строки 6 и 7), выбрать случайную цель (строка 8) и смоделировать выстрел с известной точностью попадания (строка 17).

После запуска программы 2 компьютер будет моделировать протекание одиночных дуэлей (строки 5—23, составляющие тело цикла с параметром), подсчитывать число побед каждого участника и выдавать на дисплей имя очередного победителя (строка 24). После окончания всех запланированных дуэлей на дисплее выдается искомая информация (строки 26 и 27).

Вот результат прогонки программы 2 при вышеописанных условиях (меткость Сэма равна 1, Билла — 0.8, Джона — 0.5; Сэм и Билл стреляют в самого меткого, а Джон придерживается «хитрой» тактики):

ВЕРОЯТНОСТЬ ВЫЖИВАНИЯ В 10000 ДУЭЛЯХ СЭМ 36.43% (30) БИЛЛ 17.8% (17.777...) ДЖОН 51.77% (52.2222 ...)

В скобках указаны цифры, полученные при решении задачи методами теории вероятностей [2].

С помощью программы 2 можно показать, что в одиночных дуэлях шансы Сэма и Билла существенно меняются в зависимости от того, кому Джон при намеренном промахе уступает свой выстрел. Если Биллу (С=-1, строка 7), то вероятности выживания будут примерно такими:

СЭМ 22.94% БИЛЛ 24.44% ДЖОН 52.62%

Если Джон уступает свой выстрел Сэму, то у Билла дела становятся совсем плохи:

СЭМ 36.82% БИЛЛ 11.81% ДЖОН 51.37%

Если Джон не будет хитрить, то и в этом случае шансы на его выживание останутся достаточно высокими — примерно 45%.

В вышеприведенных выкладках слово «примерно» подчеркивает зависимость метода Монте-Карло от качества генератора псевдослучайных чисел и от числа проведенных дуэлей.

Программу 2 при желании можно развить в следующих направлениях:

Необходимо предусмотреть возможность проведения статистических испытаний при числе дуэлянтов больше трех. Для этого необходимо запрограммировать перестановку местами дуэлянтов перед очередной дуэлью. При трех дуэлянтах это достигается изменением знака переменной С (строка 7). Многосторонняя дуэль получится, например, когда директор завода начнет кивать на смежников, поставляющих бракованные чипы, или на разработчиков, давших негодный проект машины. Разработчики в свою очередь сошлются на министерство, а оно на Госплан и т. д. Так что трехсторонней дуэлью тут никак не обойтись.

Не исключается возможность сговора дуэлянтов. Ведь Сэм (директор завода) и Билл (Госприемка) могут для повышения своих шансов на выживание договориться стрелять не в самого меткого, а в самого хитрого, т. е. в Джона (потребитель).

Список литературы

1.     Позиция 28 по горизонтали кроссворда с фрагментами. Наука и жизнь, № 10, 1984.

2.     Гудман С, Хидетниеми С. Введение в анализ и разработку алгоритмов / Пер. с англ. — М.: Мир, 1981.

3.     Мостлер Ф. 50 занимательных вероятностных задач с решениями/ Пер. с англ. — М.: Наука, 1985.

4.     Лотман Ю. М. Роман А. С. Пушкина «Евгений Онегин». Комментарии. — Л.: Просвещение, Ленингр. отд-ние, 1983.