Пятнадцать человек на сундук мертвеца

Квант 2016, №1 с. 10, 11, 12, 13, 14, 15, 18, 20 Тег 9GJZ

С.ГРИБОК, К.КНОП

ВСЕ ЗАДАЧИ, О КОТОРЫХ МЫ СОБИРАЕМСЯ ВАМ рассказать, связаны общим сюжетом: команда пиратов хочет поделить золотые монеты. Но прежде чем приступить к рассказу, мы должны поближе познакомиться с пиратской логикой и ее законами. i Ни при каких обстоятельствах ни один из пиратов не желает очутиться за бортом корабля. i Пираты очень любят золото. Каждый из них действует так, чтобы получить как можно больше монет в результате дележа. i Ни один из пиратов никогда не вступит в сговор с другим пиратом, чтобы сообща обыграть остальных. «Каждый сам за себя» – правило, которому следует каждый пират. i Каждый пират в совершенстве владеет логикой, и все его действия логически обоснованы. i Все предпочтения, законы и правила пиратов (включая и это правило) известны и самим пиратам. Итак…

Задача 1

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

Пятнадцать пиратов с брига «Арабелла» – капитан, 13 матросов и юнга – нашли клад: сундук, в котором лежало 100 одинаковых золотых монет. Чтобы поделить деньги, пираты использовали такую процедуру: 1. Капитан, как самый старший, предлагает свой план дележа клада. 2. Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».

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

Бриг «Арабелла»

Если все пираты проголосовали «за», то план принимается и деньги делятся по плану. Если же хотя бы один из пиратов проголосовал против, то старшего пирата бросают за борт. После этого следующий по старшинству пират вносит свой план, пираты снова голосуют и так далее, пока, наконец, план одного из пиратов не будет принят. Еще одна особенность пиратов «Арабеллы» – их природная доброта. Если решение пирата голосовать «за» или «против» никак не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то каждый пират по доброте душевной всегда проголосует «за». Как будут поделены деньги, если пираты будут использовать данный метод дележа? Чей план будет принят? Решение. Нетрудно сообразить, что у юнги есть простой способ добиться того, чтобы все монеты достались ему. Он должен голосовать против любого другого плана до тех пор, пока либо один из пиратов не предложит ему все деньги, либо все пираты, кроме юнги, не окажутся за бортом. Понимая это и желая сохранить свою жизнь, капитан сам предложит юнге все деньги. Юнга согласится на этот план по доброте душевной: если деньги и так его, зачем же голосовать против и губить капитана. Остальные пираты также проголосуют «за», так как им все равно никаких денег не светит. Во всех следующих задачах мы используем для решения «обратный ход», т.е. рассуждения «с конца». Поэтому предлагаем читателям потренировать умение так рассуждать на более простых сюжетах.

КВАНТ 2016/№1

Упражнения

Капитан делил добычу между пиратами. Сначала он взял себе 1/16 всех монет и еще одну монету. Второму пирату он дал 1/16 оставшихся монет и еще две и т.д. Пятнадцатому (юнге) он дал 1/16 оставшихся монет и еще 15 монет. Оказалось, что все получили поровну и все монеты розданы. Сколько всего было монет?

Боишься – всадим в бок перо мы? Так отвечай, черт побери, Как разделить две пинты рома На три? А.Чернин

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

Теперь расскажем о том, как делила клад другая команда пиратов со шлюпа «Бестия».

Задача 2

– Если эта скотина решил изменить своему слову, вы думаете, он остановится на полпути? Как только мы согласимся на одну десятую, так, будьте спокойны, он тут же найдет предлог, чтобы вовсе ничего нам не дать. Р.Сабатини. Хроника капитана Блада

Пираты на «Бестии» использовали другой метод дележа: 1. Самый старший пират рассказывает план остальным. 2. Все пираты голосуют, следует ли принять план старшего. Каждый из пиратов голосует либо «за», либо «против». 3. Если не менее половины пиратов проголосовали «за», то план принимается, и деньги делятся по плану. Если же большинство пиратов проголосовало против, то старшего пирата бросают за борт. После этого следующий по старшинству пират излагает свой план, пираты снова голосуют и так далее, пока, наконец, план одного из пиратов не будет принят. Пираты «Бестии» – такие же добродушные ребята, как и их коллеги с «Арабеллы». Если решение пирата голосовать «за» или «против» не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то каждый пират всегда голосует «за». Как 15 пиратов со шлюпа «Бестия» поделят 100 монет? Ответ: старший пират заберет себе все деньги. Решение. Итак, «начнем с конца», т.е. поставим себя на место последнего из пиратов, в предположении, что до него дошла очередь. Пусть 14 планов уже отвергнуто. Тогда юнга остался один, и он забирает все монеты:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 100

Теперь, когда мы разобрались, как поступит юнга, можно мысленно вернуться на шаг назад. Пусть 13

планов отвергнуто. 14-й пират проголосует за любой свой план, и ему этого голоса уже достаточно. Поэтому он может не делиться с юнгой и просто забрать себе все монеты:

0 0 0 0 0 0 0 0 0 0 0 0 0 100 0

Сделаем еще один шаг назад. Как будет рассуждать 13-й пират? Чтобы остаться в живых, ему нужно два голоса из трех. 14-й в любом случае будет против, значит, поддержку можно ждать только от юнги. Но юнге 14-й не оставит ничего, поэтому даже если ему ничего не дать, то миролюбивый юнга все равно проголосует «за». Таким образом, план 13-го пирата

0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 проходит двумя голосами (13-го, 15-го) против одного. Следующему пирату (12-му) тоже достаточно двух голосов, и при этом голоса 14-го и 15-го (которые от 13- го ничего не получат) у него уже в кармане. А так как больше не нужно, то он тоже забирает все себе: 0 0 0 0 0 0 0 0 0 0 0 100 0 0 0 Продолжая рассуждать аналогично, получаем, что первый пират также при любом своем плане может рассчитывать на голоса всех остальных пиратов, кроме второго. А так как ему хочется заполучить больше денег, то его план будет самым жадным из возможных: 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Упражнение 3. Как изменится дележ монет на «Бестии», если пираты изменят правило 3: план будет считаться принятым, если все пираты, кроме, быть может, одного, проголосовали «за»?

Задача 3

– Мы послали за тобой, капитан Пайк, потому как у нас теперь один, как говорится, общий интерес – вот эти ценности. Их надо поделить поскорее, без лишней проволочки, и тогда каждый из нас может отправляться, куда кому надобно. Р.Сабатини. Хроника капитана Блада

Пираты с фрегата «Валькирия» отличаются от пиратов «Бестии» отсутствием доброты: если решение пирата голосовать «за» или «против» никак не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то в пирате просыпается его жестокая бабушка с отцовской стороны, и он голосует «против». А в качестве алгоритма дележа на «Валькирии» используются правила, описанные в упражнении 3: 1. Самый старший пират рассказывает остальным свой план. 2. Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против». 3. Если все пираты, кроме, быть может, одного, проголосовали «за», то план принимается, и деньги делятся по плану. Если же хотя бы двое из пиратов проголосовали против, то старшего пирата бросают за борт. После этого план предлагает следующий по старшинству, пираты снова голосуют и так далее, пока план одного из пиратов не будет принят.

ПЯТНАДЦАТЬ

ЧЕЛОВЕК

НА

СУНДУК

МЕРТВЕЦА

Задача 4

Был однажды богатой добычи дележ – И пиpаты бесились и выли… Юнга вдpуг побледнел и схватился за нож, Потому что его обделили. В.Высоцкий. Был развеселый розовый восход…

Фрегат «Валькирия»

Как 15 пиратов с «Валькирии» поделят 100 монет? Ответ: 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Решение. Снова начнем рассуждать за пиратов с конца. 14-й (второй с конца) пират может не беспокоиться за свою жизнь и за судьбу своего плана: что бы он ни предложил, «все кроме одного» – это и есть он сам. Поэтому он может забрать себе все монеты: 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 13-му (третьему с конца) пирату уже нужно заручиться поддержкой хотя бы одного из двух последних. Чьей? Ясно, что не 14-го: тому в случае провала плана 13-го светит перспектива получить все. Значит, нужна поддержка юнги. Чтобы ее получить, достаточно предложить ему больше 0, т.е. 1 монету. Итак, он предлагает

0 0 0 0 0 0 0 0 0 0 0 0 99 0 1 и вместе с юнгой голосует «за». 12-му пирату, понимающему этот расклад, приходится игнорировать жадного 13-го и задабривать всех следующих, предлагая им больше, чем даст им 13-й. Таким образом, самое большее, на что он может рассчитывать, это

0 0 0 0 0 0 0 0 0 0 0 97 0 1 2

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

9 0 1 2 3 4 5 6 7 8 9 10 11 12 13

Упражнение 4. а) Как 15 этих пиратов поделят 20 монет? б) Как N пиратов с «Валькирии» разделят K монет?

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

Один из пиратов, бывший в те славные времена юнгой на «Валькирии», спустя много лет после описываемых событий хвастался, что сумел забрать себе весь клад. – Тысяча чертей! Этот скряга капитан предложил мне всего 13 монет. Тут я вижу, что шкипер голосует против, и тоже проголосовал против! И пока все на меня выпучились, шкипер уже успел выкинуть капитана за борт. А после этого, как ни в чем не бывало, шкипер предложил мне всего 12! Ну, я еще раз проголосовал против – и наш бывший шкипер тут же улетел за борт к бывшему капитану. И вот тут до следующего стало что-то доходить… Тысяча чертей! Он раз пять подряд начинал что-то говорить и каждый раз, не доведя предложение до точки, смотрел на меня и сбивался… В конце концов он предложил отдать все мне. Мне, безусому юнге! А все остальные пираты, постоянно косясь на меня, проголосовали «за». Конечно, после этого я не мог уже ни минуты находиться на нашем фрегате, поэтому отвязал капитанскую шлюпку, погрузил в нее сундук и немедленно отчалил. Докажите, что этот рассказ юнги немножко не соответствует истине. Решение. Эта история – прекрасная иллюстрация того, в чем идеальный мир математических задач отличается от реальной жизни. На настоящих пиратских кораблях, безусловно, и не такие вещи случались, но в наших задачах изначально оговорена безупречность пиратской логики. Как мы увидим, это не оставляет никакого места для шантажа, а поэтому у пиратов «Валькирии» (начиная с капитана) не было никаких причин опасаться строптивого юнги. Действительно, если (ну а вдруг!) очередь выдвигать план дойдет до второго с конца пирата, то он ничем не рискует, потому что кроме него остался только юнга. Следовательно, в этом случае юнга ничего не получит. Поэтому ему нечем шантажировать третьего с конца пирата в тот момент, когда тот вносит свой план. Юнга будет просто вынужден проголосовать за любой его план, если только тот предложит юнге хотя бы одну монетку. Более того, третий с конца пират тоже это прекрасно понимает, поэтому ровно столько он юнге и даст. Но, собственно, у него и не будет такой возможности, потому что ровно так же понимают невозможность шантажа (а значит, и отсутствие нужды его бояться) и все предыдущие пираты. Поэтому все будет происходить именно так, как описано в решении предыдущей задачи, а не так, как пытался рассказать бывший юнга.

Наша серия пиратских баек была бы неполной, если бы мы не рассказали историю пиратов со шхуны «Горгона».

КВАНТ 2016/№1

Задача 5

– Они не будут проверять ваши книги, тем более что мало кто из моих людей вообще умеет читать. Но им хорошо известно – вы заставляете меня быть резким, – что ваши подсчеты фальшивые. Р.Сабатини. Одиссея капитана Блада

Все пираты на шхуне «Горгона» такие же жестокие, как и на «Валькирии», а для дележа используют тот же метод, что и команда шлюпа «Бестия»: 1. Самый старший пират излагает свой план дележа. 2. Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».

голосов, и дешевле всего покупается голос 14-го пирата. Для этого достаточно отдать ему всего одну монету, потому что от 13-го он не получит ничего: 0 0 0 0 0 0 0 0 0 0 0 99 0 1 0 Продолжая рассуждать аналогично, получаем, что старшему пирату достаточно поделиться монетами с семью другими – третьим, пятым, …, пятнадцатым. В этом случае все они проголосуют за его план, и никому не придется оказываться за бортом. Таким образом, окончательный дележ монет – 93 0 1 0 1 0 1 0 1 0 1 0 1 0 1 б) Ответ: план 94-го пирата, считая с конца (7-го с начала). Решение. Когда есть всего 15 монет, то вплоть до 32 пиратов работает логика из пункта а). Старший из 32 пиратов не получает ничего, но делится 15 монетами с другими и на этом (вместе со своим голосом) набирает необходимые ему 16 голосов:

0 0 1 0 1 0 … 1 0 1 0

Шхуна «Горгона»

Если не менее половины пиратов проголосовали «за», то план принимается, и деньги делятся так, как было предложено. Если же большинство пиратов проголосовали против, то старшего пирата бросают за борт. После этого следующий по старшинству пират вносит новый план, оставшиеся пираты снова голосуют и так далее, пока, наконец план одного из пиратов не будет принят. а) Как 15 пиратов «Горгоны» поделят 100 монет? б) Чей план будет принят, если 100 пиратам со шхуны «Горгона» нужно разделить 15 монет? а) Ответ: 93 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Решение. Как обычно, начнем разбирать задачу с конца. Пусть 13 планов уже отвергнуто, как рассуждает второй с конца пират? Его голос составляет не менее половины от оставшихся голосов, так что он может вообще не делиться с юнгой. Поэтому он просто забирает себе все монеты: 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 Сделаем шаг назад. Как будет рассуждать 13-й пират? Чтобы остаться в живых, ему нужны два голоса из трех. 14-й в любом случае будет против, значит, поддержку можно ждать только от юнги. Чтобы ее получить, юнге достаточно дать больше, чем он получит от 14-го. Значит, юнге можно оставить одну монету, а все остальное забрать себе:

0 0 0 0 0 0 0 0 0 0 0 0 99 0 1

Следующему пирату (12-му) тоже достаточно двух

Попробуем разобраться с 33 пиратами. Монет всего 15, а чтобы выжить, старший пират должен «купить» 16 чужих голосов. Ему не имеет смысла давать что-то тем 15-ти, кто при 32 пиратах получит деньги, значит, он должен делить 15 монет между собой и 17-ю остальными. Но так как хотя бы двоим из 17 он не сможет дать ничего, то эти свирепые пираты безусловно проголосуют против его плана. Таким образом, 33- го пирата ждет смерть за бортом. Положение 34-го пирата явно лучше, потому что у него есть в запасе не только свой голос, но и голос 33- го, которому, несомненно, хочется, чтоб план 34-го прошел, иначе ему самому несдобровать. Еще пятнадцать голосов он сможет купить, предложив по монете любым 15 из тех 17, которые останутся без денег при голосовании по плану 32-го. Этот момент мы отразим с помощью специального значка – звездочки. Звездочка означает, что пират может получить деньги, но может и не получить. При этом 15 из отмеченных звездочкой получат по монете, а остальные двое – нет. Итак, при 34 пиратах план старшего принимается, и монеты делятся так:

0 0 * * 0 * 0 * … 0 *

35-му, как и 33-му, придется нырять за борт: ни одного чужого голоса «бесплатно» у него нет, а купить он может только 15 из необходимых ему 17. 36-му чуть легче, но не сильно: за его предложение бесплатно проголосует 35-й, но ему нужно 18 голосов, а удастся купить только 15, итого наберется 17, поэтому и его участь тоже печальна. По аналогичной причине убивают и 37-го. Зато 38-му удается выжить: он сам, а также 37-й, 36-й и 35-й голосуют «за», а еще 15 голосов он покупает монетами, например, у тех, кто от 34-го точно ничего не получал. (Можно было бы покупать голоса и у пиратов, которые отмечены звездочками, предполагая, что каждый из них предпочтет гарантированную монету в настоящий момент вместо «звездочки» – не

ПЯТНАДЦАТЬ

ЧЕЛОВЕК

гарантированной монеты в одном из следующих планов.) Итого он имеет 19 голосов. Следующие несколько пиратов также не выживают, а шанс на выживание появляется только у 46-го: за его план проголосуют все смертники, начиная с 39-го (итого 8) и еще 15 купленных за деньги из последних 38, в итоге он получит нужные ему 23 голоса. По индукции несложно доказать, что выживают пираты с номерами (считая от конца) $30 + 2^{k}$ . А вот однозначно установить распределение денег при этом невозможно, потому что у каждого из пиратов есть достаточно свободный выбор, кому именно он предложит деньги.

НА

СУНДУК

МЕРТВЕЦА

Решение. Как обычно, начнем разбирать задачу с конца. Пусть 14 планов уже отвергнуты. Тогда все монеты уже практически в кармане у юнги. Ему достаточно выдвинуть любой план, за который не проголосуют остальные пираты (например, предложить оставить все деньги самому себе). После того как этот план будет отвергнут, юнга получит все монеты:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 100

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

Вернемся теперь на шаг назад. Пусть 13 планов отвергнуты. Как должен рассуждать 14-й пират? Он не может допустить, чтобы его план был отвергнут, так как в этом случае все монеты заберет юнга. Значит, ему нужен план, за который проголосуют 14 пиратов из 15. Юнга будет голосовать против любого его плана, следовательно, 14-му нужно, чтобы его план поддержали все остальные. Для этого он должен выделить по монете каждому из пиратов, кроме юнги. На это потребуется 13 монет. Оставшиеся 87 монет 14-й пират заберет себе:

Задача 6

1 1 1 1 1 1 1 1 1 1 1 1 1 87 0

Что ж, если в Портленд нет возврата, Поделим золото, как братья. Б.Окуджава. Пиратская лирическая

Пираты с корвета «Даная» были такими же жестокими, как на «Горгоне» и «Валькирии», но придумали новый способ дележа монет, который позволяет пиратам оставаться на борту и претендовать на часть добычи даже после того, как их план не будет принят. 1. Самый старший пират излагает свой план дележа. 2. Все пираты голосуют «за» либо «против». 3. Если все пираты, кроме, быть может, одного, проголосовали «за», то план принимается, и деньги делятся так, как было предложено. Если же хотя бы двое из пиратов проголосовали «против», то план не принимается, и голосование продолжается. Следующий по старшинству пират предлагает свой план, пираты снова голосуют и так далее, пока план одного из пиратов не будет принят. Если ни один из планов не пройдет, то все деньги получит юнга. Как 15 пиратов «Данаи» поделят 100 монет? Ответ: 11 11 11 12 0 1 2 3 4 5 6 7 8 9 10

Сделаем еще один шаг назад. Пусть отвергнуты 12 планов. Как будет рассуждать 13-й пират? Если его план будет отвергнут, то 14-й пират даст ему одну монету. Но одной монеты ему маловато, поэтому он не должен этого допустить. Для этого по крайней мере 14 пиратам (включая себя) он должен дать больше монет, чем дал бы им 14-й. Таким образом, пиратам с номерами с 1 по 12 нужно дать по 2 монеты, а одну монету дать юнге. Остальные 75 монет 13-й пират оставит себе:

2 2 2 2 2 2 2 2 2 2 2 2 75 0 1

Аналогично рассуждает и 12-й пират. 13-му он не дает ничего, остальным же дает на одну монету больше, чем они смогли бы получить от 13-го. Следовательно, пиратам с номерами с 1 по 11 достанется по 3 монеты, 14-му пирату – одна, а 15-му – две. Остальные 64 монеты можно оставить себе:

3 3 3 3 3 3 3 3 3 3 3 64 0 1 2

Можно было бы продолжать в том же духе и выписать планы остальных пиратов. Но общая закономерность уже очевидна. Пират с номером X отдает каждому из пиратов с меньшими номерами по 15 – X монет, каждому пирату с большим номером Y он отдает Y – X – 1 монету, а остальные монеты забирает себе. Таким образом, прибыль пирата с номером X составляет

100 - ( X - 1 ) ( 15 - X ) - ( 15 - X ) ( 14 - X ) 2 монет. Раскрыв скобки, получим следующее выражение для прибыли пирата с номером X:

$X^{2} 2 - 3 X 2 + 10$ .

Прибыль должна быть больше, чем число монет, которое пирату с номером X на следующем шаге выделит пират с номером X + 1, иначе свой собственный план не принесет пирату с номером X никакой выгоды. Таким образом, справедливо неравенство:

Корвет «Даная»

$X^{2} 2 - 3 X 2 + 10 > 14 - X$ .

КВАНТ 2016/№1

Упрощая, получим

$X^{2} - X > 8$ . Наименьшее натуральное X, при котором неравенство выполняется, равно 4. Следовательно, будет принят план 4-го пирата:

11 11 11 12 0 1 2 3 4 5 6 7 8 9 10

Поскольку пираты «Данаи» жестокие, то каждый из них будет голосовать против любого плана, в котором он получает не больше, чем может получить от 4-го. Какой бы план ни предлагал 3-й пират, он может «отобрать» деньги только у одного из остальных, а распределить их должен между всеми остальными (иначе получит хотя бы двоих обиженных, и его план будет провален). Но отобрать он может только 12 монет, которые при любом дележе на 14 приведут к тому, что кто-то монет не получит. Поэтому никакой план 3-го не будет принят, даже если он предложит тот план, который потом предложит 4-й (потому что все жестокие, и если денег при «за» и «против» будет одинаково, то голосуют «против»)! Аналогично не будут приняты никакие планы первых двоих пиратов.

Заметим, что доверие пиратов к демократическим механизмам принятия решений тоже не такое абсолютное, как вам могло показаться…

Задача 7

Истерлинг надул щеки и сделал широкий жест своей огромной лапищей. – А какую дележку предлагаете вы? – Мы должны это обсудить. Но, во всяком случае, наша доля не может быть меньше одной пятой. Р.Сабатини. Хроника капитана Блада

На бригантине «Ехидна» только капитан и шкипер имеют право предлагать планы дележа монет. Все остальные пираты могут лишь голосовать. Таким образом, алгоритм дележа выглядит так: 1. Шкипер рассказывает всем остальным свой план дележа монет. 2. Затем капитан рассказывает всем свой план дележа монет. 3. Все пираты (включая капитана и шкипера) голосуют либо за первый, либо за второй план. 4. Монеты делятся в соответствии с планом, набравшим больше голосов. Известно, что если оба плана сулят пирату равное число монет, он проголосует за первый план. Как 15 пиратов (капитан, шкипер и 13 матросов) с «Ехидны» поделят 63 монеты? Ответ: 49 8 1 1 1 1 1 1 0 0 0 0 0 0 0 Решение. Как всегда, начнем разбираться с задачей с конца. Прежде всего установим оптимальную стратегию капитана. Рассмотрим группу из 14 пиратов, исключая капитана. Разделим их на такие две группы А и Б по 7 пиратов, что каждому из пиратов группы А шкипер предложил не меньше монет, чем любому пирату из группы Б. Нетрудно убедиться в том, что оптимальная стратегия капитана заключается в том,

Бригантина «Ехидна»

чтобы забрать все деньги у 7 «богатых» пиратов группы А, выделить из этих денег по одной монетке каждому из 7 «бедных» пиратов группы Б, а все прочие монеты забрать себе. В этом случае за план капитана проголосуют все пираты группы Б и сам капитан. Пираты группы А проголосуют против, но они окажутся в меньшинстве. Конечно, эта стратегия применима лишь в том случае, если у пиратов группы А есть по крайней мере 8 монет. В противном случае капитан не сможет выделить по монете каждому из 7 пиратов группы Б и при этом оставить хотя бы одну монету себе, и ему будет выгоднее соглашаться с планом шкипера. Теперь займемся анализом стратегий шкипера. У него есть два возможных варианта действий. Первый – поставить капитана в ситуацию, когда он будет вынужден согласиться с планом шкипера. Для этого, как мы выяснили, достаточно, чтобы у 7 пиратов, которым шкипер предложил наибольшее число монет, в сумме набралось не более 7 монет. Делиться с другими пиратами не в интересах шкипера, поэтому он просто может взять 7 монет себе, а остальные монеты отдать капитану. Капитан выдвинет какой-нибудь план, за который не будут голосовать остальные (например, оставить все деньги себе), после чего большинством голосов будет принят план шкипера: 56 7 0 0 0 0 0 0 0 0 0 0 0 0 0 Вторая возможная стратегия для шкипера – позволить капитану выдвинуть план, который наберет большинство голосов, но при этом сам шкипер окажется среди тех семи пиратов, которым капитан даст по дополнительной монете (другими словами, войдет в группу Б). Для этого шкипер должен пообещать 7 пиратам (которые войдут в группу А) больше монет, чем самому себе. Оставшимся 6 пиратам, которые составят шкиперу компанию в группе Б, можно ничего не предлагать. Таким образом, план шкипера выглядит так: 0 7 0 0 0 0 0 0 8 8 8 8 8 8 8 Капитан даст шкиперу и другим 6 пиратам по одной дополнительной монете, а остальные монеты заберет себе: 49 8 1 1 1 1 1 1 0 0 0 0 0 0 0

ПЯТНАДЦАТЬ

ЧЕЛОВЕК

Итак, первая стратегия принесет шкиперу 7 монет, тогда как вторая позволит получить 8 монет. Таким образом, шкипер предпочтет вторую стратегию.

Задача 8

В Кейптаунском порту С пробоиной в борту «Жанетта» поправляла такелаж. П.Гандельман. В Кейптаунском порту

На барке «Жанетта», как и на «Ехидне», матросы не имеют права выдвигать планы. Это могут делать лишь старшие пираты. Алгоритм дележа такой: 1. Первый пират рассказывает свой план дележа. 2. Второй пират рассказывает свой план – «альтернативу». 3. План и альтернатива сравниваются. Если план дает хотя бы двум пиратам не меньше монет, чем альтернатива, то альтернатива отвергается. Если же альтернатива дает больше денег всем пиратам, кроме быть может одного, то план отвергается, а альтернатива становится планом. Затем следующий пират озвучивает новую альтернативу и так далее. 4. После того как все старшие пираты высказались, монеты делятся по плану. 5 старших пиратов и 10 матросов с «Жанетты» делят 105 монет. Как первый пират сможет получить 14 монет?

Барк «Жанетта»

Решение. Правила в этой задаче кажутся довольно запутанными, однако можно заметить следующее: если какой-то план обещает одному из пиратов 14 монет, а каждому из остальных пиратов не более чем по 13 монет, то существует лишь одна альтернатива, способная заменить этот план (т.е. лучшая, чем план, для всех пиратов, кроме одного): забрать все деньги у обладателя 14 монет и разделить их по одной между остальными. Теперь рассмотрим план 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14. Единственная лучшая альтернатива к нему 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0. Легко видеть, что это тот же план, циклически сдвинутый на одну позицию. Чтобы извлечь выгоду из этого свойства, первый пират выдвигает такой план:

10 9 8 7 6 5 4 3 2 1 0 14 13 12 11

НА

СУНДУК

МЕРТВЕЦА

Таким образом, он оставляет себе 10 монет, а остальным старшим пиратам предлагает 9, 8, 7 и 6 монет соответственно. Последовательность альтернатив, каждая из которых лучше предыдущей и заменяет ее, строится единственным способом: 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12

12 11 10 9 8 7 6 5 4 3 2 1 0 14 13

13 12 11 10 9 8 7 6 5 4 3 2 1 0 14

14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Нетрудно убедиться в том, что доли каждого из пяти старших пиратов растут. Таким образом, каждый из них заинтересован в том, чтобы выдвинуть одну за другой эти 4 альтернативы. Итоговым планом станет последняя из них. Таким образом, первый пират станет богаче на 14 монет.

Задачи для самостоятельного решения Заприходованные суммы становились все крупнее. И в самом конце, после пяти или шести ошибочных, зачеркнутых подсчетов, был подведен итог и внизу подписано: «Доля Бонса». Р.Л.Стивенсон. Остров сокровищ

В среднем эти задачи более сложные, чем разобранные выше. 1. Как изменится дележ на «Данае», если пираты поменяют правило 3: план будет считаться принятым, если более половины пиратов проголосовали «за»? Для решения задачи требуется уточнить, как пират решает, какой выдвинуть план, если есть несколько разных планов, каждый из которых принесет этому пирату одно и то же число монет. В этом случае будем считать, что выбор плана происходит случайным образом (например, пират бросает монетку, чтобы сделать выбор между двумя равноценными планами). 2. Как изменится решение предыдущей задачи, если в случае выбора между равноценными планами пират «Данаи» всегда предпочтет тот план, который оставляет больше монет более старшим пиратам? 3. Как именно будут разделены монеты в задаче 5 б) («Горгона» с большой командой и малым запасом золота), если выбор между равноценными планами делается так же, как в предыдущей задаче 2? 4. Сколько денег получит штурман на бригантине «Ехидна» в результате дележа K монет между 2 M + 1 пиратами? 5**. На яхте «Золушка» команда состоит всего из троих – капитана, шкипера и юнги. В найденном ими кладе оказалось всего 15 монет. Поэтому они договорились, что сначала выслушают все три плана, а уже потом будут выбирать. Итак, все по очереди, начиная с капитана и заканчивая юнгой, предлагают свои варианты дележа. Потом все трое одновременно голосуют – каждый выбирает тот из планов, в котором ему достается больше монет. Если таких планов несколько, он проголосует за первый из них. План, получивший больше одного голоса, принимается, и клад делится в соответствии с ним. Однако если такого плана не оказалось, то никто ничего не получает (весь клад выбрасывается за борт). Как окажутся разделены монеты? А каким будет распределение, если решение может быть принято только единогласно?

КВАНТ 2016/№1

такой же. Покидая ядро вместе с бета-частицей (электроном), нейтрон берет на себя те части энергии, импульса и момента импульса, которые необходимы для соблюдения законов сохранения… Мой друг Дебай однако написал мне, что об этой проблеме лучше не думать, как не стоит думать, например, о новых налогах. Но как это ни маловероятно, поскольку нет никаких экспериментальных доказательств, я все же рискну выдвинуть эту гипотезу. Не рискуя, не выиграешь». Через год, в 1931 году Паули опубликовал статью об этой таинственной частице, которая должна спасти законы сохранения, но массу ее уже предложил много меньшую массы электрона. А в 1932 году Чедвик экспериментально доказал, что в атомном ядре содержатся массивные нейтральные частицы – нейтроны и при бета-распаде они не вылетают из ядра. Это открытие принесло Чедвику Нобелевскую премию (1935 г). Теперь гипотетической частице Паули – спасительнице законов сохранения – нужно было давать другое название. Это сделал в 1932 году не он сам, а молодой итальянский физик Энрико Ферми, будущий нобелевский лауреат, прямо на лекции по общей физике перед студентами-первокурсниками Римского университета (которую, кстати, слушал студент Бруно Понтекорво). Ферми экспансивно назвал эту частицу нейтрончиком, маленьким нейтроном, что по-итальянски и звучало как «нейтрино». Итак, законы сохранения были на бумаге спасены. Осталась маленькая загвоздочка – поймать эту частичку, доказать экспериментально, что она есть, и измерить ее энергию и импульс в бета-распаде. С развитием ядерной физики выяснилось, что процессы рождения нейтрино есть, а вот о процессах захвата ничего не было известно. Наконец, в 1960-е годы некоторые такие процессы были предсказаны. У отдельных ядер были определены дискретные уровни энергии, которые подходили для захвата нейтрино, энергии которых теоретически были известными. Правда, вероятность захвата по расчетам оставалась очень маленькой. Поэтому первые эксперименты стали проводить там, где нейтрино очень много, – около работающих ядерных реакторов. И в 1975 году в США Ф.Райнес и К.Коуэн добились успеха. Они использовали реакцию захвата электронного антинейтрино хлором с получением изотопа аргона и позитрона (антиэлектрона). Поскольку позитроны тут же исчезали, аннигилируя с первыми попавшимися электронами, для подсчета поглощенных антинейтрино определялось количество рожденных атомов аргона. Это тоже было непростой задачей, потому что аргона получалось очень мало. Через три месяца работы установки в ней образовалось всего около 5000 атомов аргона (в сутки происходило примерно 40 событий захвата). Конечно, ни на каких весах взвесить это было нельзя, количество аргона определялось по его радиоактивности. Этот эксперимент вошел в историю физики под названием «Полтергейст», в буквальном переводе – «суматошный дух», а в современном вольном переводе – «барабашка». Этот (или эта) барабашка, однако, принес Райнесу Нобелевскую премию в 1995 году, когда ученому исполнилось 85 лет (другой автор открытия и вовсе не дожил до присуждения награды). Почему случился такой большой перерыв? Дело в том, что когда стали уточнять и повторять работу Райнеса, появилась возможность улавливать аналогичным образом и солнечные нейтрино. И оказалось, что земные эксперименты всегда давали в несколько раз меньшее число нейтрино, чем предполагала солнечная астрономия. Возникли подозрения в ошибках солнечной физики. Но во всем остальном ее следствия оправдывались на опыте. Опять нейтрино преподнесло физикам загадку – «головную боль», как стали говорить

Бруно Понтекорво в то время. И вот тогда Понтекорво и выдвинул свою гениальную догадку об «ипостасях» нейтрино и об осцилляциях его различных ароматов. Согласно этой гипотезе, любое нейтрино существует в трех ипостасях – физики пока обозначают эти ипостаси просто номерами 1, 2, 3. Ипостаси имеют разные массы и разные скорости распространения. Согласно корпускулярно-волновому дуализму, они характеризуются дебройлевскими волнами разной длины. Отметим, что если бы массы у них не было, то скорости были бы равны скорости света и ни о каких дебройлевских волнах не могло быть и речи. При распространении по одному направлению дебройлевские волны трех ипостасей интерферируют и образуют регулярные максимумы. Эти максимумы и являются ароматами нейтрино. Таким образом, если при поглощении ядром электрона рождаемое нейтрино имело электронный аромат, то, благодаря тому, что оно состоит из трех ипостасей, через некоторое время движения оно станет мюонным нейтрино, а еще через некоторое время – тау-нейтрино. И это будет все время повторяться. Вот такой оборотень это загадочное нейтрино. А эксперименты были нацелены вначале только на захват («ловлю») электронных нейтрино. Мюонные нейтрино и тау-нейтрино просто не фиксировались в опытах. Так и возникает «пропажа» двух третей солнечных нейтрино. Но это все красиво выглядело на бумаге, в теории. Экспериментальная же проверка гипотезы Понтекорво требовала гораздо большей точности нейтринных экспериментов. Нужно, чтобы события захвата нейтрино происходили гораздо чаще, хотя бы ежесекундно. Очевидно, что единственный путь для этого – значительное увеличение в одной точке (в одной лаборатории) количества установок, где нейтрино могут быть захвачены. Оценочные расчеты показали, что вещества должно быть не меньше нескольких десятков тонн. И к тому же, все это должно происходить там, где будет исключено появление любых других частиц, кроме нейтрино. А космическое излучение – как солнечное, так и приходящее из глубин космоса – в земной атмосфере рождает целые «ливни» частиц. Значит, ловящие нейтрино установки должны располагаться глубоко под землей (или под водой), что значительно увеличивает стоимость таких экспериментов. В 80-е годы прошлого века единственным подходящим по уровням энергии ядра для захвата солнечных нейтрино элементом был галлий. При захвате ядром галлия нейтрино образуется ядро изотопа германия и электрон. Германий может быть химически отделен от галлия, и по его излучению можно судить о его количестве и, значит, о числе захватываемых нейтрино. Галлий содержится обычно как очень не-

КВАНТ 2016/№1

Установка Супер-Камиоканде. Детектор нейтрино меньше.) И тогда электрон начинает терять энергию – он излучает электромагнитную волну, фронт которой имеет вид $конуса.^{2}$ Когда этот фронт пересекает фотоэлемент, возникает импульс фототока. Он очень слабенький, поэтому должен усиливаться специальным прибором – фотоумножителем. Фотоумножитель регистрирует энергию излучения, а значит, энергию электрона, вылетевшего при захвате нейтрино. Реакция фотоумножителя зависит и от направления движения этих электронов. В установке SNO на поверхности шара, содержащего тяжелую воду, было установлено 9500 фотоумножителей. Результаты работы этой установки позволяли подсчитывать как число захватов, вызванных только электронными нейтрино, так и число захватов, вызываемых всеми тремя ароматами нейтрино. Их оказывалось, с хорошей точностью, в 3 раза больше. Однозначный вывод из этого факта такой: несмотря на то что в недрах Солнца рождаются только электронные нейтрино, по дороге в Канаду они осциллируют, превращаясь в другие ароматы. Гипотеза Понтекорво об осцилляциях нейтрино и, следовательно, о наличии у них массы была надежно подтверждена, что и принесло руководителю и вдохновителю проекта Артуру Макдональду Нобелевскую награду. В то время как в Канаде разворачивались эти события, далеко от этого места, в Японии, в 290 километров от Токио в заброшенной цинковой шахте в 1986 году заработала модернизированная установка Супер-Камиоканде (названная так по имени местности около горы Камио). И хотя во многом эти две установки похожи и цель работы у них была одна и та же, японская лаборатория регистрирует совсем другие нейтрино – не солнечные, а атмосферно-космические мюонные нейтрино, рождаемые довольно близко, в верхней атмосфере Земли на высоте 20–30 километров. Было обнаружено еще ранее, что мюонные нейтрино такой энергии имеют некоторую вероятность устроить маленький погром в электронном облаке молекулы обычной воды, в

2 Излучение электронов, двигающихся в веществе быстрее скорости света в этом веществе, по имени открывшего его в 1934 году физика П.А.Черенкова называется черенковским излучением. Черенков и физики-теоретики И.Е.Тамм и И.М.Франк, объяснившие это явление, стали нобелевскими лауреатами в 1958 году. Это была первая Нобелевская премия по физике, полученная учеными нашей страны.

результате которого молекула выбросит быстрый мю-мезон (мюон), становясь при этом ионом. Мюон очень похож на электрон, он точно так же, двигаясь в воде быстрее скорости света в ней, рождает черенковское излучение, которое фиксируется фотоумножителями. Супер-Камиоканде имеет еще большие размеры, чем установка SNO. Она представляет собой цилиндр диаметром около 40 метров и такой же высоты. Цилиндр заполнен обычной, но тщательно очищенной от всех примесей водой. На внутренней поверхности цилиндра размещены 11146 фотоумножителей. Как и в SNO, имеется огромное электротехническое, радиоэлектронное и компьютерное обеспечение работы фотоумножителей и обработки полученных данных. Главным результатом работы этой лаборатории было обнаружение факта зависимости числа поглощаемых нейтрино от направления их движения. Тех частиц, которые двигались сверху вниз, оказалось в два раза больше, чем тех, которые двигались снизу. Последние, прежде чем попасть в ловушку, должны были пройти сквозь весь земной шар. Они по пути не застревали, поскольку воды там почти не было, а других вариантов исчезновения у нейтрино таких энергий нет. Вывод: на пути сквозь земной шар нейтрино успели проосциллировать так, что из начальных мюонных нейтрино осталась только половина. Другая половина оборотилась, став тау-нейтрино, которые если и творили погром молекулы воды, то при этом появлялся не мю-мезон, а тау-мезон. А на черенковское излучение тау-мезона, имеющего другую массу, фотоумножители не реагировали. Хронологически это было первым свидетельством осцилляций, правда не солнечных, а атмосферно-космических нейтрино. В этих опытах оказалось возможным даже оценить массу мюонных нейтрино и таунейтрино. Заметим, что именно здесь 23 ноября 1987 года в один и тот же момент времени все фотоумножители словно помешались – они зарегистрировали огромное количество нейтрино, пришедших от облака взрыва сверхновой звезды. В 2015 году, через 15 лет после опубликования успешных результатов работы руководитель коллектива этой лаборатории Такааки Кадзита стал нобелевским лауреатом вместе с Артуром Макдональдом. Однако ему и его коллективу пришлось пережить тяжелое потрясение – 12 ноября 2001 года стеклянная оболочка одного фотоумножителя не выдержала напора воды и треснула. Поскольку во внутреннем пространстве этого прибора должен быть глубокой вакуум, разрушение носило взрывной характер, и родившаяся ударная волна привела к разрушению 7000 фотоумножителей и другого оборудования. За 5 лет все было построено заново, и в улучшенном варианте установка Супер-Камиоканде II продолжает успешно работать и в настоящее время. Возникает вопрос – а зачем? Результаты получены, нейтрино осциллирует. Можно сказать, что он один существует в трех ипостасях, каждая из которых тоже есть нейтрино. У нейтрино есть масса… На самом деле вопросов, на которые пока нет ответа, стало гораздо больше. Появились гипотезы о других ароматах нейтрино, кроме трех уже известных. Один из них, «стерильное нейтрино», может приблизить разгадку темной материи, другой, «майорановское нейтрино», поможет разгадать асимметрию вещества и антивещества во Вселенной. Так что, возможно, еще не раз на страницах «Кванта» появятся статьи о Нобелевских премиях за нейтрино, эту почти свободную частицу.