Е19-21.8 до­ба­вить в кучу один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.

до­ба­вить в кучу один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.

ЕГЭ 16.06.2016 по информатике. Основная волна. Вариант 41 (Часть С)

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

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

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

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

За­да­ние 1

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

б) У кого есть вы­иг­рыш­ная стра­те­гия при S = 38, 39, 40?

За­да­ние 2

Кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию при S = 19, 20?

За­да­ние 3

Кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию при S = 18?

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