Уроки 43–45. Выигрышные стратегии и большие числа

Материалы к урокам: лист определений «Выигрышные стратегии и большие числа», бумажные задачи 31–45 (2 часть), занятия 15 и 16 на Клавиатурном тренажере.

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

Выигрышные стратегии и большие числа

Вы, наверное, заметили, что кто-то из ваших ребят, решая задачи, относящиеся к предыдущему листу определений, начиная с некоторой позиции, раскрашивал позиции очень быстро, практически не задумываясь. Отдельные ученики, возможно, высказывали вам свои догадки о том, что иногда расположение выигрышных и проигрышных позиций на числовой линейке подчиняется некоторой закономерности. Ребятам приходилось встречаться с тем, что проигрышные и выигрышные позиции чередуются через одну, одна через две, одна через три и пр. В таких случаях можно формулировать выигрышную стратегию не пошагово, описывая каждый ход игры, а в виде общего правила, которое бы определяло, позиции какого вида должен оставлять противнику игрок, обладающий выигрышной стратегией. Такое общее правило не только делает описание выигрышной стратегии более коротким, но и освобождает нас от полного раскрашивания числовой линейки – мы раскрашиваем числовую линейку, пока не увидим закономерность. Особенно это актуально, если в начальной позиции камешков много: руководствуясь общей закономерностью определения выигрышной или проигрышной позиции, мы и в этом случае можем выяснить, кто обладает выигрышной стратегией и в чем она заключается.

Решение бумажных задач

Задача 31. Для начала ребята раскрашивают числовую линейку:


и замечают, что в распределении выигрышных и проигрышных позиций наблюдается некоторая закономерность – за каждой проигрышной позицией следует три выигрышных, затем снова одна проигрышная и т. д. Более того, видно, что все проигрышные позиции – это числа, делящиеся на 4. Именно поэтому в данной игре (как сказано в условии задачи) выигрышной стратегией обладает Первый (175 на 4 не делится, значит, позиция 175 – выигрышная). Таким образом, выигрышная стратегия Первого состоит в том, чтобы на каждом ходу забирать столько камешков, чтобы Второму доставалось число камешков, делящееся на 4.

Задача 32. Здесь ребята должны научиться следовать открытой в предыдущей задаче выигрышной стратегии для победы в соревновании. Как видите, раскрашенной линейки им для этого не хватит, поэтому они будут вынуждены следовать общему правилу, которое выражено в ответе к задаче 31. Для начала ребятам необходимо понять, что Первый должен выбирать начальные позиции, которые не делятся на 4 (подробнее см. комментарий к бумажной задаче 23).

Задача 33. Ребята работают с этой задачей аналогично задаче 31, но по возможности самостоятельно. Вот раскрашенная числовая линейка:


Ответ: Первый должен на каждом своем ходу забирать столько камешков, чтобы Второму доставалось число, делящееся на 3.

Задача 34. Повторяем лист определений «Раскрытие цепочки мешков».
Ответ:


Задача 35. Необязательная. Эта задача немного похожа на задачу про молоко и творог (см. часть 1, задача 53). Для решения этой задачи также могут помочь наглядные рисунки или схемы. Например, нарисуем ситуацию, соответствующую первому предложению задачи:

КАРАНДАШ + КАРАНДАШ+ ЛАСТИК =
= КАРАНДАШ + ЛАСТИК + ЛАСТИК + ЛАСТИК + ЛАСТИК

Теперь уберем (или вычеркнем) из обеих частей равенства пары одинаковых предметов (карандашей и ластиков). Получим новую схему:

КАРАНДАШ = ЛАСТИК + ЛАСТИК + ЛАСТИК

Получаем, что карандаш дороже ластика в 3 раза.

Задача 36. Сначала ребятам необходимо раскрасить начало числовой линейки:


Если после этого кто-то из учеников не будет знать, что делать, спросите его, какие позиции являются проигрышными. Когда ребенок поймет, что проигрышные позиции – числа, делящиеся на 3, можно спросить его, какой позицией (выигрышной или проигрышной) будет число 213. Оказывается, что проигрышной, значит, в данной игре выигрышная стратегия есть у Второго. Он должен на каждом своем ходу забирать столько камешков, чтобы противнику доставалось число, делящееся на 3.

Задача 37. Необязательная. Три команды, уже заданные в программе, дают ребятам ключ к решению, поскольку на поле имеется лишь одна клетка, из которой Робот, не выходя за пределы закрашенной фигуры, может выполнить серию команд вниз–вверх– вверх: это центральная клетка второй строки. Следующий вопрос, который нужно решить детям: из какой клетки Робот начинал свой путь, если он добрался до упомянутой выше клетки за 4 команды? При этом нужно учитывать фигуру, которую закрасил Робот в процессе выполнения программы – нельзя выходить за ее пределы. Клетку положения Робота на поле в начальной позиции можно искать перебором. Таких возможных клеток оказывается две – вторая и шестая клетки второй строки. Отсюда возможных программ Т тоже две.
Ответ:


Или


Задача 38. Необязательная. Эта задача «с подвохом». Поскольку начальная позиция нечетная и все разрешенные ходы нечетные, то после любого хода Первого позиция будет четной, после любого хода Второго – нечетной. Таким образом, в данной игре всегда будет выигрывать Первый. По сути дела, выигрышная стратегия Первому вообще не нужна, однако это не значит, что ее нельзя найти формально. Кроме того, дети поймут, что всегда выигрывает Первый тоже далеко не сразу. Они начнут решать задачу по знакомому алгоритму:

1. Раскрасят числовую линейку (можно взять ее заготовку на вкладыше):


2. Заметят, что все проигрышные позиции – четные числа, а выигрышные – нечетные числа.

3. Запишут выигрышную стратегию формально – Первый должен на каждом своем ходу забирать столько камешков, чтобы Второму досталось четное число.

Лишь при выполнении последнего задания основная масса учащихся поймет, что в игре не может победить Второй. К этому выводу можно прийти, анализируя раскрашенную числовую линейку или из соображений четности-нечетности (подробнее см. в комментарии к бумажной задаче 19).

По окончании решения мы советуем провести общее обсуждение этого вопроса. Следует обратить внимание на то, что существуют игры, когда у игроков просто нет выбора (например, игры в Камешки с ходом 1), в этом случае выигрышная стратегия не нужна. Если кто-то из сильных детей поймет это еще до выполнения последнего задания и выскажет вам свои соображения, пусть пишет ответ в произвольной форме, например, так: «Первый выиграет всегда, какие бы ходы он ни делал» – или что-то в этом роде. Объяснение в последнем задании тоже пишется в произвольной форме, но лучше сначала все-таки выслушать соображения ребят и обобщить их.

Задача 39. Подобная задача ребятам уже встречалась (часть 1 задача 63), но в отличие от нее, эта задача является обязательной. Теперь уже все ребята должны понимать, что дело сводится к поиску выигрышной стратегии для Второго в игре в Камешки с начальной позицией 9 и разрешенными ходами 1, 2 и 3 камешка. В данном случае выигрышную стратегию требуется записать не в виде общего правила (хотя это несложно), а пошагово, поскольку ребята в итоге должны уметь делать и то и другое.
Ответ:
Шаг 1. Сначала Алеша должен отрубить 1 голову, тогда у змея останется 8 голов.
Шаг 2. Добрыня может отрубить 1, 2 или 3 головы, тогда у змея останется 7, 6 или 5 голов.
Шаг 3. Теперь Алеша должен отрубить столько голов, чтобы у змея осталось 4 головы.
Шаг 4. Добрыня может отрубить 1, 2 или 3 головы, тогда у змея останется 3, 2 или 1 голова.
Шаг 5. Алеша отрубает все оставшиеся головы змея и обретает славу победителя.

Задача 40. Эта задача – упрощенный вариант задачи 36 и решается она аналогично. Если вы чувствуете, что ребята справляются с такими задачами легко, можно использовать это задание для текущего контроля.
Ответ: выигрышная стратегия есть у Первого. Вот раскрашенная числовая линейка (красный цвет мы заменили серым, синий – белым):


Задача 41. Подобные задачи ребятам приходилось решать уже не раз. Проще всего начать с поиска одинаковых отрезков в цепочке V, а затем проверить выполнение условий о числе бусин в цепочке V и длине каждой из цепочек. Решений у этой задачи несколько. Здесь мы приводим два из них: в одном каждая из одинаковых цепочек имеет длину 3, в другом – длину 4 (при длине одинаковых цепочек 0, 1, 2 и 5 решение построить невозможно).
Ответ:


Задача 42. Необязательная. Ветка не нарисована полностью, а лишь «намечена»: во всех позициях, кроме корневой, нужно поставить еще крестики и нолики. Посоветуйте детям не спешить, если надо – начать строить дерево на отдельном листе бумаги (запасные поля есть на вкладыше) или работать в тетради карандашом. Затрудняющимся в решении можно задать следующие вопросы:

  1. Кто должен ходить из корневой позиции?
  2. Сколько у него есть возможных ходов?
  3. Есть ли среди этих ходов такой, который позволит выиграть сразу?

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

Следующие ходы крестиков также возникнут естественно. Учащиеся уже понимают, почему за корневой позицией у нас шло четыре позиции, а теперь за каждой позицией – только три. Важно сформировать здесь некоторую дисциплину работы, привычку к систематичности. В частности, полезно, как только сделан очередной выбор, т. е. дорисована позиция в одной из бусин, передать этот выбор «по цепочке», точнее, по ветке, начинающейся в данной позиции. Это потребует определенной аккуратности и сосредоточенности. Далее надо не забывать отмечать заключительные позиции – сразу рисовать стрелку и не пытаться что-то выстраивать за ними.

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


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

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


Задача 43. Проследите, чтобы все ребята справились с этой задачей самостоятельно. Можно использовать это задание для текущего контроля. Раскрасив числовую линейку, ребята замечают, что все позиции, делящиеся на 3, – проигрышные, а все остальные – выигрышные. Поэтому в первом случае выигрышная стратегия у Первого, а во втором – у Второго.

Задача 44. Необязательная. Мы уже встречались с аналогичной задачей (часть 1, задача 25) и советовали использовать ее как повод для знакомства с географической картой и атласом. Продолжим это знакомство. Попросите ребят принести на урок карты или атласы. В отличие от задачи 25, наша задача содержит дополнительное условие – все города должны принадлежать Российской Федерации. Поэтому в любом случае стоит начать решение задачи с разговора о том, что такое Российская Федерация, где она расположена, затем показать ее территорию и границы на большой карте. Чтобы не лишать детей удовольствия потренировать память и не разрушать специфику игры в Города, можно попросить их, не открывая карту, выписать на черновик названия городов, которые, по их мнению, входят в Российскую Федерацию. Теперь попросите ребят найти эти города на карте и проверить свои предположения. Возможно, кто-то из детей вспомнит небольшой городок, которого на карте нет. Тогда посоветуйте ему найти область, где расположен город, и убедиться, что эта область принадлежит Российской Федерации. Мы надеемся, что после этого у каждого ребенка на листочке останется список хотя бы из 8–10 названий. Теперь можно использовать карту для поиска на ней городов, которые в цепочке являлись бы связками между уже имеющимися городами или их заменой, если связать их никак не удается.

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

Заметки о названиях городов России

Из 87 центров субъектов Российской Федерации на букву К начинаются названия двенадцати, на С – восьми, на В, Н, П и Т – по шесть, на А, Б и М – по пять, на У и Ч – по четыре, на И и О – по три, на Г, Р, Х и Я – по два, на Д, Е, Й, Л, Э и Ю – по одному. На буквы Ё, Ж, З, Ф, Ц, Ш, Щ, Ы нет ни одного названия.

С концами этих названий дело обстоит совершенно иначе: здесь совсем не попалась частотная в начале буква С, 15 кончаются на А, а 25 – на К!

На Д начинается лишь малоизвестный поселок Дудинка, а кончается шесть городов, на А начинается 5, а кончается 15. Есть город, название которого кончается на Ы (Чебоксары), и это не такая уж редкость: в Московской области есть 4 таких города (Бронницы, Люберцы, Луховицы, Озеры).

Городов, начинающихся на Ы, в России нет, есть небольшие поселки городского типа Ыллымах и Ыныкчанский, а также райцентр село Ытык-Кюёль (все в Якутии), но обнаружить их на карте не просто.

Три названия кончаются на Й, начинается на Й только одна Йошкар-Ола, но это единственный такой населенный пункт на всю Россию.

Вот списки:
ПО АЛФАВИТУ:
1. Абакан
2. Агинское
3. Анадырь
4. Архангельск
5. Астрахань
6. Барнаул
7. Белгород
8. Биробиджан
9. Благовещенск
10. Брянск
11. Владивосток
12. Владикавказ
13. Владимир
14. Волгоград
15. Вологда
16. Воронеж
17. Горно-Алтайск
18. Грозный
19. Дудинка
20. Екатеринбург
21. Иваново
22. Ижевск
23. Иркутск
24. Йошкар-Ола
25. Казань
26. Калининград
27. Калуга
28. Кемерово
29. Киров
30. Кострома
31. Краснодар
32. Красноярск
33. Кудымкар
34. Курган
35. Курск
36. Кызыл
37. Липецк
38. Магадан
39. Майкоп
40. Махачкала
41. Москва
42. Мурманск
43. Назрань
44. Нальчик
45. Нарьян-Мар
46. Нижний Новгород
47. Новгород
48. Новосибирск
49. Омск
50. Орёл
51. Оренбург
52. Палана
53. Пенза
54. Пермь
55. Петрозаводск
56. Петропавловск-Камчатский
57. Псков
58. Ростов
59. Рязань
60. Салехард
61. Самара
62. Санкт-Петербург
63. Саранск
64. Саратов
65. Смоленск
66. Ставрополь
67. Сыктывкар
68. Тамбов
69. Тверь
70. Томск
71. Тула
72. Тура
73. Тюмень
74. Улан-Удэ
75. Ульяновск
76. Усть-Ордынский
77. Уфа
78. Хабаровск
79. Ханты-Мансийск
80. Чебоксары
81. Челябинск
82. Черкесск
83. Чита
84. Элиста
85. Южно-Сахалинск
86. Якутск
87. Ярославль
ПО КОНЦАМ:
А Вологда
А Дудинка
А Йошкар-Ола
А Калуга
А Кострома
А Махачкала
А Москва
А Палана
А Пенза
А Самара
А Тула
А Тура
А Уфа
А Чита
А Элиста
В Киров
В Псков
В Ростов
В Саратов
В Тамбов
Г Екатеринбург
Г Оренбург
Г Санкт-Петербург
Д Белгород
Д Волгоград
Д Калининград
Д Нижний Новгород
Д Новгород
Д Салехард
Е Агинское
Ж Воронеж
З Владикавказ
ИЙ Усть-Ордынский
К Архангельск
К Благовещенск
К Брянск
К Владивосток
К Горно-Алтайск
К Ижевск
К Иркутск
К Красноярск
К Курск
К Липецк
К Мурманск
К Нальчик
К Новосибирск
К Омск
К Петрозаводск
К Петропавловск-Камчатский
К Саранск
К Смоленск
К Томск
К Ульяновск
К Хабаровск
К Ханты-Мансийск
К Челябинск
К Черкесск
К Южно-Сахалинск
К Якутск
Л Барнаул
Л Кызыл
Л Орёл
ЛЬ Ставрополь
ЛЬ Ярославль
МЬ Пермь
Н Абакан
Н Биробиджан
Н Курган
Н Магадан
НЬ Астрахань
НЬ Казань
НЬ Назрань
НЬ Рязань
НЬ Тюмень
О Иваново
О Кемерово
П Майкоп
Р Владимир
Р Краснодар
Р Кудымкар
Р Нарьян-Мар
Р Сыктывкар
РЬ Анадырь
РЬ Тверь
Ы Чебоксары
ЫЙ Грозный
Э Улан-Удэ

Задача 45. Необязательная. Здесь ребята впервые сталкиваются с тем, что раскрашивать выигрышные и проигрышные позиции и строить выигрышные стратегии можно не только для игры в Камешки. Этот переход является важным, поэтому, несмотря на то, что задание необязательное, сильным учащимся предложить его стоит обязательно. Если время позволяет, можно сначала дать возможность ребятам, работающим с задачей, просто поиграть в эту игру, чтобы освоиться с правилами. После этого учащиеся раскрашивают начало числовой линейки (нарисованной на отдельном листочке). В данной игре начальная позиция – число 0, заключительная – число 100. Поэтому начинать раскрашивать линейку нужно с заключительной позиции 100 и раскрашивать позиции до тех пор, пока не выяснится общая закономерность чередования проигрышных и выигрышных позиций в данной игре.

Итак, 100 – проигрышная позиция для игрока, делающего ход (на предыдущем ходу противник назвал число 100 и уже выиграл). Позиция 99 – выигрышная, так как из нее за один ход можно получить проигрышную позицию 100, для этого нужно прибавить 1. Аналогично выигрышными являются позиции 98 – 91. Теперь рассмотрим позицию 90. В результате любого хода из позиции 90 получается выигрышная позиция (91, 92, …, 99), значит, позиция 90 – проигрышная. Так ребята движутся по числовой линейке, пока им не становится ясно, что проигрышные позиции – все числа, делящиеся на 10, а все остальные – выигрышные. Таким образом, позиция 10 – проигрышная, позиции 9, 8, 7, …, 1 – выигрышные, а ноль – проигрышная. Значит, выигрышная стратегия есть у Второго. Она заключается в том, чтобы на каждом своем ходу прибавлять такое число, чтобы в результате получалось число, делящееся на 10.