Дилемма заключенного и доминантные стратегии. Теория игр - [12]
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2011), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру можно обобщить и дальше, изменив число фишек, которые можно брать на каждом ходу.
Игра 2: выигрывает второй
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, ..., 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 - n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.
Игра 3: общий случай
Допустим, что на столе m фишек и каждым ходом можно брать от 1 до n фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?
Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:
1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n+1. Для этого на каждом ходу, если первый игрок берет p фишек (0 2. Остаток от деления равен r(0
Книга посвящена жизни и творчеству выдающегося советского кристаллографа, основоположника и руководителя новейших направлений в отечественной науке о кристаллах, основателя и первого директора единственного в мире Института кристаллографии при Академии наук СССР академика Алексея Васильевича Шубникова (1887—1970). Классические труды ученого по симметрии, кристаллофизике, кристаллогенезису приобрели всемирную известность и открыли новые горизонты в науке. А. В. Шубников является основателем технической кристаллографии.
Нильс Бор — одна из ключевых фигур квантовой революции, охватившей науку в XX веке. Его модель атома предполагала трансформацию пределов знания, она вытеснила механистическую модель классической физики. Этот выдающийся сторонник новой теории защищал ее самые глубокие физические и философские следствия от скептиков вроде Альберта Эйнштейна. Он превратил родной Копенгаген в мировой центр теоретической физики, хотя с приходом к власти нацистов был вынужден покинуть Данию и обосноваться в США. В конце войны Бор активно выступал за разоружение, за интернационализацию науки и мирное использование ядерной энергии.
Джеймс Клерк Максвелл был одним из самых блестящих умов XIX века. Его работы легли в основу двух революционных концепций следующего столетия — теории относительности и квантовой теории. Максвелл объединил электричество и магнетизм в коротком ряду элегантных уравнений, представляющих собой настоящую вершину физики всех времен на уровне достижений Галилея, Ньютона и Эйнштейна. Несмотря на всю революционность его идей, Максвелл, будучи очень религиозным человеком, всегда считал, что научное знание должно иметь некие пределы — пределы, которые, как ни парадоксально, он превзошел как никто другой.
Ежемесячный научно-популярный и научно-художественный журнал.
«Занимательное дождеведение» – первая книга об истории дождя.Вы узнаете, как большая буря и намерение вступить в брак привели к величайшей охоте на ведьм в мировой истории, в чем тайна рыбных и разноцветных дождей, как люди пытались подчинить себе дождь танцами и перемещением облаков, как дождь вдохновил Вуди Аллена, Рэя Брэдбери и Курта Кобейна, а Даниеля Дефо сделал первым в истории журналистом-синоптиком.Сплетая воедино научные и исторические факты, журналист-эколог Синтия Барнетт раскрывает удивительную связь между дождем, искусством, человеческой историей и нашим будущим.
Эта книга – захватывающий триллер, где действующие лица – охотники-ученые и ускользающие нейтрино. Крошечные частички, которые мы называем нейтрино, дают ответ на глобальные вопросы: почему так сложно обнаружить антиматерию, как взрываются звезды, превращаясь в сверхновые, что происходило во Вселенной в первые секунды ее жизни и даже что происходит в недрах нашей планеты? Книга известного астрофизика Рэя Джаявардхана посвящена не только истории исследований нейтрино. Она увлекательно рассказывает о людях, которые раздвигают горизонты человеческих знаний.
Можно ли выразить красоту с помощью формул и уравнений? Существует ли в мире единый стандарт прекрасного? Возможно ли измерить гармонию с помощью циркуля и линейки? Математика дает на все эти вопросы утвердительный ответ. Золотое сечение — ключ к пониманию секретов совершенства в природе и искусстве. Именно соблюдение «божественной пропорции» помогает художникам достигать эстетического идеала. Книга «Золотое сечение. Математический язык красоты» открывает серию «Мир математики» — уникальный проект, позволяющий читателю прикоснуться к тайнам этой удивительной науки.
В чем состоит загадка творчества? Существуют ли правила созидания? Действительно ли решение сложной задачи можно найти только в моменты удивительного озарения? Этими вопросами, наверное, задавался каждый из нас. Цель этой книги — рассказать о правилах творчества, его свойствах и доказать, что творчество доступно многим. Мы творим, когда мы размышляем, когда задаемся вопросами о жизни. Вот почему в основе математического творчества лежит умение задавать правильные вопросы и находить на них ответы.
Физика, астрономия, экономика и другие точные науки основаны на математике — это понятно всем. Но взаимосвязь математики и творчества не столь очевидна. А ведь она куда глубже и обширнее, чем думают многие из нас. Математика и творчество развивались параллельно друг другу на протяжении веков. (Например, открытие математической перспективы в эпоху Возрождения привело к перевороту в живописи.) Эта книга поможет читателю посмотреть на некоторые шедевры живописи и архитектуры «математическим взглядом» и попробовать понять замысел их создателей.
Число π, пожалуй, самое удивительное и парадоксальное в мире математики. Несмотря на то что ему посвящено множество книг, оно по праву считается самым изученным и сказать о нем что-то новое довольно сложно, оно по-прежнему притягивает пытливые умы исследователей. Для людей, далеких от математики, число π окружено множеством загадок. Знаете ли вы, для чего ученые считают десятичные знаки числа π? Зачем нам необходим перечень первого миллиарда знаков π? Правда ли, что науке известно все о числе π и его знаках? На эти и многие другие вопросы поможет найти ответ данная книга.