menu
person

Задача №2908

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­к

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

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

        до­ба­вить в кучу один ка­мень (дей­ствие А) или

        утро­ить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (дей­ствие Б).

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

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

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

 

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

 

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

1.

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

       б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за

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

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

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

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

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

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

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

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

 

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

1. а) Петя может вы­иг­рать, если S = 14, …, 39. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой не менее 40 кам­ней. Пете до­ста­точ­но уве­ли­чить ко­ли­че­ство кам­ней в 3 раза и от­нять два камня (дей­ствие Б). При S< 14 по­лу­чить за один ход боль­ше 39 кам­ней не­воз­мож­но.

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

2. Воз­мож­ные зна­че­ния S: 5, 12. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 10 кам­ней (при S = 5 он вы­пол­ня­ет дей­ствие Б; при S = 12 – до­бав­ля­ет 1 ка­мень, т. е. вы­пол­ня­ет дей­ствие А). Эта по­зи­ция разо­бра­на в п. 1б. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.

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

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

 

 

 

  По­ло­же­ния после оче­ред­ных ходов
Исх.

полож.

1‐й ход Пети

(разо­бра­ны все

ходы)

1‐й ход

Вани

(толь­ко

ход по

стра­те­гии)

2‐й ход Пети

(разо­бра­ны все

ходы)

2‐й ход Вани

(толь­ко ход по

стра­те­гии)

11 11+1 =12 12+1=13 13+1=14 3*14–2=40
3*13–2=37 3*37–2=109
3*11–2=31 3*31–2=91    

 

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