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

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

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

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

 

На­при­мер, пусть в одной куче 6 кам­ней, а в дру­гой 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (6, 9). За один ход из по­зи­ции (6, 9) можно по­лу­чить любую из четырёх по­зи­ций: (7, 9), (12, 9), (6, 10), (6, 18). Чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было 10 кам­ней, во вто­рой куче  — S кам­ней, 1 ≤ S ≤ 51.

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

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

За­да­ние 1.

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

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

За­да­ние 2.

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

За­да­ние 3.

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

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

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

Ре­ше­ние.

За­да­ние 1.

а)  Петя может вы­иг­рать един­ствен­ным спо­со­бом (уве­ли­чив ко­ли­че­ство кам­ней во вто­рой куче в два раза), если S  =  26, …, 41. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить 62 или более кам­ней в двух кучах. При S ≥ 42 у Пети есть более од­но­го вы­иг­ры­ва­ю­ще­го хода (можно удво­ить ко­ли­че­ство кам­ней в любой куче).

б)  Ми­ни­маль­ное зна­че­ние: S = 13. Петя может по­лу­чить по­зи­цию (10, 26), в ко­то­рой Ваня может вы­иг­рать ходом (10, 52). При мень­ших зна­че­ни­ях S ни при каком ходе Пети Ваня не смо­жет вы­иг­рать пер­вым ходом.

 

За­да­ние 2.

Воз­мож­ные зна­че­ния S: 20, 25. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко при S = 20 Петя может по­лу­чить по­зи­цию (20, 20), а при S = 25  — по­зи­цию (11, 25).

В пер­вом слу­чае после хода Вани воз­ник­нет одна из по­зи­ций (21, 20), (40, 20), (20, 21), (20, 40), во вто­ром слу­чае  — одна из по­зи­ций (12, 25), (22, 25), (11 26), (11, 50). В любой из пе­ре­чис­лен­ных по­зи­ций Петя может вы­иг­рать, удво­ив ко­ли­че­ство кам­ней в боль­шей куче.

 

За­да­ние 3.

Воз­мож­ное зна­че­ние S: 24. После пер­во­го хода Пети воз­мож­ны по­зи­ции (11, 24), (20, 24), (10, 25), (10, 48). В по­зи­ци­ях (20, 24) и (10, 48) Ваня может вы­иг­рать пер­вым ходом, удво­ив ко­ли­че­ство кам­ней в любой куче. Из по­зи­ций (11, 24) и (10, 25) Ваня может по­лу­чить по­зи­цию (11, 25), разо­бран­ную в за­да­нии 2. Игрок, после хода ко­то­ро­го воз­ник­ла эта по­зи­ция (в дан­ном слу­чае  — Ваня), вы­иг­ры­ва­ет сле­ду­ю­щим ходом.

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

 

 

 

Ис­ход­ное по­ло­же­ние1-й ход Пети (разо­бра­ны все ходы, ука­за­на по­лу­чен­ная по­зи­ция)1-й ход Вани (толь­ко ход по стра­те­гии, ука­за­на по­лу­чен­ная по­зи­ция)2-й ход Пети (разо­бра­ны все ходы, ука­за­на по­лу­чен­ная по­зи­ция)2-й ход Вани (толь­ко ход по стра­те­гии, ука­за­на по­лу­чен­ная по­зи­ция)
(10, 24)
Всего 34		(10 · 2, 24) = (20,24)
Всего 44		(20 · 2, 24) = (40, 24)
Всего 64
(10, 24 · 2) = (10, 48)
Всего 58		(10 · 2, 48) = (20, 48)
Всего 68
(10 + 1, 24) = (11, 24)
Всего 35		(11, 24 + 1) = (11, 25)
или
(10 + 1, 25) = (11, 25)
Всего 36		(11 + 1, 25) = (12, 25)
Всего 37		(12, 25 · 2) = (12, 50)
Всего 62
(11 · 2, 25) = (22, 25)
Всего 47		(22, 25 · 2) = (22, 50)
Всего 72
(10, 24 + 1) = (10, 25)
Всего 35		(11, 25 + 1) = (11, 26)
Всего 37		(11, 26 · 2) = (11, 52)
Всего 63
(11, 25 · 2) = (11, 50)
Всего 61		(11, 50 · 2) = (11, 100)
Всего 111

 

Рис. 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