Главная страница

Анализ результатов егэ за 2013 год


Скачать 372.53 Kb.
НазваниеАнализ результатов егэ за 2013 год
Дата18.03.2023
Размер372.53 Kb.
Формат файлаdocx
Имя файла2glava_1.docx
ТипАнализ
#998479
страница3 из 5
1   2   3   4   5

Задание С3


Задание С3 относится к высокому уровню сложности. В данном проверяется умение строить дерево игры по заданному алгоритму и обосновывать выигрышную стратегию [15].

Теоретический материал для решения задания С3


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

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

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

Построить дерево игры – это значит рассмотреть для каждой позиции игры все возможные ходы игроков до тех пор, пока позиция не окажется выигрышной.

Разбор задания С3


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

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

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

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

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

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

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

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

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

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

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

Суть игры описана подробно, поэтому можно сразу переходить к заданиям и строить дерево игры.

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

  1. б) Из пункта 1 а) следует, что все значения при которых Петя не сможет выиграть в один ход находятся в промежутке от 1 до 15 включительно. Для того, чтобы при любом ходе Пети первым ходом выиграл Ваня, утроив полученное число, S изначально должно быть равно 15. В этом случае дерево игры может выглядеть следующим образом:



  1. Для того, чтобы Петя гарантированно выиграл вторым ходом, независимо от того, как будет ходить Ваня, нужно, чтобы после первого хода Пети число камней в куче стало 15. После очередного хода Вани, Петя выиграет утроив число камней в куче. То есть изначально в куче должно быть 14 или 5 камней. В этом случае дерево игры может выглядеть следующим образом:





  1. Ваня сможет гарантированно выиграть вторым ходом, если после хода Пети камней в куче будет 14. Соответственно, начальное количество камней в куче должно быть 13 для того, чтобы Петя своим первым ходом увеличил их либо до 14, либо до 39. Дальнейшие действия (для 14) описаны в п.2, а при 39 Ваня выиграет, увеличив число камней в куче в 3 раза. В этом случае дерево игры может выглядеть следующим образом:


Рекомендации к решению заданий С3


Для решения этого задания необходимо понимать, что представляет собой игра и правильно построить дерево игры.

Решить задание – значит грамотно ответить на вопросы, которые расположены в порядке увеличения сложности. При ответе на каждый вопрос нужно показать, что число камней в куче найдено верно и объяснить почему та или иная позиция является проигрышной или выигрышной для каждого игрока. Нужно указать все возможные проигрышные ходы для того, чтобы убедиться, что выигрышный ход найден верно. Важно не перепутать порядок игроков. Каждый ответ должен быть обоснован.

В этом задании при оценки не учитываются арифметические ошибки [14].
1   2   3   4   5


написать администратору сайта