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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой 7 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 7). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка – зна­чит, опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка. На­при­мер, при на­чаль­ных по­зи­ци­ях (6, 36), (7, 35), (9, 34) вы­иг­рыш­ная стра­те­гия есть у Пети. Чтобы вы­иг­рать, ему до­ста­точ­но удво­ить ко­ли­че­ство кам­ней во вто­рой куче.

 

      За­да­ние 1. Для каж­дой из на­чаль­ных по­зи­ций (6, 35), (8, 34) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт

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

 

      За­да­ние 2. Для каж­дой из на­чаль­ных по­зи­ций (6, 34), (7, 34), (8, 33) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

 

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

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

Ре­ше­ние.

За­да­ние 1. В на­чаль­ных по­зи­ци­ях (6, 35), (8, 34) вы­иг­рыш­ная стра­те­гия есть у Вани. При на­чаль­ной по­зи­ции (6, 35) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (7, 35), (12, 35), (6, 36), (6, 70). Каж­дая из этих по­зи­ций со­дер­жит менее 77 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 77 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Для по­зи­ции (8, 34) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (9, 34), (16, 34), (8, 35), (8, 68). Каж­дая из этих по­зи­ций со­дер­жит менее 77 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 77 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Таким об­ра­зом, Ваня при любом ходе Пети вы­иг­ры­ва­ет своим пер­вым ходом.

 

      За­да­ние 2. В на­чаль­ных по­зи­ци­ях (6, 34), (7, 34) и (8, 33) вы­иг­рыш­ная стра­те­гия есть у Пети. При на­чаль­ной по­зи­ции (6, 34) он дол­жен пер­вым ходом по­лу­чить по­зи­цию (6, 35), из на­чаль­ных по­зи­ций (7, 34) и (8, 33) Петя после пер­во­го хода дол­жен по­лу­чить по­зи­цию (8, 34). По­зи­ции (6, 35) и (8, 34) рас­смот­ре­ны при раз­бо­ре за­да­ния 1. В этих по­зи­ци­ях вы­иг­рыш­ная стра­те­гия есть у иг­ро­ка, ко­то­рый будет хо­дить вто­рым (те­перь это Петя). Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 1. Таким об­ра­зом, Петя при любой игре Вани вы­иг­ры­ва­ет своим вто­рым ходом.

 

      За­да­ние 3. В на­чаль­ной по­зи­ции (7, 33) вы­иг­рыш­ная стра­те­гия есть у Вани. После пер­во­го хода Пети может воз­ник­нуть одна из четырёх по­зи­ций: (8, 33), (7, 34), (14, 33) и (7, 66). В по­зи­ци­ях (14, 33) и (7, 66) Ваня может вы­иг­рать одним ходом, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. По­зи­ции (8, 33) и (7, 34) были рас­смот­ре­ны при раз­бо­ре за­да­ния 2. В этих по­зи­ци­ях у иг­ро­ка, ко­то­рый дол­жен сде­лать ход (те­перь это Ваня), есть вы­иг­рыш­ная стра­те­гия. Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 2. Таким об­ра­зом, в за­ви­си­мо­сти от игры Пети Ваня вы­иг­ры­ва­ет на пер­вом или на вто­ром ходу.

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

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

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

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

1) пра­виль­но ука­за­ны все по­зи­ции, в ко­то­рых Петя вы­иг­ры­ва­ет пер­вым ходом;

2) пра­виль­но ука­за­на по­зи­ция, в ко­то­рой Ваня вы­иг­ры­ва­ет пер­вым ходом;

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

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

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

 

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

и вы­пол­не­но одно из сле­ду­ю­щих усло­вий.

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

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

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

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

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

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

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

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

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


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