Ре­ше­ние. 1.  а) Паша может вы­иг­рать, если S  =  19 или S  =  10, 11, 12, 13, 14, 15. При S  =  19 пер­вым ходом нужно до­ба­вить в кучу один ка­мень, при осталь­ных ука­зан­ных зна­че­ни­ях S нужно удво­ить ко­ли­че­ство кам­ней.

б)  При S  =  16, 17 или 18 удва­и­вать ко­ли­че­ство кам­ней не имеет смыс­ла, так как после та­ко­го хода вы­иг­ры­ва­ет про­тив­ник. По­это­му можно счи­тать, что един­ствен­ный воз­мож­ный ход – это до­бав­ле­ние в кучу од­но­го камня.

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

Вы­иг­рыш­ная стра­те­гия есть у Вали.

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

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

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

Дру­гая воз­мож­ность  — (1) ука­зать на то, что удва­и­вать кучу не имеет смыс­ла, и (2) по­сле­до­ва­тель­но сво­дить слу­чай S  =  18 к слу­чаю S  =  19, слу­чай S  =  17  — к слу­чаю S  =  18 и т. д.

2.  При S  =  9 или 8 вы­иг­рыш­ная стра­те­гия есть у Паши. Она со­сто­ит в том, чтобы удво­ить ко­ли­че­ство кам­ней в куче и по­лу­чить кучу, в ко­то­рой будет со­от­вет­ствен­но 18 или 16 кам­ней. В обоих слу­ча­ях игрок, ко­то­рый будет де­лать ход (те­перь это Валя), про­иг­ры­ва­ет (п. 1б).

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

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