Задания
Версия для печати и копирования в MS Word
Тип 20 № 76688
i

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

В от­ве­те за­пи­ши­те най­ден­ные зна­че­ния в по­ряд­ке воз­рас­та­ния.

 

Ответ:

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

Ре­ше­ние.

Если игрок по­лу­ча­ет кучу из 46 кам­ней, то он по­беж­да­ет, при­ба­вив к куче мак­си­маль­ный де­ли­тель 46. Сле­до­ва­тель­но, игрок по­лу­чив­ший кучу из 45 кам­ней не может вы­иг­рать, но может вы­иг­рать со­пер­ник, не­за­ви­си­мо от хода пер­во­го иг­ро­ка. Тогда мак­си­маль­ная куча, при ко­то­рой вы­иг­ра­ет Петя вто­рым ходом, не­за­ви­си­мо от хода Вани - 44 камня. Петя до­бав­ля­ет один ка­мень и, при любом ходе Вани, вы­иг­ры­ва­ет своим вто­рым ходом.

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

Ва­ри­ан­ты:

44+1

42+3

40+5

36+9

30+15

Ми­ни­маль­ное зна­че­ние - 30 кам­ней. Петя до­бав­ля­ет 15 кам­ней, тогда, не­за­ви­си­мо от хода Вани, Петя вы­иг­ры­ва­ет своим вто­рым ходом.

 

 

Ответ: 30; 44.