Две по­дру­ги, Катя и Ира, иг­ра­ют в сле­ду­ю­щую игру. Перед по­дру­га­ми лежит куча кам­ней. Де­вуш­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Катя. За один ход де­вуш­ка может до­ба­вить в кучу один или два камня или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11, 12 или 20 кам­ней. У каж­дой де­вуш­ки, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

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

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

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

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

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

Опи­ши­те вы­иг­рыш­ную стра­те­гию Иры.

2.  Ука­жи­те два таких зна­че­ния S, при ко­то­рых у Кати есть вы­иг­рыш­ная стра­те­гия, причём (а) Катя не может вы­иг­рать за один ход и (б) Катя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ира.

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

3.  Ука­жи­те зна­че­ние S, при ко­то­ром:

– у Иры есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ей вы­иг­рать пер­вым или вто­рым ходом при любой игре Кати, и

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

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