СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 26 № 13556

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 36. Если при этом в куче ока­за­лось не более 98 кам­ней, то по­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход. В про­тив­ном слу­чае по­бе­ди­те­лем ста­но­вит­ся его про­тив­ник. На­при­мер, если в куче было 33 камня и Паша утро­ит ко­ли­че­ство кам­ней в куче, то игра за­кон­чит­ся и по­бе­ди­те­лем будет Валя. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 35.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния.

1. а) При каких зна­че­ни­ях числа S Паша может вы­иг­рать в один ход?

Ука­жи­те все такие зна­че­ния и со­от­вет­ству­ю­щие ходы Паши.

б) У кого из иг­ро­ков есть вы­иг­рыш­ная стра­те­гия при S = 34; 33; 32?

Опи­ши­те вы­иг­рыш­ные стра­те­гии для этих слу­ча­ев.

2. У кого из иг­ро­ков есть вы­иг­рыш­ная стра­те­гия при S = 11; 10?

Опи­ши­те со­от­вет­ству­ю­щие вы­иг­рыш­ные стра­те­гии.

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

Ре­ше­ние.

1. а) Паша может вы­иг­рать, если S = 35 или S = 12; 13; …; 32. При S = 35 пер­вым ходом нужно до­ба­вить в кучу 1 ка­мень, при осталь­ных ука­зан­ных зна­че­ни­ях S нужно утро­ить ко­ли­че­ство кам­ней.

б) При S = 32 Паша вы­иг­ры­ва­ет в один ход, утра­и­вая ко­ли­че­ство кам­ней (см. п. а). При S = 33 или 34 утра­и­вать ко­ли­че­ство кам­ней не имеет смыс­ла, так как после та­ко­го хода вы­иг­ры­ва­ет про­тив­ник. По­это­му можно счи­тать, что един­ствен­ный воз­мож­ный ход – это до­бав­ле­ние в кучу од­но­го камня.

При S = 34 после та­ко­го хода Паши в куче ста­нет 35 кам­ней. В этой по­зи­ции хо­дя­щий (т. е. Валя) вы­иг­ры­ва­ет (см. п. а)). Т. е. при S = 34 Паша (игрок, ко­то­рый дол­жен хо­дить пер­вым) про­иг­ры­ва­ет. Вы­иг­рыш­ная стра­те­гия есть у Вали.

При S = 33 после того, как Паша своим пер­вым ходом до­ба­вит один ка­мень, в куче ста­нет 34 камня. В этой по­зи­ции хо­дя­щий (т. е. Валя) про­иг­ры­ва­ет (см. выше). Т. е. при S = 33 Паша (игрок, ко­то­рый дол­жен хо­дить пер­вым) вы­иг­ры­ва­ет. Вы­иг­рыш­ная стра­те­гия есть у Паши. Ком­мен­та­рии для экс­пер­тов. Ско­рее всего, ре­ше­ние эк­за­ме­ну­е­мо­го будет не столь по­дроб­ным. Это не яв­ля­ет­ся ошиб­кой. Уче­ник может, на­при­мер, на­ри­со­вать де­ре­вья всех воз­мож­ных пар­тий для ука­зан­ных зна­че­ний S. Дру­гая воз­мож­ность — (1) ука­зать на то, что при S = 33 и 34 утра­и­вать кучу смыс­ла не имеет, и (2) по­сле­до­ва­тель­но сво­дить слу­чай S = 34 к слу­чаю S = 35, а слу­чай S = 33 — к слу­чаю S = 34.

2. При S = 11 после пер­во­го хода Паши в куче будет либо 12 кам­ней, либо 33 камня. В обоих слу­ча­ях вы­иг­рыш­ная стра­те­гия есть у иг­ро­ка, ко­то­рый дол­жен хо­дить, те­перь это Валя. Слу­чай S = 12 рас­смот­рен в за­да­нии 1(а), а слу­чай S = 33 — в за­да­нии 1(б). По­это­му вы­иг­рыш­ная стра­те­гия есть у Вали.

При S = 10 вы­иг­рыш­ная стра­те­гия есть у Паши. Ему нужно пер­вым ходом до­ба­вить 1 ка­мень и по­лу­чить кучу из 11 кам­ней. Как по­ка­за­но выше, в этой си­ту­а­ции вы­иг­рыш­ная стра­те­гия есть у иг­ро­ка, ко­то­рый НЕ дол­жен хо­дить, т. е. у Паши.

3. При S = 9 вы­иг­рыш­ная стра­те­гия есть у Вали. После пер­во­го хода Паши в куче может стать либо 10 кам­ней, либо 27 кам­ней. В обеих этих по­зи­ци­ях вы­иг­ры­ва­ет игрок, ко­то­рый будет де­лать ход (те­перь это Валя).

Слу­чай S = 10 рас­смот­рен в п. 2, слу­чай S = 27 рас­смот­рен в п. 1(а).

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

 

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 30 сентября 2016 года Вариант ИН10103