Задания
Версия для печати и копирования в MS Word
Тип Д26 C3 № 11362
i

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

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

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

 

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

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

б)  У кого из иг­ро­ков есть вы­иг­рыш­ная стра­те­гия при S = 18, 17, 16? Опи­ши­те вы­иг­рыш­ные стра­те­гии для этих слу­ча­ев.

2.  У кого из иг­ро­ков есть вы­иг­рыш­ная стра­те­гия при S = 9, 8? Опи­ши­те со­от­вет­ству­ю­щие вы­иг­рыш­ные стра­те­гии.

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

Спрятать решение

Ре­ше­ние.

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

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

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

Вы­иг­рыш­ная стра­те­гия есть у Вали.

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

При S  =  16 вы­иг­рыш­ная стра­те­гия есть у Вали. Дей­стви­тель­но, если Паша пер­вым ходом удва­и­ва­ет ко­ли­че­ство кам­ней, то в куче ста­но­вит­ся 32 камня, и игра сразу за­кан­чи­ва­ет­ся вы­иг­ры­шем Вали. Если Паша до­бав­ля­ет один ка­мень, то в куче ста­но­вит­ся 17 кам­ней. Как мы уже знаем, в этой по­зи­ции игрок, ко­то­рый дол­жен хо­дить (т. е. Валя), вы­иг­ры­ва­ет.

Во всех слу­ча­ях вы­иг­рыш до­сти­га­ет­ся тем, что при своём ходе игрок, име­ю­щий вы­иг­рыш­ную стра­те­гию, дол­жен до­ба­вить в кучу один ка­мень. За­ме­ча­ние для про­ве­ря­ю­ще­го. Ско­рее всего, ре­ше­ние эк­за­ме­ну­е­мо­го будет не столь по­дроб­ным. Это не яв­ля­ет­ся ошиб­кой. Уче­ник может, на­при­мер, на­ри­со­вать де­ре­вья всех воз­мож­ных пар­тий для ука­зан­ных зна­че­ний S.

Дру­гая воз­мож­ность  — (1) ука­зать на то, что удва­и­вать кучу не имеет смыс­ла, и (2) по­сле­до­ва­тель­но сво­дить слу­чай S  =  18 к слу­чаю S  =  19, слу­чай S  =  17  — к слу­чаю S  =  18 и т. д.

2.  При S  =  9 или 8 вы­иг­рыш­ная стра­те­гия есть у Паши. Она со­сто­ит в том, чтобы удво­ить ко­ли­че­ство кам­ней в куче и по­лу­чить кучу, в ко­то­рой будет со­от­вет­ствен­но 18 или 16 кам­ней. В обоих слу­ча­ях игрок, ко­то­рый будет де­лать ход (те­перь это Валя), про­иг­ры­ва­ет (п. 1б).

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

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

Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Вы­пол­не­ны вто­рое и тре­тье за­да­ния.

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

– в п. 1а не ука­за­но, каким ходом вы­иг­ры­ва­ет Паша;

– в п. 1б не ука­за­но, что иг­ро­кам нет смыс­ла удва­и­вать ко­ли­че­ство кам­ней в куче.

Здесь и далее в ре­ше­ни­ях до­пус­ка­ют­ся ариф­ме­ти­че­ские ошиб­ки, ко­то­рые не ис­ка­жа­ют сути ре­ше­ния и не при­во­дят к не­пра­виль­но­му от­ве­ту

3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 балла, и вы­пол­не­но одно из сле­ду­ю­щих усло­вий.

 · Вы­пол­не­но тре­тье за­да­ние.

 · Вы­пол­не­ны пер­вое и вто­рое за­да­ния.

 · Пер­вое за­да­ние вы­пол­не­но, воз­мож­но, при на­ли­чии недочётов, ука­зан­ных в кри­те­ри­ях на 3 балла; для вто­ро­го за­да­ния (i) пра­виль­но ука­за­но, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию в каж­дой из ука­зан­ных по­зи­ций, и (ii) пра­виль­но ука­зан пер­вый ход Паши при вы­иг­рыш­ной стра­те­гии, од­на­ко не ука­за­но, что после вы­бран­но­го хода Паши по­лу­ча­ет­ся по­зи­ция, вы­иг­рыш­ная для Вали; для тре­тье­го за­да­ния пра­виль­но ука­зан игрок, име­ю­щий вы­иг­рыш­ную стра­те­гию

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 или 2 балла, и вы­пол­не­но одно из сле­ду­ю­щих усло­вий.

 · Пер­вое за­да­ние вы­пол­не­но, воз­мож­но, с недочётами, ука­зан­ны­ми в кри­те­ри­ях на 3 балла.

 · Вто­рое за­да­ние вы­пол­не­но, воз­мож­но, с недочётами, ука­зан­ны­ми в кри­те­ри­ях на 2 балла.

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

1
Не вы­пол­не­но ни одно из усло­вий, поз­во­ля­ю­щих по­ста­вить 1, 2 или 3 балла0
Мак­си­маль­ный балл3
Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ—2017 по ин­фор­ма­ти­ке
Спрятать решение · КритерииСпрятать критерии · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026