Категория C3 • задача №1

 
 
 

Условие задачи

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

 

Найти:
кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

 

Решение

I этап: анализ условия задачи.

В игре принимает участие два игрока, для которых допустимы следующие операции:

  • удвоение количества камней в какой-либо куче;

  • добавление ровно два камня в любую из куч.

Условие победы в игре: суммарное количество камней в обеих кучах становится не менее 24 штук.

 

II этап: алгоритмизация задачи

Для решения поставленной задачи (для разбора игры) рассмотрим полное дерево игры, оформленное в виде табличной структуры, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа будут соответствовать количеству камней на каждом этапе игры в первой и второй кучах соответственно.

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

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

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

 

Рассмотрим схему развития дерева игры для варианта, когда первый игрок увеличил вдвое количество камней во второй куче.

Если первый игрок сходит (3, 12), то второй игрок непременно отвечает победным набором (3, 24).

 

Рассмотрим схему развития дерева игры для варианта, когда первый игрок добавил два камня в первую кучу.

Если второй игрок отвечает на ход первого игрока комбинацией (7, 6) или (5, 8), то игрок №1 побеждает не позднее V хода игры. Если второй игрок ходит как (10, 6) или (5, 12), то первый игрок побеждает не позднее III хода игры. То есть, в данной ветви игры всегда побеждает игрок под номером один.

 

Рассмотрим схему развития дерева игры для варианта, когда первый игрок добавил два камня во вторую кучу.

Как видно из вышеприведенного фрагмента дерева игры, на ход первого игрока (3, 8), второй игрок отвечает ходом (3, 10) и побеждает не позднее IV хода игры.

 

Выведем полное дерево игры:

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

 

Вывод:

при верной игре победит игрок №1. Для победы ему необходимо первым ходом прибавить два камня к первой куче

Резюме

  1. провели анализ условия задачи;

  2. дифференцировали развитие полного дерева игры на четыре направления;

  3. визуализировали полное дерево игры и провели соответствующие умозаключения.

 

Ответ:

I игрок, добавление двух камней в первую кучу

 
Рейтинг:
 
Проголосовало: 4
Количество просмотров: 1892
 
 
 

Категория C3 • задача №1

 

Комментарии

Для комментирования или зарегистрируйтесь
 

Остальные решения из билета №1 для подготовки к ЕГЭ по информатике 2013

 
Условие задачи
(наведите курсор мыши на ссылку)
Аудиовизуальное
решение
Мультимедийная
видеопрезентация
Решение в формате
слайд-шоу
Текстовое
решение
Категория A1
/sites/default/files/slides/inf/1211/inf_A1_01_01_t4S.jpg
Перейти Перейти Перейти Перейти
Категория A2
/sites/default/files/slides/inf/804/inf_A2_01_01_knN.jpg
Перейти Перейти Перейти Перейти
Категория A3
/sites/default/files/slides/inf/805/inf_A3_01_01_53B.jpg
Перейти Перейти Перейти Перейти
Категория A4
/sites/default/files/slides/inf/806/inf_A4_01_01_HXr.jpg
Перейти Перейти Перейти Перейти
Категория A5
/sites/default/files/slides/inf/877/inf_A5_01_01_phpTD0463.jpg
Перейти Перейти Перейти Перейти
Категория A6
/sites/default/files/slides/inf/1225/inf_A6_01_01_CRr.jpg
Перейти Перейти Перейти Перейти
Категория A7
/sites/default/files/slides/inf/890/inf_A7_01_01_Ado.jpg
Перейти Перейти Перейти Перейти
Категория A8
/sites/default/files/slides/inf/898/inf_A8_01_01_JJV.jpg
Перейти Перейти Перейти Перейти
Категория A9
/sites/default/files/slides/inf/2159/inf_A9_01_01_phpUpivnW.jpg
Перейти Перейти Перейти Перейти
Категория A10
/sites/default/files/slides/inf/2170/inf_A10_01_01_phpl32P1w.jpg
Перейти Перейти Перейти Перейти
Категория A11
/sites/default/files/slides/inf/994/inf_A11_01_01_KyH.jpg
Перейти Перейти Перейти Перейти
Категория A12
/sites/default/files/slides/inf/1295/inf_A12_01_01_TJK.jpg
Перейти Перейти Перейти Перейти
Категория A13
/sites/default/files/slides/inf/1310/inf_A13_01_01_VsS.jpg
Перейти Перейти Перейти
Категория B1
/sites/default/files/slides/inf/899/inf_B1_01_01_php1fwK8N.jpg
Перейти Перейти Перейти Перейти
Категория B2
/sites/default/files/slides/inf/2193/inf_B2_01_01_phpUx4Mvg.jpg
Перейти Перейти Перейти Перейти
Категория B3
/sites/default/files/slides/inf/2202/inf_B3_01_01_phpUx4Mvg.jpg
Перейти Перейти Перейти Перейти
Категория B4
/sites/default/files/slides/inf/1364/inf_B4_01_01_iKq.jpg
Перейти Перейти Перейти Перейти
Категория B5
/sites/default/files/slides/inf/1341/inf_B3_01_01_i5V.jpg
Перейти Перейти Перейти Перейти
Категория B6
/sites/default/files/slides/inf/2213/inf_B6_01_01_phpEyxdxU.jpg
Перейти Перейти Перейти Перейти
Категория B7
/sites/default/files/slides/inf/2221/inf_B7_01_01_phpo5DDL8.jpg
Перейти Перейти Перейти Перейти
Категория B8
/sites/default/files/slides/inf/2228/inf_B8_01_01_phpLRZYf4.jpg
Перейти Перейти Перейти Перейти
Категория B9
/sites/default/files/slides/inf/2250/inf_B9_01_01_phpqjzRBb.jpg
Перейти Перейти Перейти Перейти
Категория B10
/sites/default/files/slides/inf/2271/inf_B10_01_01_phpBoQYXv.jpg
Перейти Перейти Перейти Перейти
Категория B11
/sites/default/files/slides/inf/2281/inf_B11_01_01_phpi8udor.jpg
Перейти Перейти Перейти Перейти
Категория B12
/sites/default/files/slides/inf/2290/inf_B12_01_01_phpE00GlF.jpg
Перейти Перейти Перейти Перейти
Категория B13
/sites/default/files/slides/inf/2310/inf_B13_01_01_phpwzFLNF.jpg
Перейти Перейти Перейти Перейти
Категория B14
/sites/default/files/slides/inf/2324/inf_B14_01_01_php64fzgb.jpg
Перейти Перейти Перейти Перейти
Категория B15
/sites/default/files/slides/inf/2330/inf_B15_01_01_phpKZvkiX.jpg
Перейти Перейти Перейти Перейти
Категория C1
/sites/default/files/slides/inf/901/inf_C1_01_01_VWF.jpg
Перейти Перейти Перейти Перейти
Категория C2
/sites/default/files/slides/inf/902/inf_C2_01_01_DuJ.jpg
Перейти Перейти Перейти Перейти
Категория C4
/sites/default/files/slides/inf/904/inf_C4_01_01_kuu.jpg
Перейти Перейти Перейти Перейти
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?