Игры в развернутой форме

Игры в развернутой форме Дмитрий Дагаев НИУ Высшая школа экономики Игры в развернутой форме ▶ В предыдущих лекциях мы обсудили различные концепции решения игр, в которых игроки принимают решения о выборе стратегии одновременно и независимо друг от друга. ▶ На этой неделе мы познакомимся с играми, в которых игроки ходят последовательно, и выбор стратегии одного игрока может зависеть от истории игры. Дмитрий Дагаев НИУ ВШЭ 2 / 69 День рождения Иа-Иа Изображение: кадр из мультфильма «Винни-Пух и день забот», Союзмультфильм, 1972. Добросовестное использование. Дмитрий Дагаев НИУ ВШЭ 3 / 69 День рождения Иа-Иа Изображение: кадр из мультфильма «Винни-Пух и день забот», Союзмультфильм, 1972. Добросовестное использование. Дмитрий Дагаев НИУ ВШЭ 4 / 69 День рождения Иа-Иа Изображение: кадр из мультфильма «Винни-Пух и день забот», Союзмультфильм, 1972. Добросовестное использование. Дмитрий Дагаев НИУ ВШЭ 5 / 69 Стратегическое взаимодействие В этой истории между Винни-Пухом и Иа-Иа происходит стратегическое взаимодействие. 1. Сначала Винни-Пух решает, съесть мед из горшочка или нет. 2. А затем уже Иа-Иа решает, принимать подарок от Винни-Пуха или нет. Дмитрий Дагаев НИУ ВШЭ 6 / 69 Стратегическое взаимодействие Предпочтения Винни-Пуха ▶ С одной стороны, Пух очень голоден, а с другой стороны, ему хочется порадовать Иа-Иа, подарив тому замечательный подарок. ▶ Лучше всего для него было бы, если бы он съел мед, а Иа-Иа всё равно бы принял подарок. ▶ Однако для Винни всё-таки лучше не есть мед при условии, что Иа-Иа примет его подарок, чем съесть мед, а потом получить отказ от Иа-Иа. ▶ Хуже всего ему в ситуации, в которой он не ест мед, а Иа-Иа отказывается от подарка. Дмитрий Дагаев НИУ ВШЭ 7 / 69 Стратегическое взаимодействие Предпочтения Иа-Иа ▶ Иа-Иа всегда лучше принять подарок, чем отказаться от него. ▶ Но получить полный горшочек ему хочется больше, чем получить пустой. Дмитрий Дагаев НИУ ВШЭ 8 / 69 Дерево игры ▶ Описанную ситуацию можно представить в виде дерева. ▶ Напомним, что ребра обозначают действия игроков. ▶ А вершинам соответствуют разные состояния игры. Принять Съесть Иа-Иа Не принимать Пух Принять Не есть Иа-Иа Не принимать Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 9 / 69 Дерево игры ▶ Вершины, в которых игра заканчивается, называются терминальными. ▶ Каждой из них приписаны платежи, которые получают игроки. ▶ Такое представление игры называется игрой в развернутой форме. Принять Съесть Иа-Иа Не принимать Пух Принять Не есть Иа-Иа Не принимать Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 10 / 69 Подыгра Подыгрой называется часть дерева, начинающаяся в одной из нетерминальных вершин. Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C 10 5 –5 5 10 –10 0 В нашей игре 3 подыгры: A, B, C. Дмитрий Дагаев НИУ ВШЭ 11 / 69 Стратегия Стратегией игрока в игре в развернутой форме называется набор действий игрока в каждой вершине, в которой ему принадлежит ход. В нашей игре множество действий Винни-Пуха совпадает со множеством его стратегий, так как Винни-Пуху принадлежит ход только в одной вершине: ▶ Съесть мед (С) ▶ Не есть мед (Н) Дмитрий Дагаев НИУ ВШЭ 12 / 69 Стратегия игрока в игре в развернутой форме А как будет выглядеть множество стратегий Иа-Иа? Стратегия Иа-Иа должна содержать информацию о том, что будет делать ослик в каждой из своих вершин: ▶ Как поступит Иа-Иа, если Винни-Пух съел мед? ▶ Как поступит Иа-Иа, если Винни-Пух не съел мед? Дмитрий Дагаев НИУ ВШЭ 13 / 69 Стратегии Первая стратегия Иа-Иа выглядит так: ▶ принять подарок в любом случае (ПП); Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 14 / 69 Стратегии Вторая стратегия Иа-Иа выглядит так: ▶ принять подарок, если Винни съел мед, и не принимать подарок, если Винни не съел мед (ПН); Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 15 / 69 Стратегии Третья стратегия Иа-Иа выглядит так: ▶ не принимать подарок, если Винни съел мед, и принимать подарок, если Винни не съел мед (НП); Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 16 / 69 Стратегии Четвертая стратегия Иа-Иа выглядит так: ▶ не принимать подарок ни в каком из случаев (НН). Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 17 / 69 Решение игры Мы формализовали игру, теперь решим ее. ▶ ▶ ▶ Что, если Винни-Пух уже сделал свой выбор (например, съел мед)? Рассмотрим соответствующую подыгру B. Иа-Иа выгоднее принять подарок, так как тогда его платеж будет равен 5, что больше, чем платеж 0, который он получает, отказываясь от подарка. Принять Съесть Иа-Иа B Пух Не принимать Принять A Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 18 / 69 Решение игры ▶ А что, если Винни-Пух решил не есть мед? ▶ Рассмотрим соответствующую подыгру C. ▶ Иа-Иа опять выгоднее принять подарок, так как тогда его платеж будет больше, чем его платеж в том случае, если он откажется от подарка. Принять Съесть Иа-Иа Не принимать B Пух Принять A Не есть Иа-Иа C Дмитрий Дагаев Не принимать НИУ ВШЭ 10 5 –5 5 10 –10 0 19 / 69 Решение игры Винни-Пух понимает, что какое бы действие он ни совершил, Иа-Иа выгоднее принять его подарок. ▶ ▶ Если Пух съест мед и Иа-Иа примет подарок, то платеж Пуха будет равен 10. Если Пух не съест мед и Иа-Иа примет подарок, то платеж Пуха будет равен 5. Поэтому Винни лучше съесть мед. Принять Съесть Не принимать B Пух A Иа-Иа Принять Не есть Иа-Иа Не принимать C Дмитрий Дагаев НИУ ВШЭ 10 5 –5 5 10 –10 0 20 / 69 Алгоритм Цермело –– Куна ▶ Понять, что произойдет в игре в развернутой форме, можно, последовательно выяснив, как будут себя вести игроки на каждой подыгре. ▶ Алгоритм «решения с конца», который мы использовали в предыдущем примере, называется алгоритмом обратной индукции. ▶ Также он называется алгоритмом Цермело –– Куна. Дмитрий Дагаев НИУ ВШЭ 21 / 69 Дележ пирога Постановка игры ▶ Мама испекла пирог двум своим сыновьям, старшему (C) и младшему (M), и ушла отдыхать, предоставив мальчикам возможность самим решить, как его поделить. ▶ Дележ пирога осуществляется в два периода. ▶ Сразу после ухода мамы старший брат предлагает дележ –– пропорцию, в которой братья могут разделить пирог. ▶ Если младший соглашается на предложение старшего, то они тут же делят пирог в предложенной пропорции и едят его. Дмитрий Дагаев НИУ ВШЭ 22 / 69 Дележ пирога Постановка игры ▶ Если младший отвергает предложение, то во втором периоде (через 15 минут после ухода мамы) настает черед младшего предлагать дележ. ▶ Если старший брат соглашается, то они делят пирог в предложенной младшим пропорции. ▶ Если дележ оба раза заканчивается неудачей, то через 30 минут после ухода мамы с работы приходит голодный папа и съедает весь пирог. Дмитрий Дагаев НИУ ВШЭ 23 / 69 Дележ пирога Платеж старшего брата ▶ Зададим функцию полезности старшего брата от полученной доли пирога: uC (kC ) = δ n kC , Дмитрий Дагаев НИУ ВШЭ 24 / 69 Дележ пирога Платеж старшего брата ▶ Зададим функцию полезности старшего брата от полученной доли пирога: uC (kC ) = δ n kC , ▶ kC –– доля пирога, которую получает старший брат. Дмитрий Дагаев НИУ ВШЭ 25 / 69 Дележ пирога Платеж старшего брата ▶ Зададим функцию полезности старшего брата от полученной доли пирога: uC (kC ) = δ n kC , ▶ n –– число прошедших 15-минутных отрезков. Дмитрий Дагаев НИУ ВШЭ 26 / 69 Дележ пирога Платеж старшего брата ▶ Зададим функцию полезности старшего брата от полученной доли пирога: uC (kC ) = δ n kC , ▶ δ ∈ [0; 1] –– ставка дисконтирования (параметр, показывающий, во сколько раз уменьшается полезность пирога за один 15-минутный отрезок). Дмитрий Дагаев НИУ ВШЭ 27 / 69 Дележ пирога Платеж младшего брата ▶ Функция полезности младшего брата: uM (kM ) = δ n kM , Дмитрий Дагаев НИУ ВШЭ 28 / 69 Дележ пирога Платеж младшего брата ▶ Функция полезности младшего брата: uM (kM ) = δ n kM , ▶ kM –– доля, которую получает младший брат. Дмитрий Дагаев НИУ ВШЭ 29 / 69 Интерпретация ставки дисконтирования Первый период Второй период Третий период Полезность от целого пирога равна 1 Полезность от целого пирога равна 1/2 Полезность от целого пирога равна 1/4 Изображение: Jeûne Genevois plum pie by Schnäggli / CC BY-SA 3.0 Дмитрий Дагаев НИУ ВШЭ 30 / 69 Дележ пирога Дележ Дележом пирога будем называть пару чисел (kC , kM ), где: ▶ kC –– доля пирога, которую получает старший брат; ▶ kM –– доля пирога, которую получает младший брат; ▶ kC + kM = 1. Дмитрий Дагаев НИУ ВШЭ 31 / 69 Дележ пирога Ставка дисконтирования ▶ ▶ ▶ ▶ 1 Будем считать, что в этой игре δ = . 2 За 15 минут пирог теряет половину своих вкусовых качеств. В первом периоде ценность всего пирога равна 1. 1 Во втором периоде ценность пирога равна . 2 Дмитрий Дагаев НИУ ВШЭ 32 / 69 Дележ пирога ▶ Каждый из братьев максимизирует свою полезность. ▶ Если одному из братьев безразлично, принимать дележ, предложенный другим братом, или отвергать его, то он его принимает. Дмитрий Дагаев НИУ ВШЭ 33 / 69 Дележ пирога Решим эту игру с конца. ▶ Если братьям так и не удастся поделить пирог, то платежи C и M будут соответственно равны (uC , uM ) = (0, 0), так как папа съест весь пирог. ▶ Тогда C согласится на любой дележ, который предложит M через 15 минут 1 после ухода мамы, так как uC = δ · kC = · kC ⩾ 0 вне зависимости от того, 2 какую долю пирога kC предложит ему младший брат. Дмитрий Дагаев НИУ ВШЭ 34 / 69 Дележ пирога В какой пропорции предложит разделить пирог M во втором периоде? 1 . 2 ▶ Во втором периоде полезность от всего пирога равна ▶ Максимизируя свой платеж, M предложит C дележ (0, 1). ▶ Тогда uC = δ · kC = ▶ Любой дележ вида (kC , kM ), где kC > 0 принесет M меньшую полезность. Дмитрий Дагаев 1 1 1 · 0 = 0, uM = δ · kM = · 1 = 2 2 2 НИУ ВШЭ 35 / 69 Дележ пирога Какой дележ тогда предложит C после ухода мамы? ▶ ▶ ▶ ▶ 1 1 1 Если C предложит M долю пирога kM < , то uM = kM < = . 2 2 2 Но тогда M не согласится на такой дележ, так как в следующем периоде M 1 1 сможет забрать весь пирог себе и получить uM = δ · kM = · 1 = . 2 2 ( ) 1 1 Поэтому C предложит дележ , . 2 2 1 Предлагать M больше невыгодно для C. 2 Значит, пирог будет разделен сразу после ухода мамы (в первом периоде), и каждый из мальчиков получит платеж 1/2. Дмитрий Дагаев НИУ ВШЭ 36 / 69 Дележ пирога ▶ ▶ Чем закончится игра, если пирог будет за 15 минут терять не половину, а треть своих вкусовых качеств? 2 2 Теперь δ = , то есть во втором периоде ценность целого пирога равна . 3 3 Дмитрий Дагаев НИУ ВШЭ 37 / 69 Дележ пирога ▶ ▶ ▶ ▶ ▶ Максимизируя свою полезность от пирога, M предложит дележ (0, 1) во втором периоде. 2 2 2 Тогда uC = δ · kC = · 0 = 0, uM = δ · kM = · 1 = . 3 3 3 ( ) 1 2 , . Поэтому C в первом периоде предложит дележ 3 3 ( ) 1 2 M согласится на предложение C, и итоговые платежи будут равны , . 3 3 Платеж младшего брата увеличился! Дмитрий Дагаев НИУ ВШЭ 38 / 69 Дележ пирога ▶ Получается, что чем больше δ, тем меньше платеж старшего брата и тем выше платеж младшего брата. ▶ Чем больше δ, тем большую часть пирога при дележе во втором периоде «забирает» себе младший брат. ▶ Поэтому старшему брату приходится предлагать младшему большую долю от пирога в первом периоде. ▶ Важной предпосылкой является тот факт, что пирог теряет свои вкусовые качества в течение времени. ▶ Если бы этого не происходило, то весь пирог забирал бы тот, кто предлагал бы дележ последним. В нашем случае это младший брат. Дмитрий Дагаев НИУ ВШЭ 39 / 69 Дележ пирога ▶ Пусть теперь папа приходит не через 30 минут после ухода мамы, а через 45 минут. ▶ Братья теперь делят пирог в течение трех периодов: сразу после ухода мамы, через 15 минут и через 30 минут после ее ухода. ▶ Первым дележ предлагает старший брат, через 15 минут наступает очередь младшего брата, а через 30 минут дележ снова предлагает старший брат. 1 Ставка дисконтирования δ = . 2 ▶ Дмитрий Дагаев НИУ ВШЭ 40 / 69 Дележ пирога 1 1 1 · = . 2 2 4 ▶ В третьем периоде ценность всего пирога упадет до δ 2 = ▶ Максимизируя свой платеж, в третьем периоде C предложит дележ (1, 0). ▶ Тогда uC = δ 2 · kC = ▶ 1 1 1 · 0 = 0, uM = δ 2 · kM = · 1 = . 4 4 4 M согласится, так как в противном случае весь пирог съест папа и платеж M все равно будет равен 0. Дмитрий Дагаев НИУ ВШЭ 41 / 69 Дележ пирога ▶ ▶ ▶ ▶ ▶ 1 Во втором периоде ценность всего пирога составит δ = . 2 ( ) 1 1 M, максимизируя свою полезность, предложит дележ , . 2 2 1 1 1 1 1 1 Тогда uC = δ · kC = · = , uM = δ · kM = · = . 2 2 4 2 2 4 1 Если M предложит C меньше , то C не примет его предложение, так как 2 в третьем периоде он сможет забрать весь пирог себе и гарантированно 1 1 получить платеж uM = δ 2 · kM = · 1 = . 4 4 1 M нет смысла предлагать C больше . 2 Дмитрий Дагаев НИУ ВШЭ 42 / 69 Дележ пирога ▶ В первом периоде ценность всего пирога составит 1. ▶ Старший, максимизируя свою полезность, предложит дележ ▶ ▶ ( ) 3 1 , . 4 4 1 Если C предложит M меньше , то M не примет его предложение, так как 4 во втором периоде он сможет забрать себе половину пирога и 1 1 1 гарантированно получить платеж uC = δ · kC = · = . 2 2 4 1 C нет смысла предлагать M больше . 4 Дмитрий Дагаев НИУ ВШЭ 43 / 69 Дележ пирога ▶ ▶ Значит, пирог будет разделен в первом периоде, причем старший брат 3 1 получит всего пирога, а младший –– . 4 4 Платеж старшего брата увеличился. ▶ Это произошло из-за того, что старший теперь обладает большей «переговорной силой»: и первый, и последний дележи теперь остаются за ним. ▶ Младший брат, наоборот, оказывается в значительно более слабом положении и получает лишь небольшую часть пирога. Дмитрий Дагаев НИУ ВШЭ 44 / 69 Дележ пирога ▶ Описанная нами игра –– простой случай модели торга Рубинштейна. ▶ Ее автор –– известный израильский экономист Ариэль Рубинштейн 1 . ▶ Данная модель используется, например, в экономике труда. Она хорошо описывает механизм установления равновесной заработной платы на рынке труда, так как заработная плата является результатом торга между работником и работодателем. 1 Rubinstein, A. (1982). Perfect Equilibrium in a Bargaining Model. Econometrica, 50(1), 97–109. Дмитрий Дагаев НИУ ВШЭ 45 / 69 Сломанная ладья Постановка игры ▶ Играют двое. ▶ На клетке a1 стоит ладья. ▶ За один ход можно подвинуть ладью на любое число клеток вправо или на любое число клеток вверх. ▶ Игроки двигают ладью по очереди. ▶ Выигрывает тот, кто первым переставит ладью на клетку h8. Дмитрий Дагаев НИУ ВШЭ 46 / 69 Сломанная ладья ▶ Воспользуемся алгоритмом обратной индукции. ▶ Если после хода соперника ладья оказалась на клетке h8, то игрок проиграл. ▶ Поэтому позиция h8 является проигрышной. ▶ Поставим «0» в клетку h8. Дмитрий Дагаев НИУ ВШЭ 47 / 69 Сломанная ладья ▶ Тогда позиции h1-h7 и a8-g8 являются выигрышными, так как игрок может за один ход передвинуть ладью на клетку h8 и выиграть. ▶ Например, если после хода соперника ладья оказалась на клетке d8, то игрок может передвинуть ладью на 4 клетки вправо и победить. ▶ Поставим «1» в клетки h1-h7 и a8-g8. Дмитрий Дагаев НИУ ВШЭ 48 / 69 Сломанная ладья ▶ Позиция g7 является проигрышной, так как игрок, делающий ход, может передвинуть ладью либо на одну клетку вверх (g8), либо на одну клетку вправо (h7). ▶ Но тогда его соперник, делающий ход следующим, окажется в выигрышной позиции. Дмитрий Дагаев НИУ ВШЭ 49 / 69 Сломанная ладья ▶ Клетки a7-f7 и g1-g6 тогда являются выигрышными, так как игрок может за один ход передвинуть ладью на клетку g7, и тем самым поставить соперника в проигрышную позицию. Дмитрий Дагаев НИУ ВШЭ 50 / 69 Сломанная ладья ▶ Рассуждая подобным образом, можно доказать, что клетки на главной диагонали будут проигрышными, а все остальные клетки –– выигрышными. ▶ Получается, что позиция a1 –– проигрышная. ▶ Значит, при правильной игре всегда выигрывает второй игрок. Дмитрий Дагаев НИУ ВШЭ 51 / 69 Сломанная ладья ▶ Какую стратегию нужно выбрать второму игроку, чтобы гарантировать себе победу? ▶ Например, стратегию «как бы ни сходил первый игрок, всегда возвращать ладью на главную диагональ». ▶ Например, если первый игрок переместил ладью на клетку a4, то второму игроку нужно переместить фигуру на клетку d4. Дмитрий Дагаев НИУ ВШЭ 52 / 69 Сломанная ладья ▶ Действуя таким образом, второй игрок гарантированно выиграет у первого, так как каждый раз после хода второго первый игрок будет оказываться в проигрышной позиции. Дмитрий Дагаев НИУ ВШЭ 53 / 69 Палочки В качестве одного из испытаний в телепередаче «Форт Боярд» игрокам предлагалось сыграть в игру «Палочки». Постановка игры ▶ Играют двое. ▶ На столе лежит 20 палочек. ▶ Два игрока по очереди забирают палочки со стола. ▶ За один ход игрок может убрать 1, 2 или 3 палочки. ▶ Игрок, забирающий со стола последнюю палочку, проигрывает. Дмитрий Дагаев НИУ ВШЭ 54 / 69 Палочки Используем алгоритм обратной индукции, иными словами, решим игру с конца. ▶ Если перед игроком на столе лежит 1 палочка, то он проиграл. Дмитрий Дагаев НИУ ВШЭ 55 / 69 Палочки Тогда игрок, которому принадлежит ход, когда на столе остались 2, 3 или 4 палочки, может заставить соперника проиграть. ▶ Если на столе лежат 2 палочки, то игрок может взять 1 палочку, и тогда его соперник проиграет. ▶ Если на столе лежат 3 палочки, то игрок может взять 2 палочки. ▶ Если на столе лежат 4 палочки, тогда игрок может взять 3 палочки, и тогда его соперник проиграет. Дмитрий Дагаев НИУ ВШЭ 56 / 69 Палочки ▶ Значит, игрок, перед которым находятся 5 палочек, проиграет, так как после того, как он сделает свой ход, перед его соперником окажутся 2, 3 или 4 палочки, а значит, его соперник выиграет. Дмитрий Дагаев НИУ ВШЭ 57 / 69 Палочки ▶ Такой же проигрышной будет и ситуация с 9 палочками. ▶ Если перед кем-то из игроков лежит 9 палочек, то вне зависимости от того, как сходит он, его соперник сможет сделать так, чтобы перед игроком оказались 5 палочек. Дмитрий Дагаев НИУ ВШЭ 58 / 69 Палочки ▶ Ситуации, в которых перед игроком лежат 13 или 17 палочек, также будут проигрышными. Дмитрий Дагаев НИУ ВШЭ 59 / 69 Палочки Что же делать игроку, перед которым лежат 20 палочек? ▶ Взять 3 палочки. ▶ Это поставит соперника в проигрышную ситуацию, так как перед ним окажутся 17 палочек. ▶ Затем можно будет добиться того, чтобы перед соперником оказались 13, 9, 5 и, в конечном итоге, 1 палочка. Дмитрий Дагаев НИУ ВШЭ 60 / 69 Палочки ▶ В общем виде проигрышными будут ситуации, когда перед игроком находятся 4k + 1 палочки (k –– целое, неотрицательное). ▶ 1 палочка является проигрышной позицией, следовательно проигрышными позициями являются и 5, 9, 13, 17, 21, 25, … палочек. ▶ Таким образом, от изначального количества палочек на столе зависит, кто будет выигрывать при правильной игре обоих игроков –– первый или второй игрок. Дмитрий Дагаев НИУ ВШЭ 61 / 69 Палочки ▶ Например, если изначально на столе 20 палочек, как в нашем примере, тогда при правильной игре выигрывает игрок, делающий ход первым. ▶ Однако если на столе изначально лежала бы 21 палочка, тогда бы у первого игрока не было бы шансов победить при правильной игре второго игрока, так как позиция 21 –– проигрышная. Дмитрий Дагаев НИУ ВШЭ 62 / 69 Числа на доске Постановка игры ▶ На доске написаны последовательно числа 1, 2, . . . , 11. ▶ Филипп и Жан по очереди расставляют плюсы и минусы между числами. ▶ Между числами 1 и 2 знак ставит Филипп, между числами 2 и 3 –– Жан, между числами 3 и 4 –– снова Филипп и так далее. Дмитрий Дагаев НИУ ВШЭ 63 / 69 Числа на доске Постановка игры ▶ После того как все знаки проставлены, Филипп и Жан вычисляют значение написанного на доске выражения. ▶ Выигрывает Филипп, если результат получается нечетным. ▶ Выигрывает Жан, если результат получается четным. ▶ На кону шоколадная медаль и 200 долларов. Дмитрий Дагаев НИУ ВШЭ 64 / 69 Числа на доске ▶ Филипп и Жан один раз сыграли в игру, и Жан выиграл. ▶ Филипп в запале предлагает сыграть еще один раз. Он верит, что в этот раз сможет победить. ▶ Прав ли Филипп? ▶ Напомним, на кону шоколадная медаль и 200 долларов. Дмитрий Дагаев НИУ ВШЭ 65 / 69 Числа на доске ▶ Пусть Филипп поставил знак «плюс» между числами 1 и 2. ▶ Сумма чисел 1 и 2 равна 3. Она нечетна. Дмитрий Дагаев НИУ ВШЭ 66 / 69 Числа на доске ▶ Пусть Филипп поставил знак «плюс» между числами 1 и 2. ▶ Сумма чисел 1 и 2 равна 3. Она нечетна. ▶ Пусть теперь Филипп поставил знак «минус» между числами 1 и 2. ▶ Разность чисел 1 и 2 равна −1. Она также нечетна. ▶ Получается, что четность/нечетность результата не зависит от того, какой знак поставил Филипп! Дмитрий Дагаев НИУ ВШЭ 66 / 69 Числа на доске ▶ Предположим, что Филипп поставил знак «плюс» между числами 1 и 2, и теперь пришла очередь Жана делать ход. ▶ Если Жан поставит знак «плюс» между числами 2 и 3, тогда на доске будет записано следующее выражение: 1+2+3 ▶ Его значение равно 6, то есть четно. Дмитрий Дагаев НИУ ВШЭ 67 / 69 Числа на доске ▶ Предположим, что Филипп поставил знак «плюс» между числами 1 и 2, и теперь пришла очередь Жана делать ход. ▶ Если Жан поставит знак «плюс» между числами 2 и 3, тогда на доске будет записано следующее выражение: 1+2+3 ▶ Его значение равно 6, то есть четно. ▶ Если Жан поставит знак «минус» между числами 2 и 3, тогда на доске будет записано следующее выражение: 1+2−3 ▶ Его значение равно 0, то есть четно. Дмитрий Дагаев НИУ ВШЭ 67 / 69 Числа на доске ▶ Получается, что четность/нечетность значения выражения, записанного на доске, не зависит от того, какие знаки стоят между числами. ▶ Пусть на доске написаны числа a и b. ▶ Тогда сумма этих чисел равна a + b, а разность равна a − b. ▶ Заметим, что (a + b) − (a − b) = 2b. ▶ 2b –– четное число. ▶ Значит, для любых чисел a и b значения выражений a + b и a − b имеют одинаковую четность. Дмитрий Дагаев НИУ ВШЭ 68 / 69 Числа на доске ▶ Представим, что Филипп и Жан везде поставили плюсы. ▶ Тогда результат получается четным: 1 + 2 + 3 + . . . + 11 = ▶ (11 + 1) · 11 = 66 2 Если Филипп и Жан поменяют свои стратегии и заменят некоторые плюсы на минусы, значение выражения останется четным, поэтому в этой игре всегда будет выигрывать Жан. Дмитрий Дагаев НИУ ВШЭ 69 / 69