СДАМ ГИА






Каталог заданий. Игра в камни, два варианта хода
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word
1
Задание 26 № 4570

Два игрока, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед ними лежат две кучки камней, в пер­вой из ко­то­рых – 4, а во вто­рой – 3 камня. У каж­до­го иг­ро­ка не­огра­ни­чен­но много камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. Ход со­сто­ит в том, что игрок или утра­и­ва­ет число кам­ней в какой-либо куче, или до­бав­ля­ет 2 камня в какую-либо кучу. Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство кам­ней в одной из куч ста­но­вит­ся не менее 19. Если в мо­мент за­вер­ше­ния игры общее число кам­ней в двух кучах не менее 35, то вы­иг­рал Ваня, в про­тив­ном слу­чае – Петя. Кто вы­иг­ры­ва­ет при без­оши­боч­ной игре обоих игроков? Каким дол­жен быть пер­вый ход вы­иг­ры­ва­ю­ще­го игрока? Ответ обоснуйте.

Источник: Демонстрационная версия ЕГЭ—2013 по информатике.
Пояснение · ·

2
Задание 26 № 4861

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

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

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

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

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

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

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

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

Источник: МИОО: Ди­а­гно­сти­че­ская работа по ин­фор­ма­ти­ке 14.12.2012 ва­ри­ант 3.
Пояснение · ·

3
Задание 26 № 4867

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

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

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

 

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

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

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

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

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


4
Задание 26 № 4877

Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 20. Если в момент завершения игры общее число камней в двух кучах не менее 36, то выиграл Ваня, в противном случае — Петя. Кто выигрывает при безошибочной игре обоих игроков? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.


5
Задание 26 № 4880

Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Игра завершается в тот момент, когда общее число камней в двух кучах становится не менее 31. Если в момент завершения игры общее число камней в двух кучах не менее 40, то выиграл Петя, в противном случае — Ваня. Кто выигрывает при безошибочной игре обоих игроков? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.


6
Задание 26 № 4884

Два игрока, Петя и Вася, иг­ра­ют в сле­ду­ю­щую игру. Перед ними лежат две кучки камней, в пер­вой из ко­то­рых 2, а во вто­рой — 1 камень. У каж­до­го игрока не­огра­ни­чен­но много камней. Иг­ро­ки ходят по очереди, пер­вым ходит Петя. Ход со­сто­ит в том, что игрок или уве­ли­чи­ва­ет в 3 раза число кам­ней в какой-то куче, или до­бав­ля­ет 3 камня в какую-то кучу. Вы­иг­ры­ва­ет игрок, после хода ко­то­ро­го в одной из куч ста­но­вит­ся не менее 24 камней. Кто вы­иг­ры­ва­ет при без­оши­боч­ной игре? Каким дол­жен быть пер­вый ход вы­иг­ры­ва­ю­ще­го игрока?

 

Ответ обоснуйте.


7
Задание 26 № 4958

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

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

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

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

 

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

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

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

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

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

 

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


8
Задание 26 № 5069

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

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

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

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

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

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

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

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

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

- у Вани есть вы­иг­рыш­ная стратегия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и при этом

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

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

Источник: МИОО: Тре­ни­ро­воч­ная ра­бо­та по ин­фор­ма­ти­ке 22.03.2013 ва­ри­ант ИНФ1401.

9
Задание 26 № 5225

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

 

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

 

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

 

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

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

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

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

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

 

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

- у Вани есть вы­иг­рыш­ная стратегия, поз­во­ля­ю­щая ему вы­иг­рать первым или вто­рым ходом при любой игре Пети, и при этом

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

 

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

Источник: МИОО:Диагностическая ра­бо­та по ин­фор­ма­ти­ке 18.04.2013 ва­ри­ант ИНФ1502.

10
Задание 26 № 5257

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

 

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

 

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

 

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

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

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

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

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

 

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

- у Вани есть вы­иг­рыш­ная стратегия, поз­во­ля­ю­щая ему вы­иг­рать первым или вто­рым ходом при любой игре Пети, и при этом

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

 

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

Источник: МИОО:Диагностическая ра­бо­та по ин­фор­ма­ти­ке 18.04.2013 ва­ри­ант ИНФ1501.

11
Задание 26 № 5322

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

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

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

 

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

 

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

 

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

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

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

Для указанных значений S опишите выигрышную стратегию Пети.

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

- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом

- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

 

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

Источник: МИОО: Тре­ни­ро­воч­ная работа по ин­фор­ма­ти­ке 17.05.2013 ва­ри­ант ИНФ1602.

12
Задание 26 № 5406

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

 

Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 47.

 

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

 

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

 

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

 

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

 

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

 

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

 

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

 

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Дальний Восток. Ва­ри­ант 2.

13
Задание 26 № 5438

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

 

Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 47.

 

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

 

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

 

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

 

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

 

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

 

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

 

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

 

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Дальний Восток. Ва­ри­ант 4.

14
Задание 26 № 5534

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Даль­ний Восток. Ва­ри­ант 3.

15
Задание 26 № 5566

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

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

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

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

 

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

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

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

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

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

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

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

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Даль­ний Восток. Ва­ри­ант 5.

16
Задание 26 № 6201

Два игрока, Паша и Вова, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Паша. За один ход игрок может до­ба­вить в кучу 1 камень или добавить в кучу 10 камней. Например, имея кучу из 7 камней, за один ход можно по­лу­чить кучу из 8 или 17 камней. У каж­до­го игрока, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство камней. Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 52. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 52 или боль­ше камней. В на­чаль­ный мо­мент в куче было S камней, 1 ≤ S ≤ 51.

 

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

 

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

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

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

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

Источник: МИОО: Тре­ни­ро­воч­ная работа по ин­фор­ма­ти­ке 08.10.2013 ва­ри­ант ИНФ10101.

17
Задание 26 № 6246

Два игрока, Паша и Вова, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Паша. За один ход игрок может до­ба­вить в кучу 1 камень или добавить в кучу 10 камней. Например, имея кучу из 7 камней, за один ход можно по­лу­чить кучу из 8 или 17 камней. У каж­до­го игрока, чтобы де­лать ходы, есть не­огра­ни­чен­ное количество камней. Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство камней в куче ста­но­вит­ся не менее 52. По­бе­ди­те­лем считается игрок, сде­лав­ший последний ход, то есть пер­вым получивший кучу, в ко­то­рой будет 52 или боль­ше камней. В на­чаль­ный момент в куче было S камней, 1 ≤ S ≤ 51.

 

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

 

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

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

 

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

 

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

Источник: МИОО: Тре­ни­ро­воч­ная работа по ин­фор­ма­ти­ке 08.10.2013 ва­ри­ант ИНФ10102.

18
Задание 26 № 6278

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

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 501.

19
Задание 26 № 6318

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

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 502.

20
Задание 26 № 6350

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

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 601.

21
Задание 26 № 6435

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

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 602.

22
Задание 26 № 6471

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

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 603.

23
Задание 26 № 6513

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

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

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 801.

24
Задание 26 № 6589

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

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

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

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

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

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

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

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

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

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 802.

25
Задание 26 № 6823

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

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

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

1. а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать в один ход? Ука­жи­те все такие значения.

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

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

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

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

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

Источник: МИОО: Тре­ни­ро­воч­ная работа по ин­фор­ма­ти­ке 20.02.2014 ва­ри­ант ИН10602.

26
Задание 26 № 6855

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

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

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

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

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

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

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

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

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

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


27
Задание 26 № 6970

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

Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 41.

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

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

встретиться при раз­лич­ной игре противника.

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

Задание 1.

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

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

Задание 2.

Укажите два таких зна­че­ния S, при ко­то­рых у Пети есть выигрышная

стратегия, причём од­но­вре­мен­но вы­пол­ня­ют­ся два условия:

- Петя не может вы­иг­рать за один ход;

- Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

Задание 3.

Укажите зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два условия:

- у Вани есть вы­иг­рыш­ная стратегия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

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

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

Источник: МИОО: Ди­а­гно­сти­че­ская ра­бо­та по ин­фор­ма­ти­ке 19.03.2014 Ва­ри­ант ИНФ10801.

28
Задание 26 № 7002

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

Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 42.

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

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

встретиться при раз­лич­ной игре противника.

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

Задание 1.

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

в один ход. Обоснуйте, что най­де­ны все нуж­ные зна­че­ния S, и ука­жи­те вы­иг­ры­ва­ю­щие ходы.

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

Задание 2.

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

- Петя не может вы­иг­рать за один ход;

- Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

Задание 3.

Укажите зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два условия:

- у Вани есть вы­иг­рыш­ная стратегия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

- у Вани нет стратегии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но выиграть

первым ходом.

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

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

Источник: МИОО: Ди­а­гно­сти­че­ская ра­бо­та по ин­фор­ма­ти­ке 19.03.2014 Ва­ри­ант ИНФ10802.

29
Задание 26 № 7215

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

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

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

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

встретиться при раз­лич­ной игре противника.

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

 

Задание 1

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

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

 

Задание 2

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

– Петя не может вы­иг­рать за один ход;

– Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

 

Задание 3

Укажите зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два условия:

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

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

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

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 05.05.2014. До­сроч­ная волна. Ва­ри­ант 1.

30
Задание 26 № 7384

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

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

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

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

встретиться при раз­лич­ной игре противника.

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

 

Задание 1

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

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

 

Задание 2

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

– Петя не может вы­иг­рать за один ход;

– Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

 

Задание 3

Укажите зна­че­ние S, при ко­то­ром одновременно вы­пол­ня­ют­ся два условия:

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

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

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

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 05.05.2014. До­сроч­ная волна. Ва­ри­ант 2.

31
Задание 26 № 7387

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

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

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

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

встретиться при раз­лич­ной игре противника.

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

 

1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения.

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

 

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

 

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

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


32
Задание 26 № 7388

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

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

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

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

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

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

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

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

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


33
Задание 26 № 7419

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

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

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

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

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

 

Задание 1

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

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

 

Задание 2

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

– Петя не может вы­иг­рать за один ход;

– Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

 

Задание 3

Укажите зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два условия:

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

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

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

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 08.05.2014. До­сроч­ная волна, ре­зерв­ный день. Ва­ри­ант 201.

34
Задание 26 № 7423

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

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

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

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

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

 

Задание 1

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

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

 

Задание 2

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

– Петя не может вы­иг­рать за один ход;

– Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

 

Задание 3

Укажите зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два условия:

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

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

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

 

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 08.05.2014. До­сроч­ная волна, ре­зерв­ный день. Ва­ри­ант 202.

35
Задание 26 № 7683

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

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

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

 

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

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

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

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

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

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

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

Источник: СтатГрад: Тре­ни­ро­воч­ная ра­бо­та по ин­фор­ма­ти­ке 26.11.2014 ва­ри­ант ИН10301.

36
Задание 26 № 7710

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

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

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

 

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

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

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

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

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

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

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

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

Источник: СтатГрад: Тре­ни­ро­воч­ная ра­бо­та по ин­фор­ма­ти­ке 26.11.2014 ва­ри­ант ИН10302.

37
Задание 26 № 7937

Два игрока, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. За один ход игрок может: до­ба­вить в кучу один ка­мень (действие А) или утро­ить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи один ка­мень (действие Б). Например, имея кучу из 10 камней, за один ход можно по­лу­чить кучу из 11 или 29 камней. У каж­до­го игрока, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство камней. Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 32. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 33 или боль­ше камней. В на­чаль­ный мо­мент в куче было S камней, 1 ≤ S ≤ 32.

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

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

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

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

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

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

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

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

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

Источник: СтатГрад: Тренировочная работа по ин­фор­ма­ти­ке 27.02.2015 ва­ри­ант ИН10901.

38
Задание 26 № 8002

Два игрока, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. За один ход игрок может: до­ба­вить в кучу один ка­мень (действие А) или утро­ить ко­ли­че­ство кам­ней в куче, а затем до­ба­вить ещё один ка­мень (действие Б). Например, имея кучу из 10 камней, за один ход можно по­лу­чить кучу из 11 или 31 камней. У каж­до­го игрока, чтобы де­лать ходы, есть неограниченное количество камней. У каж­до­го игрока, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство камней. Игра за­вер­ша­ет­ся в тот момент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 31. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 32 или боль­ше камней. В на­чаль­ный мо­мент в куче было S камней, 1 ≤ S ≤ 31.

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

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

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

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

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

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

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

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

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

Источник: СтатГрад: Тре­ни­ро­воч­ная работа по ин­фор­ма­ти­ке 27.02.2015 ва­ри­ант ИН10902.

39
Задание 26 № 9210

Два игрока, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. За один ход игрок может:

        добавить в кучу один камень (действие А) или

        утроить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (действие Б).

Например, имея кучу из 10 камней, за один ход можно по­лу­чить кучу из 11 или 28 камней. У каж­до­го игрока, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство камней.

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

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

 

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

 

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

1.

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

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

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

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

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

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

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

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

Постройте де­ре­во всех партий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таблицы). На реб­рах де­ре­ва указывайте, кто де­ла­ет ход, в узлах – ко­ли­че­ство кам­ней в позиции.

Источник: СтатГрад: Тренировочная работа по ин­фор­ма­ти­ке 06.05.2015 ИН10801

40
Задание 26 № 9318

Два игрока, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. За один ход игрок может:

        добавить в кучу один камень (действие А) или

        утроить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (действие Б).

Например, имея кучу из 20 камней, за один ход можно по­лу­чить кучу из 21 камня или из 58 камней. У каж­до­го игрока, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство камней.

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

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

 

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

 

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

1.

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

       б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за

один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

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

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

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

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

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

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

Постройте де­ре­во всех партий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таблицы). На реб­рах де­ре­ва указывайте, кто де­ла­ет ход, в узлах – ко­ли­че­ство кам­ней в позиции.

Источник: СтатГрад: Тре­ни­ро­воч­ная работа по ин­фор­ма­ти­ке 06.05.2015 ИН10802

41
Задание 26 № 10489

Два игрока, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му выбору) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. Например, пусть в одной куче 6 камней, а в дру­гой 9 камней; такую по­зи­цию в игре будем обо­зна­чать (6, 9). Тогда за один ход можно по­лу­чить любую из четырёх позиций: (12, 9), (7, 9), (6, 10), (6, 18). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство камней.

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

Будем говорить, что игрок имеет вы­иг­рыш­ную стратегию, если он может вы­иг­рать при любых ходах противника. Опи­сать стра­те­гию иг­ро­ка — зна­чит описать, какой ход он дол­жен сде­лать в любой ситуации, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре противника. Например, при на­чаль­ных по­зи­ци­ях (21, 30) и (41, 20) вы­иг­рыш­ная стра­те­гия есть у Пети. Чтобы выиграть, ему до­ста­точ­но удво­ить ко­ли­че­ство кам­ней во вто­рой куче.

Задание 1

Для каж­дой из на­чаль­ных по­зи­ций (10, 35), (6, 37) укажите, кто из иг­ро­ков имеет вы­иг­рыш­ную стратегию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стратегию; объясните, по­че­му эта стра­те­гия ведёт к выигрышу, и укажите, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стратегии.

Задание 2

Для каж­дой из на­чаль­ных по­зи­ций (10, 34), (5, 37), (6, 36) укажите, кто из иг­ро­ков имеет вы­иг­рыш­ную стратегию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стратегию; объясните, по­че­му эта стра­те­гия ведёт к выигрышу, и укажите, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стратегии.

Задание 3

Для на­чаль­ной по­зи­ции (5, 36) укажите, кто из иг­ро­ков имеет вы­иг­рыш­ную стратегию. Опи­ши­те вы­иг­рыш­ную стратегию; объясните, по­че­му эта стра­те­гия ведёт к выигрышу, и укажите, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стратегии. По­строй­те де­ре­во всех партий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стратегии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таблицы.

Источник: Типовые те­сто­вые за­да­ния по ин­фор­ма­ти­ке под ре­дак­ци­ей С. С. Крылова, Т. Е. Чуркиной. 2016. В. 1.

42
Задание 26 № 11322

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

Игра заканчивается, когда в куче не меньше 42 камней.

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

 

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

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

 

Задание 1

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

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

 

Задание 2

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

 

Задание 3

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

 

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

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

43
Задание 26 № 11326

Паша и Валя играют в следующую игру: перед игроками лежит куча камней, каждый игрок за один ход может добавить в кучу 1 камень или удвоить количество камней в куче. Камни для ходов не ограничены. Выигрывает тот игрок, после хода которого в кучу оказалось 24 и более камней, но не более 38. Если после хода игрока в куче более 38 камней, выигрывает его соперник. Первым ходит Паша.

Пусть S — начальное количество камней в куче.

а) При каких значениях S Паша может выиграть первым ходом?

б) У кого есть выигрышная стратегия при S = 20, 21, 22.

в) У кого выигрышная стратегия при S = 10, 11?

г) У какого игрока выигрышная стратегия при S = 9? Нарисуйте дерево решений.

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

44
Задание 26 № 11328

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 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? Опишите эту стратегию, постройте дерево ходов.

Источник: ЕГЭ 16.06.2016 по информатике. Основная волна.

45
Задание 26 № 11331

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

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

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

 

1) а) При каких значениях Паша выиграет 1 ходом. б) Кто выиграет при S=20, 19, 18.

2) Кто выиграет при S=10, 9.

3) Кто выиграет при S=8. Нарисуйте дерево партий.


Пройти тестирование по этим заданиям



     О проекте · Редакция

© Гущин Д. Д., 2011—2017


СПб ГУТ! С! Ф! У!