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

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

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

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

 

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

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

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

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

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

За­да­ние 1.

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

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

За­да­ние 2.

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

За­да­ние 3.

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

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

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

Ре­ше­ние.

За­да­ние 1.

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

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

 

За­да­ние 2.

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

В пер­вом слу­чае после хода Вани воз­ник­нет одна из по­зи­ций (17, 16), (32, 16), (16, 17), (16, 32), во вто­ром слу­чае  — одна из по­зи­ций (10, 20), (18, 20), (9, 21), (9, 40). В любой из пе­ре­чис­лен­ных по­зи­ций Петя может вы­иг­рать, удво­ив ко­ли­че­ство кам­ней в боль­шей куче.

 

За­да­ние 3.

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

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

 

 

 

Ис­ход­ное по­ло­же­ние1-й ход Пети (разо­бра­ны все ходы, ука­за­на по­лу­чен­ная по­зи­ция)1-й ход Вани (толь­ко ход по стра­те­гии, ука­за­на по­лу­чен­ная по­зи­ция)2-й ход Пети (разо­бра­ны все ходы, ука­за­на по­лу­чен­ная по­зи­ция)2-й ход Вани (толь­ко ход по стра­те­гии, ука­за­на по­лу­чен­ная по­зи­ция)
(8, 19)
Всего 27		(8 · 2, 19) = (16,19)
Всего 35		(16 · 2, 19) = (32, 19)
Всего 51
(8, 19 · 2) = (8, 38)
Всего 46		(8 · 2, 38) = (16, 38)
Всего 54
(8 + 1, 19) = (9, 19)
Всего 28		(9, 19 + 1) = (9, 20)
или
(8 + 1, 20) = (9, 20)
Всего 29		(9 + 1, 20) = (10, 20)
Всего 30		(10, 20 · 2) = (10, 40)
Всего 50
(9 · 2, 20) = (18, 20)
Всего 38		(18, 20 · 2) = (18, 40)
Всего 58
(8, 19 + 1) = (8, 20)
Всего 28		(9, 20 + 1) = (9, 21)
Всего 30		(9, 21 · 2) = (9, 42)
Всего 51
(9, 20 · 2) = (9, 40)
Всего 49		(9, 40 · 2) = (9, 80)
Всего 89

 

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