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

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

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 41.

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

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

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

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

 

За­да­ние 1.

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

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

 

За­да­ние 2.

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

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

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

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

 

За­да­ние 3.

Ука­жи­те зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

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

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

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

Ре­ше­ние.

За­да­ние 1.

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

При­ме­ча­ние. При куче, на­при­мер, из 40 кам­ней Ваня может вы­иг­рать и дру­гим ходом  — до­ба­вив в кучу 1 или 4 камня. Но в усло­вии не тре­бу­ет­ся ука­зы­вать все вы­иг­рыш­ные стра­те­гии.

б)  Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S  =  13 кам­ней. Тогда после пер­во­го хода Пети в куче будет 14, 17 или 39 кам­ней. Во всех слу­ча­ях Ваня утра­и­ва­ет ко­ли­че­ство кам­ней и вы­иг­ры­ва­ет в один ход.

 

За­да­ние 2.

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

 

За­да­ние 3.

Воз­мож­ные зна­че­ния S: 8, 11.

На­при­мер, для S  =  8 после пер­во­го хода Пети в куче будет 9 кам­ней, 12 кам­ней или 24 камня. Если в куче ста­нет 24 камня, Ваня утро­ит ко­ли­че­ство кам­ней и вы­иг­ра­ет пер­вым ходом. Си­ту­а­ция, когда в куче 9 или 12 кам­ней, разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

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

 

 

Де­ре­во всех пар­тий, воз­мож­ных при Ва­ни­ной стра­те­гии.

Зна­ком >> обо­зна­че­ны по­зи­ции, в ко­то­рых пар­тия за­кан­чи­ва­ет­ся.

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

В за­да­че от уче­ни­ка тре­бу­ет­ся вы­пол­нить 3 за­да­ния. Их труд­ность воз­рас­та­ет. Ко­ли­че­ство бал­лов в целом со­от­вет­ству­ет ко­ли­че­ству вы­пол­нен­ных за­да­ний (по­дроб­нее см. ниже).

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

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

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

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

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

Во всех слу­ча­ях стра­те­гии могут быть опи­са­ны так, как это сде­ла­но

в при­ме­ре ре­ше­ния, или дру­гим спо­со­бом.

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Вы­пол­не­ны вто­рое и тре­тье за­да­ния. Пер­вое за­да­ние вы­пол­не­но пол­но­стью или ча­стич­но. Здесь и далее до­пус­ка­ют­ся ариф­ме­ти­че­ские ошиб­ки, ко­то­рые не ис­ка­жа­ют сути ре­ше­ния и не при­во­дят к не­пра­виль­но­му от­ве­ту3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 балла, и вы­пол­не­но одно из сле­ду­ю­щих усло­вий.

1. Тре­тье за­да­ние вы­пол­не­но пол­но­стью.

2. Пер­вое и вто­рое за­да­ния вы­пол­не­ны пол­но­стью.

3. Пер­вое за­да­ние вы­пол­не­но пол­но­стью или ча­стич­но, для вто­ро­го и тре­тье­го за­да­ний ука­за­ны пра­виль­ные зна­че­ния S

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

1. Пер­вое или вто­рое за­да­ние вы­пол­не­но пол­но­стью.

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

3. Пер­вое за­да­ние вы­пол­не­но ча­стич­но, и для од­но­го из осталь­ных за­да­ний пра­виль­но ука­за­ны зна­че­ния S.

4. Для вто­ро­го и тре­тье­го за­да­ний пра­виль­но ука­за­ны зна­че­ния S

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