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

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

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

 

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

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

За­да­ние 1

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

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

 

За­да­ние 2

Ука­жи­те два таких зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная

стра­те­гия, причём од­но­вре­мен­но вы­пол­не­ны два усло­вия:

– Петя не может вы­иг­рать за один ход;

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

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

 

За­да­ние 3

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

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

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

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

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

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

Ре­ше­ние.

1а) Петя может вы­иг­рать, если 64 >= S >= 33. Ему нужно удво­ить ко­ли­че­ство кам­ней.

1б) Ис­ко­мые по­зи­ции те, ко­то­рые при­ве­дут Ваню к вы­иг­рыш­ным зна­че­ни­ям S >= 33. Это S=32, по­сколь­ку при любом ходе Пети S+1=33 или S*2=64 Ваня вы­иг­ра­ет.

2.  По­зи­ция S=32 про­иг­рыш­ная, зна­чит, если Петя смо­жет в свой ход при­ве­сти Ваню в по­зи­цию S=32, он вы­иг­ра­ет. Это можно сде­лать из по­зи­ций S=31 и S=16. В пер­вом слу­чае мы до­бав­ля­ем 1 ка­мень, а во вто­ром уве­ли­чи­ва­ем их ко­ли­че­ство вдвое. Как бы ни по­хо­дил Вася, для вы­иг­ры­ша Пете до­ста­точ­но будет уве­ли­чить ко­ли­че­ство кам­ней в 2 раза.

 

3.  S=30. При­ве­дем таб­ли­цу и де­ре­во пар­тий.

 

Пер­вый ход ПетиПер­вый ход ВаниВто­рой ход ПетиВто­рой ход Вани
30 + 1 = 3131 + 1 = 3232 + 1 = 3333 · 2 = 66  — ПО­БЕ­ДА
30 · 2 = 6060 · 2 = 120  — ПО­БЕ­ДА32 · 2 = 6464 · 2 = 128  — ПО­БЕ­ДА

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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