Два иг­ро­ка, Паша и Валя, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Паша. За один ход игрок может до­ба­вить в кучу 1 ка­мень или уве­ли­чить число кам­ней в 2 раза. На­при­мер, имея кучу из 7 кам­ней, за один ход можно по­лу­чить кучу из 8 или 14 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 24. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 24 или боль­ше кам­ней. Но, если кам­ней в куче ста­но­вит­ся боль­ше 38, то про­иг­ры­ва­ет тот, кто сде­лал по­след­ний ход. На­при­мер, в куче было 20 кам­ней. Паша, удво­ив ко­ли­че­ство кам­ней, по­лу­чил 40. В таком слу­чае вы­иг­ры­ва­ет не Паша, а Валя.

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

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

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

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

б)  Кто имеет вы­иг­рыш­ную стра­те­гию при S  =  22, 21, 20?

2.  Кто имеет вы­иг­рыш­ную стра­те­гию при S  =  10, 11?

3.  Кто имеет вы­иг­рыш­ную стра­те­гию при S  =  9? Опи­ши­те эту стра­те­гию, по­строй­те де­ре­во ходов.