Question

За один ход игрок может добавить в одну из куч (по своему выбору) добавить два камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 66. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 66 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче – S камней; 1 ≤ S ≤ 58. 20 минимальное значение 21 два значения

Answer 1

Такое зна­че­ние S — 30. При S = 30 Петя своим пер­вым ходом может по­лу­чить одну из четырёх по­зи­ций: (7, 31), (8, 30), (14, 30), (7, 60).

В по­зи­ции (7, 60) Ваня удва­и­ва­ет ко­ли­че­ство кам­ней во вто­рой куче и вы­иг­ры­ва­ет своим пер­вым ходом.

Из по­зи­ций (14, 30) и (7, 31) Ваня может по­лу­чить по­зи­цию (14, 31). В этом слу­чае после вто­ро­го хода Пети может воз­ник­нуть одна из четырёх по­зи­ций: (15, 31), (14, 32), (28, 31), (14, 62). Во всех слу­ча­ях Ваня удва­и­ва­ет ко­ли­че­ство кам­ней во вто­рой куче и вы­иг­ры­ва­ет своим вто­рым ходом.

Из по­зи­ции (8, 30) Ваня своим пер­вым ходом может по­лу­чить по­зи­цию (16, 30). После вто­ро­го хода Пети может воз­ник­нуть одна из четырёх по­зи­ций: (17, 30), (16, 31), (32, 30), (16, 60). Во всех слу­ча­ях Ваня удва­и­ва­ет ко­ли­че­ство кам­ней во вто­рой куче и вы­иг­ры­ва­ет своим вто­рым ходом.

Таким об­ра­зом, ответ — 30.

ответ: 30.

При­ме­ча­ние. До­ка­жем, что при S ≤ 29 либо вы­иг­ры­ва­ет Петя своим пер­вым или вто­рым ходом, либо игра не за­вер­шит­ся за 4 хода.

При S ≤ 7 Петя своим пер­вым ходом может до­ба­вить в боль­шую кучу один ка­мень. Тогда, даже если из­на­чаль­но S = 7, наи­боль­шее ко­ли­че­ство кам­ней, ко­то­рое можно по­лу­чить сум­мар­но в обеих кучах за 4 хода, каж­дый раз удва­и­вая боль­шую кучу, рав­ня­ет­ся 71.

При 8 ≤ S ≤ 16 Петя может вы­брать такую стра­те­гию, ко­то­рая не поз­во­лит по­бе­дить Ване за один или два хода. Для этого Петя каж­дый ход может при­бав­лять к пер­вой куче один ка­мень. При этом наи­боль­шее сум­мар­ное ко­ли­че­ство кам­ней в обеих кучах, ко­то­рое можно по­лу­чить за 4 хода, равно 9 + 64 = 73.

При S = 17. Петя пер­вым ходом может по­лу­чить по­зи­цию (7, 18). Из этой по­зи­ции Ваня может по­лу­чит по­зи­ции (8, 18), (7, 19), (14, 18) и (7, 36). В по­зи­ции (7, 36) Петя вы­иг­ры­ва­ет своим вто­рым ходом. В осталь­ных по­зи­ци­ях у Пети есть стра­те­гия, ко­то­рая поз­во­ля­ет ему по­лу­чить по­зи­ции, из ко­то­рых Ваня не смо­жет вы­иг­рать своим вто­рым ходом.

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