Задача №2907

Два иг­ро­ка, Паша и Вася, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­л

Поиск задачи:

Здесь представлено решение задачи по информатике. Если у вас возникли сложности в решении то вы можете воспользоваться ответами которые размещены на данной странице. Вы конечно можете не согласиться с ответами, но данная информация размещена с целью ознакомления. Списывать с ответов или решать самому выбирать вам. Данная задача по теме Вы­иг­рыш­ная стратегия
Решение задачи:

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

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

кам­ней в куче в два раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16, 17 или 30 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 55.

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

 

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

 

За­да­ние 1

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

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

 

За­да­ние 2

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

 

За­да­ние 3

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

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

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

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Васи.

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

 

По­яс­не­ние.

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

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

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

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

В таб­ли­це при­ве­де­ны воз­мож­ные пар­тии при опи­сан­ной стра­те­гии Васи.

За­клю­чи­тель­ные по­зи­ции (в них вы­иг­ры­ва­ет Вася) подчёрк­ну­ты. На ри­сун­ке де­ре­во изоб­ра­же­но в гра­фи­че­ском виде (оба спо­со­ба изоб­ра­же­ния де­ре­ва до­пу­сти­мы).

 

 

Категория: по информатике | Добавил: (13.09.2015)
Просмотров: | Теги: Вы­иг­рыш­ная стратегия | Рейтинг: 0.0/0


Другие задачи:
Всего комментариев: 0
avatar