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

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

до­ба­вить в кучу один ка­мень или

до­ба­вить в кучу два камня или

уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.

 

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

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

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

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

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

За­да­ние 1.

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

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

За­да­ние 2.

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

За­да­ние 3.

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

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

Де­ре­во не долж­но со­дер­жать пар­тий, не­воз­мож­ных при ре­а­ли­за­ции вы­иг­ры­ва­ю­щим иг­ро­ком своей вы­иг­рыш­ной стра­те­гии. На­при­мер, пол­ное де­ре­во игры не будет вер­ным от­ве­том на это за­да­ние.

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

Ре­ше­ние.

За­да­ние 1.

а)  Петя может вы­иг­рать един­ствен­ным спо­со­бом (уве­ли­чив ко­ли­че­ство кам­ней в 2 раза), если S = 19, ..., 35. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой будет 38 или более кам­ней. При S = 36 и S = 37 у Пети есть более од­но­го вы­иг­ры­ва­ю­ще­го хода.

б)  Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 18 кам­ней. Тогда после пер­во­го хода Пети в куче будет 19, 20 или 36 кам­ней. Во всех слу­ча­ях Ваня уве­ли­чи­ва­ет ко­ли­че­ство кам­ней в 2 раза и вы­иг­ры­ва­ет в один ход.

За­да­ние 2.

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

За­да­ние 3.

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

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

 

Ис­ход­ное по­ло­же­ние1-й ход Пети (разо­бра­ны все ходы, ука­за­на по­лу­чен­ная по­зи­ция)1-й ход Вани (толь­ко ход по стра­те­гии, ука­за­на по­лу­чен­ная по­зи­ция)2-й ход Пети (разо­бра­ны все ходы, ука­за­на по­лу­чен­ная по­зи­ция)2-й ход Вани (толь­ко ход по стра­те­гии, ука­за­на по­лу­чен­ная по­зи­ция)
1515 + 1 = 1616 + 2 = 1818 + 1 = 1919 * 2 = 38>>
18 + 2 = 2020 * 2 = 40>>
18 * 2 = 3636 * 2 = 72>>
15 + 2 = 1717 + 1 = 1818 + 1 = 1919 * 2 = 38>>
18 + 2 = 2020 * 2 = 40>>
18 * 2 = 3636 * 2 = 72>>
15 * 2 = 3030 * 2 = 60>>

Рис. 1. Де­ре­во всех пар­тий, воз­мож­ных при опи­сан­ной стра­те­гии Пети. Ходы Пети по­ка­за­ны сплош­ны­ми стрел­ка­ми, ходы Вани по­ка­за­ны пунк­тир­ны­ми стрел­ка­ми. За­клю­чи­тель­ные по­зи­ции обо­зна­че­ны зна­ком >>.

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

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

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

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

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

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

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

3

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

— вы­пол­не­но тре­тье за­да­ние;

— вы­пол­не­ны пер­вое и вто­рое за­да­ния;

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

2

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

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

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

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

1
Не вы­пол­не­но ни одно из усло­вий, поз­во­ля­ю­щих по­ста­вить 3, 2 или 1 балл0
Мак­си­маль­ный балл3
Спрятать решение · КритерииСпрятать критерии · Помощь


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