Элементарная задачка

Добрый день.

В прошлой заметке была сформулирована математическая задача из одного давнего Турнира Городов о выборе таких четырёх карт из пяти, чтобы только их порядком можно было точно указать на пятую (для колод из 52 и 53 карт). А во второй половине этой заметки я объясню, почему расширение этой задачки является элементарным.

Классическим решением задачи с 52 картами, к которому многие приходят сами, является следующее:

0. Можно отсортировать все карты (договориться, что 2 < 3, пики < крести и т.д.). Этот порядок нам пригодится, чтобы уметь отсортировать любой набор карт (и потом строить любые перестановки этого набора).

1. Из пяти карт хотя бы две имеют одинаковую масть. Поэтому загадывать надо именно одну из них. Соответственно, первая в нашей четвёрке карт прямо укажет на масть загаданной карты.

2. Оставшиеся три карты можно расположить 3! = 6 разными способами. И нам этого хватает, чтобы закодировать достоинство пятой карты, поскольку на первом шаге из двух карт одинаковой масти мы выбрали не случайную, а ту, от которой до второй карты будет от 1 до 6 шагов (представьте себе круг из карт 2, 3, 4, 5, 6, 7, 8, 9, 10, В, Д, К, Т).

Соответственно, компьютер, посмотрев на первую карту в переданном ему наборе, выясняет не только масть загаданной карты, но и номер, к которому надо прибавить число от 1 до 6, чтобы узнать достоинство искомой карты. А сам этот номер вычисляется мгновенно, так как совпадает с номером перестановки второй, третьей и четвёртой карты.

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

Итак, у нас есть четыре карты, которые можно переставить 4! = 24 способами. А описать этой перестановкой мы должны одну из 49 карт (53 в колоде минус 4 переданных). Как это сделать? Есть масса способов. Но нам должно быть лениво придумывать новое, если и предыдущее решение сработает (кстати, ниже я покажу, что можно было поступить ещё ленивее):

0. На картах задан порядок, поэтому мы их можем перенумеровать от 1 до 52 (джокера сейчас не считаем),

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

2. Пусть J — джокер, T — карта, указывающая остаток при делении на 3, а A и B — две другие карты. Пересчитаем возможные перестановки:
  1) JTAB,
  2) JTBA,
  3) TJAB,
  4) TJBA,
  5) TAJB,
  6) TBJA,
  7) TABJ,
  8) TBAJ.
Получается, что мы можем передать сдвиг от 1 до 8. Но легко понять, что большего нам и не требуется, так как максимальное расстояние между двумя числами от 1 до 49, имеющих одинаковые остатки при делении на три, не превышает 8 (на множестве этих чисел, конечно).

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

Как надо переформулировать задачу, чтобы её было решать просто и приятно?

Из набора чисел от 1 до N каким-то способом выбирают 5 чисел. Необходимо придумать способ закодировать одно из них порядком оставшихся четырёх чисел. Найти максимальное N, при котором это возможно.

Давайте оценим теоретический предел, выше которого N точно не поднимется. Нам на вход дают множество из пяти карт, а мы в ответ должны вернуть загаданную карту X и ещё четыре карты в определённом порядке. Давайте посчитаем, сколькими способами мы можем это сделать:
- загадать карту можем пятью способами (выбрать одну из пяти возможных),
- оставшиеся четыре переставить можно только 4! = 24 способами.
Итого: 5*24 = 120 — это количество разных состояний, которые мы можем вернуть.

А какую информацию надо сообщить? Требуется указать на одну из оставшихся N-4 карт. Т.е. надо передать одно из N-4 состояний.

Выходит, что если N больше 124, то фокус принципиально невозможно исполнить, потому что закодировать мы можем только одно из 120 состояний, а передать требуется одно из N-4 состояний. Так мы поняли, что N не может быть больше 124.

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

Эту задачу можно было бы смело назвать сложной, если бы не существовало способа кодирования для 124 карт, но был бы какой-нибудь способ для, например, 117 карт (так как тогда стояла бы большая проблема доказать, что для 118 карт никакого способа не существует). Но у нас всё просто — верхняя граница достижима, способ для 124 карт есть, поэтому достаточно всего лишь его предъявить :)
Кстати, в комментариях к прошлой заметке уже была дана ссылка не только на разборы этой задачи при N=124, но и на другие её модификации. Но всё же я предлагаю сначала попробовать найти решение своими руками, а уже потом читать чужой подход.

Хорошей недели!

(Хотите примеров сложных задач из разных областей знаний? Недавно мы рассматривали сложную задачку о коробочках, табличках и общей цели, а достаточно давно была геометрическая формулировка о впихивании тетраэдров в куб. В обоих случаях после нахождения какого-то неплохого решения возникает настоящая проблема — доказать, что ничего лучше не сочинить.)

Карты и теория кодирования

Добрый день.

Можно учить теории кодирования (или любому другому разделу математики) традиционно: читать скучные лекции, формулировать непонятные леммы, доказывать ненужные теоремы... А можно показать всего один карточный фокус, чтобы удивить и заинтересовать, а уже потом читать интересные лекции и доказывать нужные теоремы.

Кстати, вчера вышла статья «iPad за партой. Заменят ли планшеты учебники?», для подготовки второй половины которой у меня взяли интервью. Я скептически отношусь к полезности подобной электроники в школе, но отлично понимаю, что хорошая идея и на плохой технике сработает, а плохая идея и на суперкомпьютерах не принесёт плодов. Другими словами, если всё делать грамотно, то и на iPad, и на более бюджетных устройствах можно хорошо обучать. Ниже я предлагаю описание фокуса, для демонстрации которого хватит колоды карт и любого компьютера или даже смартфона (вообще говоря, пару десятилетий назад и человек справлялся, но сейчас это может выглядеть не так эффектно).

На столе стоит компьютер-фокусник (считаем, что без камеры, микрофона и сети). Обычная колода из 52 карт отправляется в аудиторию, откуда возвращаются 5 случайно выбранных карт. Лектор одну из этих карт кладёт на стол, а оставшиеся четыре называет помощнику, который, не зная карту со стола, последовательно нажимает на клавиатуре 8 кнопок (для каждой из четырёх карт сначала масть, а потом достоинство). После этого на экране компьютера появляется изображение пятой карты. Как ему это удаётся?

Надо исходить из того, что это не обман, а математическая задача (то есть, хитрость не в том, что ещё один помощник «как-то через blue-touth с сотового телефона сообщил компьютеру о пятой карте»). Да, всё очень честно! Этот фокус может ошарашить и удивить. Но если вдуматься, то окажется, что это всего лишь математическая задача, которую может решить любой студент.

Давайте сравним количество информации (мы и раньше решали задачи про количество информации), которую ввели в компьютер, с объёмом данных, который он должен вернуть.

Проще всего разобраться с выходными данными: раз всего карт 52, то компьютер, чтобы сообщить достоинство и масть карты со стола, должен вернуть число от 1 до 52 (т.е. всего 52 варианта).

А что со входными данными? Четыре карты можно сообщить 4! = 24 разными способами (меняя порядок карт). Не так уж и мало, хоть и меньше необходимых 52. Как же двигаться дальше? Надо поискать, где ещё можно спрятать хоть чуть-чуть информации.

Предлагаю в комментариях поделиться своими идеями, как подвинуть эти две оценки друг к другу, чтобы стало понятно, как обучить компьютер этому фокусу.

Хорошего дня!

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

Мясные суши (роллы)

Добрый день.

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

Я называю их мясными роллами. Они похожи на суши, только вместо листов нори надо использовать обычный тонкий лаваш, а внутрь можно закладывать всё, что вы любите.

На фотографии справа представлена разделочная досочка, на которой есть всё необходимое.

Итак, нам понадобится:
1. Тонкий лаваш,
2. Мясо (можно два вида, чтобы было интереснее),
3. Сыр (тоже рекомендую заготовить разные, чтобы роллы получались с разными вкусами),
4. Огурцы,
5. Помидоры,
6. Базилик (или что любите)
7. Майонез (чтобы было не слишком сухо и диетично).

Всё (кроме лаваша и майонеза) надо порезать «столбиками» высотой около 7 сантиметров, а лаваш нарежьте ножницами на полоски шириной 7-10, а длиной 17-25 сантиметров (только без линейки, а «на глаз» :). Как говорят программисты, эта деятельность «хорошо параллелится», поэтому веселее всего все приготовления делать хорошей компанией (лишь бы досок и ножей хватило).

После этого можно собирать наши роллы: на листик лаваша кладётся немножко мяска, немножко сыра, огурец или помидор, базилик и капелька майонеза. Далее всё понятно — надо свернуть получившийся ролик (если не будет держаться, то проткните зубочисткой).

Получается маленький и вкусненький «кусочек салата». Я пробовал нарезать всё не так мелко, но почему-то получается менее вкусно. Поэтому рекомендую потратить чуть-чуть больше времени, но и кушать после этого с удовольствием.

Если сложить роллы в пластиковый контейнер, то они прекрасно сохранятся в холодильнике, а если оставить снаружи, то они очень быстро пропадут (будут съедены :). Знаете, очень здорово бывает навернуть супчика, используя вместо хлеба такие роллы!..

Ну а если вы не любите мясо и сыр, а хотите чего-то к чаю, то напоминаю старинный рецепт торта из мясорубки.

Хорошего завершения недели!

Интересное в феврале 2010

Добрый день.

Полтора года назад был весьма насыщенный месяц:

- блогу исполнилось два года (значит, сейчас уже 3.5 :). В той заметке приведена забавная статистика: доля читательниц в какой-то момент сократилась с 35% до 12%. Для сравнения: сейчас 20-25% читателей представляют прекрасный пол.

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

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

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

Ещё мы решали три разнородные задачки, говорили о радости от волейбола и думали о возможных вариациях задачи об острове без зеркал.

Хорошего дня!

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

Бег и травмы суставов

Последние недели мне попадалось очень много людей, решивших занять своё летнее время бегом. Эта мода хорошо распространилась в Европе и США, а теперь потихоньку захватывает и Россию. В самом деле, почему бы не развивать своё сердце и лёгкие, бегая по утрам?

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

Вроде бы красиво выглядит парк, наполненный молодёжью, бегающей по асфальтированным дорожкам. Возникает приятное ощущение, что «люди думают о своём здоровье, о своём будущем». Но проблема в том, что через 10 лет многие из этих людей будут медленно и осторожно ходить от одного врача к другому, а о беге и прыжках забудут навсегда.

И что теперь, не бегать? Конечно, бегать, если хочется. Только надо выбрать подходящее место: мягкую тропинку в лесу/парке или пляж. Кто-то скажет, что по песку бегать сложнее. А разве бегом занимаются, чтобы было проще? Плюсы от бега по пружинящей поверхности перевешивают все минусы, поэтому стоит потратить чуть-чуть времени на дорогу до леса, пляжа или парка. И лучше бегать не в тоненьких кедах, а в нормальных беговых кроссовках. Кстати, профессиональных бегунов тренеры гоняют не по стадиону, а по лесным дорожкам.

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

Если велосипедист:
1) не забывает регулярно пить (чтобы «смазка» поступала в колени),
2) не опускает количество полных оборотов педалями ниже 60 в минуту (так мы защищаемся от чрезмерных нагрузок на суставы, ибо никакого сердца и лёгких не хватит, чтобы в таком темпе ехать на высокой передаче в крутую гору, например),
то всё должно быть хорошо (во всяком случае, если ездить не более 100 километров в день). Ну а если станете ездить больше, то начнут играть роль и другие факторы, но к тому времени вы о них прочитаете на специализированных ресурсах.

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

Хороших выходных и приятного лета!

Кто пылесосит по ночам?

Представьте, что каждую ночь вы слышите не стук перфоратора, не уроки игры на пианино, не весёлую пьянку (потому что живёте в хорошем доме, жильцы которого отличаются повышенной вменяемостью), а... работающий пылесос. Вроде бы никто новый в дом не вселился, но почему-то один из соседей внезапно начал пылесосить каждую ночь примерно с 2:00 до 2:30. Нельзя сказать, что это нестерпимо громко, так как спать особо не мешает. Но интригу-то создаёт! Как тут спокойно уснёшь, если шесть месяцев каждую ночь повторяется одна и та же загадка — что они делают пылесосом по ночам? А через полгода всё прекратилось, как будто и не было ничего. И даже не понятно, кого спросить о причине странных ночных звуков.

В комментариях я буду отвечать, совпадают ли ваши версии с ответом, который я имею основания считать правильным.

Ну а если вы любите ясные формулировки, не подразумевающие нескольких толкований, то следующая математическая часть заметки для вас. Вернёмся к последней задачке об общей цели группы людей. Напомню, что вопрос был в том, с какой вероятностью группа из 2N человек побеждает в игре, если все люди умные и умеют договариваться. Другими словами, надо предъявить функцию P(N), которая описывает вероятность победы группы, а также доказать, что группа не может действовать лучше.

В самой заметке мы доказали, что P(1) = 1/2. Более того, для N>1 очевидно, что P(N) <= 1/2 (так как первый игрок не может обеспечить вероятность выше, чем 1/2, а остальные игроки выше 100% тоже не прыгнут.

Легко понять, что P(N) >= 1/2^(2N), так как каждый игрок, если будет действовать случайным образом, вытянет свой номер с вероятностью 1/2, а всего участников 2N. Так мы сделали оценку снизу.

Далее в комментариях к заметке было предложено несколько подходов для игроков:
- сначала открывать коробочку со своим номером на борту, а дальше (пока не нашёл табличку со своим номером) открывать коробочку с тем номером, который был на табличке из прошлой коробочки. Это интересный способ, но как было показано в комментариях ниже, если в нашей перестановке есть циклы, то игроку придётся открывать одни и те же коробочки несколько раз, что, очевидно, неэффективно.
- ещё можно игрокам с чётными номерами открывать только чётные коробочки, а игрокам с нечётными номерами — только нечётные коробочки.
- очень похожий подход: чётные игроки открывают коробочки с 1 по N, а нечётные — с N+1 до 2N.

Можно нафантазировать ещё несколько подходов, но что с ними делать дальше? Надо научиться корректно считать вероятность победы для предложенных стратегий. Давайте определимся, что такое вероятность победы группы в этой игре.

Определим функцию вероятности победы P(N, S), где S — стратегия группы из 2N игроков:
P(N, S) = W(N, S) / C(N).
В этой формуле W(N, S) — это количество побед для группы из 2N человек, пользующихся стратегией S, на всех возможных входных данных (наборах табличек в коробочках). А C(N) — это количество всех возможных входных данных (т.е. количество способов поместить 2N разных табличек в 2N разных коробочек). Здесь мы исходим из того, что размещение табличек по коробочкам является полностью случайным (т.е. мы можем считать, что все эти элементарные события равновероятны).

Как определиться C(N)? Очень легко — C(N) = (2N)! (т.е. 2N(2N-1)(2N-2)(2N-3)...3*2*1). Это одна из первых формул, которую доказывают студенты, начинающие заниматься комбинаторикой.

А как определить W(N, S)? Простейший способ — честно посчитать. Надо всего лишь проверить для всех перестановок, позволяет ли стратегия S выиграть всей группе (за каждый случай победы надо увеличивать W на единицу).

Давайте, например, разберёмся с этой задачкой для N=2 (раз уж с N=1 мы всё поняли в прошлой заметке):
C(2) = 4! = 24. Действительно, у нас есть следующие 24 перестановки табличек в коробочках:
1234,
1243,
1324,
1342,
1423,
1432,
...
...
4312,
4321.

Теперь для каждой стратегии S, которую мы хотим проверить, надо попробовать её применить на всех 24 возможных входных данных. Соответственно, вероятность P(2, S) = W(2, S) / 24.

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

Далее, имея в руках какие-то надёжно насчитанные равенства и неравенства, можно будет увереннее продвигаться в решении этой задачки. Предлагаю в комментариях к этой заметке добить случай N=2, чтобы в скором времени попробовать ответить на вопрос: если N стремится к бесконечности, то P(N) стремится к нулю? И если не к нулю, то к чему?

Пользуясь случаем, удивлюсь малому количеству ответов к задачке о выворачивании кубика. Что случилось? Вы не пьёте молоко и соки? Или не имеете ножниц, бумаги и скотча? ;) Задачка же хорошая! А пропадает почему-то...

Хороших выходных!

Общая цель

Добрый день!

В задачах о взаимодействии игроков бывают разные цели:
1) индивидуалистическая (максимизировать вероятность собственной победы),
2) бухгалтерская (максимизировать суммарный выигрыш всех игроков),
3) бескомпромиссная (максимизировать вероятность того, что все победят),
4) конкурентная (максимизировать количество тех, у кого результат будет хуже собственного),
5) ...

Классификаций, конечно, бывает много, но они нам сейчас и не нужны. Впрочем, для ясности приведу примеры (возможно, не самые удачные, но короткие, что важнее):
1) шахматная партия — индивидуалистическая игра,
2) задача о составлении расписания или настройке светофоров — бухгалтерская игра (максимизируем комфорт для всех участников),
3) взаимное кредитование стран — бескомпромиссная игра (если один «проиграет», то и остальные полетят вниз),
4) шахматный турнир — конкурентная игра (стараемся подняться как можно выше).

Какое это имеет отношение к жизни? Многие игры возникли не просто так, а являются отражением реальности. Например, когда автомобилист обгоняет пробку по обочине, то он выигрывает в своей индивидуалистической игре (приезжает быстрее), но все остальные проигрывают в бухгалтерской игре (пропускная способность дороги уменьшается из-за того, что эти автомобили потом с обочины лезут обратно на автодорогу). А бывают ситуации, когда даже индивидуального выигрыша человек не получает, но всё равно поступает так, чтобы другим не было удобно (например, когда ставит свою машину так, что она занимает два-три парковочных места).

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

Цель людей — договориться действовать таким образом, чтобы максимизировать вероятность того, что каждый человек откроет коробочку, в которой лежит табличка с его номером. Другими словами, выигрыш каждого возможен только тогда, когда выигрывают все. А если хоть один участник свой номер не найдёт, то их всех заберёт паром из задачки про остров без зеркал. Этого никто не хочет, поэтому все будут стараться :)

Второй вопрос: с какой вероятностью умные люди будут выигрывать в этой игре?

Для начала давайте рассмотрим крайний случай — N=1. У нас есть два участника и две коробочки. В одной коробочке номер одного, в другой — номер второго. Каждый из них может открыть только одну коробочку, поэтому они должны договориться о том, что откроют разные (так как выиграть могут только при условии, что оба увидят свои номера в коробочках). Сначала заходит первый — он может открыть любую коробку (с вероятностью 1/2 в ней он увидит свой номер). Если игроки хорошо договорились, то второй участник вскроет вторую коробку с вероятностью 100%. Соответственно, для N=1 ответ такой:
1) игроки должны договориться, что первый открывает первую коробочку, а второй — вторую (или наоборот),
2) если они так поступят, то выиграют с вероятностью 50%.

Это был простой случай, чтобы лучше понять условие. А теперь приглашаю решить задачу для N>1.

Хорошего дня!

P.S.
Поздравляю всех с победой мужской волейбольной команды России в Мировой лиге 2011! Кстати, наша сборная показала высокий уровень командной игры, что прямо относится к теме этой заметки. Было видно, что каждый игрок понимал, что важно максимизировать не количество мячей, эффектно забитых своими руками, а вероятность победы команды в матче/партии.