Slider

Задача №26. Построение дерева игры. Поиск выигрышной стратегии

Автор материалов - Лада Борисовна Есакова.

В простых играх можно найти выигрышную стратегию, расписав все возможные ходы игроков. Такая схема ходов называется деревом игры.

Все позиции в простых играх делятся на выигрышные и проигрышные.

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

Проигрышная позиция – это такая позиция, при которой игрок, делающий первый ход, проигрывает независимо от выбора очередного хода.

Определение выигравшего игрока при заданной начальной позиции

Пример 1.

Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 3, а во второй – 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигравшего игрока? Ответ обоснуйте.

Решение:

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

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

 

Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.

Таблица содержит все возможные варианты ходов второго игрока и ходы, приводящие к победе первого.

 

Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.

 

Определение выигравшего игрока для различных начальных позиций

Пример 2.

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой 7 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 7). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

Игра за­вер­ша­ет­ся в тот мо­мент, когда сум­мар­ное ко­ли­че­ство кам­ней в кучах ста­но­вит­ся не менее 73. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, т.е. пер­вым по­лу­чив­ший такую по­зи­цию, что в кучах всего будет 73 камня или боль­ше.

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка – зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка. На­при­мер, при на­чаль­ных по­зи­ци­ях (6, 34), (7, 33), (9, 32) вы­иг­рыш­ная стра­те­гия есть у Пети. Чтобы вы­иг­рать, ему до­ста­точ­но удво­ить ко­ли­че­ство кам­ней во вто­рой куче.

За­да­ние 1. Для каж­дой из на­чаль­ных по­зи­ций (6, 33), (8, 32) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

За­да­ние 2. Для каж­дой из на­чаль­ных по­зи­ций (6, 32), (7, 32), (8, 31) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

За­да­ние 3. Для на­чаль­ной по­зи­ции (7, 31) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. Опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стра­те­гии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таб­ли­цы.

 

Решение:

За­да­ние 1. В на­чаль­ных по­зи­ци­ях (6, 33), (8, 32) вы­иг­рыш­ная стра­те­гия есть у Вани. При на­чаль­ной по­зи­ции (6, 33) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (7, 33), (12, 33), (6, 34), (6, 66). Каж­дая из этих по­зи­ций со­дер­жит менее 73 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 73 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Для по­зи­ции (8, 32) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (9, 32), (16, 32), (8, 33), (8, 64). Каж­дая из этих по­зи­ций со­дер­жит менее 73 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 73 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Таким об­ра­зом, Ваня при любом ходе Пети вы­иг­ры­ва­ет своим пер­вым ходом.

За­да­ние 2. В на­чаль­ных по­зи­ци­ях (6, 32), (7, 32) и (8, 31) вы­иг­рыш­ная стра­те­гия есть у Пети. При на­чаль­ной по­зи­ции (6, 32) он дол­жен пер­вым ходом по­лу­чить по­зи­цию (6, 33), из на­чаль­ных по­зи­ций (7, 32) и (8, 31) Петя после пер­во­го хода дол­жен по­лу­чить по­зи­цию (8, 32). По­зи­ции (6, 33) и (8, 32) рас­смот­ре­ны при раз­бо­ре за­да­ния 1. В этих по­зи­ци­ях вы­иг­рыш­ная стра­те­гия есть у иг­ро­ка, ко­то­рый будет хо­дить вто­рым (те­перь это Петя). Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 1. Таким об­ра­зом, Петя при любой игре Вани вы­иг­ры­ва­ет своим вто­рым ходом.

За­да­ние 3. В на­чаль­ной по­зи­ции (7, 31) вы­иг­рыш­ная стра­те­гия есть у Вани. После пер­во­го хода Пети может воз­ник­нуть одна из четырёх по­зи­ций: (8, 31), (7, 32), (14, 31) и (7, 62). В по­зи­ци­ях (14, 31) и (7, 62) Ваня может вы­иг­рать одним ходом, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. По­зи­ции (8, 31) и (7, 32) были рас­смот­ре­ны при раз­бо­ре за­да­ния 2. В этих по­зи­ци­ях у иг­ро­ка, ко­то­рый дол­жен сде­лать ход (те­перь это Ваня), есть вы­иг­рыш­ная стра­те­гия. Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 2. Таким об­ра­зом, в за­ви­си­мо­сти от игры Пети Ваня вы­иг­ры­ва­ет на пер­вом или вто­ром ходу.

 

Ответ:

За­да­ние 1. Ваня вы­иг­ры­ва­ет своим пер­вым ходом.

За­да­ние 2. Петя вы­иг­ры­ва­ет своим вто­рым ходом.

За­да­ние 3. Ваня вы­иг­ры­ва­ет первым или вторым ходом.

Определение начальной позиции, обеспечивающей выигрыш того или иного игрока

Пример 3.

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16 или 45 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

 Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 48. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 48 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 47.

 

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

 

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

 

1. а) Ука­жи­те все такие зна­че­ния числа S, при ко­то­рых Петя может вы­иг­рать в один ход. Обос­нуй­те, что най­де­ны все нуж­ные зна­че­ния S, и ука­жи­те вы­иг­ры­ва­ю­щий ход для каж­до­го ука­зан­но­го зна­че­ния S.

б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

 

2. Ука­жи­те два таких зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём (а) Петя не может вы­иг­рать за один ход и (б) Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня. Для каж­до­го ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

 

3. Ука­жи­те зна­че­ние S, при ко­то­ром:

— у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и

— у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.

 

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

 

Решение:

1. а) Петя может вы­иг­рать, если 16, ..., 47. Во всех этих слу­ча­ях до­ста­точ­но утро­ить ко­ли­че­ство кам­ней. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой боль­ше 47 кам­ней.

б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 15 кам­ней. Тогда после пер­во­го хода Петя в куче будет 16 или 45 кам­ней. В обоих слу­ча­ях Ваня утра­и­ва­ет ко­ли­че­ство кам­ней и вы­иг­ры­ва­ет в один ход.

2. Воз­мож­ные зна­че­ния S: 5 и 14. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 15 кам­ней: в пер­вом слу­чае утро­е­ни­ем, во вто­ром до­бав­ле­ни­ем од­но­го камня. Эта по­зи­ция разо­бра­на в п. 16. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.

3. Воз­мож­ное зна­че­ние S: 13. После пер­во­го хода Пети в куче будет 14 или 39 кам­ней. Если в куче ста­нет 39 кам­ней. Ваня утро­ит ко­ли­че­ство кам­ней н вы­иг­ра­ет пер­вым ходом. Си­ту­а­ция, когда в куче 14 кам­ней, уже разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

На рисунке изображено дерево игры. Выигрышные позиции подчеркнуты.

Ответ:

1.   а) S от16 до 47

б) S = 15

2. S = 5 и S = 14

3. S = 13

Интенсивная подготовка

Бесплатные пробные ЕГЭ

Расписание курсов

Звоните нам: 8 (800) 775-06-82 (бесплатный звонок по России)
                       +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.

НОВЫЙ НАБОР 2020 ЕГЭ И ОГЭ

Типы подготовки:
Сказать спасибо
РЕКОМЕНДУЕМ:
ege-tv

Полный онлайн-курс подготовки к ЕГЭ по математике. Структурировано. Четко. Без воды. Сдай ЕГЭ на 100 баллов!

Смотреть

Для нормального функционирования и Вашего удобства, сайт использует файлы cookies. Это совершенно обычная практика.Продолжая использовать портал, Вы соглашаетесь с нашей Политикой конфиденциальности.

Позвоните мне

Все поля обязательны для заполнения

Отправить

Премиум

Вся часть 2 на ЕГЭ по математике, от задачи 13 до задачи 19. То, о чем не рассказывают даже ваши репетиторы. Все приемы решения задач части 2. Оформление задач на экзамене. Десятки реальных задач ЕГЭ, от простых до самых сложных.

Видеокурс «Премиум» состоит из 7 курсов  для освоения части 2 ЕГЭ по математике (задачи 13-19). Длительность каждого курса - от 3,5 до 4,5 часов.

  1. Уравнения (задача 13)
  2. Стереометрия (задача 14)
  3. Неравенства (задача 15)
  4. Геометрия (задача 16)
  5. Финансовая математика (задача 17)
  6. Параметры (задача 18)
  7. Нестандартная задача на числа и их свойства (задача 19).

Здесь то, чего нет в учебниках. Чего вам не расскажут в школе. Приемы, методы и секреты решения задач части 2.

Каждая тема разобрана с нуля. Десятки специально подобранных задач, каждая из которых помогает понять «подводные камни» и хитрости решения.  Автор видеокурса Премиум - репетитор-профессионал Анна Малкова.

Получи пятерку

Видеокурс «Получи пятерку» включает все темы, необходимые для успешной сдачи ЕГЭ по математике на 60-65 баллов. Полностью все задачи 1-13 Профильного ЕГЭ по математике. Подходит также для сдачи Базового ЕГЭ по математике. Если вы хотите сдать ЕГЭ на 90-100 баллов, вам надо решать часть 1 за 30 минут и без ошибок!

Курс подготовки к ЕГЭ для 10-11 класса, а также для преподавателей. Все необходимое, чтобы решить часть 1 ЕГЭ по математике (первые 12 задач) и задачу 13 (тригонометрия). А это более 70 баллов на ЕГЭ, и без них не обойтись ни стобалльнику, ни гуманитарию.

Вся необходимая теория. Быстрые способы решения, ловушки и секреты ЕГЭ. Разобраны все актуальные задания части 1 из Банка заданий ФИПИ. Курс полностью соответствует требованиям ЕГЭ-2018.

Курс содержит 5 больших тем, по 2,5 часа каждая. Каждая тема дается с нуля, просто и понятно.

Сотни заданий ЕГЭ. Текстовые задачи и теория вероятностей. Простые и легко запоминаемые алгоритмы решения задач. Геометрия. Теория, справочный материал, разбор всех типов заданий ЕГЭ. Стереометрия. Хитрые приемы решения, полезные шпаргалки, развитие пространственного воображения. Тригонометрия с нуля - до задачи 13. Понимание вместо зубрежки. Наглядное объяснение сложных понятий. Алгебра. Корни, степени и логарифмы, функция и производная. База для решения сложных задач 2 части ЕГЭ.

Сразу после оплаты вы получите ссылки на скачивание видеокурсов и уникальные ключи к ним.

Задачи комплекта «Математические тренинги - 2019» непростые. В каждой – интересные хитрости, «подводные камни», полезные секреты.

Варианты составлены так, чтобы охватить все возможные сложные задачи, как первой, так и второй части ЕГЭ по математике.

Как пользоваться?

  1. Не надо сразу просматривать задачи (и решения) всех вариантов. Такое читерство вам только помешает. Берите по одному! Задачи решайте по однойи старайтесь довести до ответа.
  2. Если почти ничего не получилось – начинать надо не с решения вариантов, а с изучения математики. Вам помогут книга для подготовки к ЕГЭи Годовой Онлайн-курс.
  3. Если вы правильно решили из первого варианта Маттренингов 5-7 задач – значит, знаний не хватает. Смотри пункт 1: Книгаи Годовой Онлайн-курс!
  4. Обязательно разберите правильные решения. Посмотрите видеоразбор – в нем тоже много полезного.
  5. Можно решать самостоятельно или вместе с друзьями. Или всем классом. А потом смотреть видеоразбор варианта.

Стоимость комплекта «Математические тренинги – 2019» - всего 1100 рублей. За 5 вариантов с решениями и видеоразбором каждого.