116 Найди выигрышную стратегию в игре Камешки (начальная позиция 15, разрешается брать 1, 3 или 4 камешка). Для этого исследуй все позиции игры, раскрась числовую линейку (можно вырезать заготовку числовой линейки со вкладыша тетради проектов). Выясни, у кого из игроков есть выигрышная стратегия. Построй последовательность такой партии, в которой этот игрок следует выигрышной стратегии, а его противник на каждом ходу берёт один камешек.
Играем в «Камешки», где можно брать 1, 3 или 4 камня за ход. Нужно определить выигрышные и проигрышные позиции, чтобы выяснить стратегию.
Шаг 1. Определение проигрышных позиций Проигрышной считается такая позиция, из которой любой ход приводит к выигрышу соперника. Начнём с нулевой позиции (0 камней) — это явно проигрышная, так как ходить больше нельзя.
Теперь проверяем позиции, из которых можно привести противника к проигрышу:
1 камень → единственный возможный ход приводит к 0 (проигрышная). 3 камня → можно взять 3 и оставить 0 (проигрышная). 4 камня → можно взять 4 и оставить 0 (проигрышная). Значит, позиции 0, 1, 3 и 4 — проигрышные.
Шаг 2. Определение выигрышных позиций Выигрышными считаются те, из которых можно перевести противника в проигрышную.
2 камня → берём 1 камень, остаётся 1 (проигрышная) → 2 — выигрышная. 5 камней → берём 4 камня, остаётся 1 (проигрышная) → 5 — выигрышная. 6 камней → берём 1 камень, остаётся 5 (выигрышная) → 6 — выигрышная. 7 камней → берём 3 камня, остаётся 4 (проигрышная) → 7 — выигрышная. 8 камней → можно взять 1, 3 или 4, но все оставляют выигрышные позиции (2, 5, 4) → 8 — проигрышная. Продолжая аналогично:
9 — выигрышная (берём 1 → 8) 10 — выигрышная (берём 1 → 9) 11 — выигрышная (берём 3 → 8) 12 — проигрышная (все возможные ходы ведут к выигрышным позициям) 13 — выигрышная (берём 1 → 12) 14 — выигрышная (берём 1 → 13) 15 — выигрышная (берём 3 → 12) Шаг 3. Построение выигрышной стратегии Так как 15 — выигрышная позиция, первый игрок может победить. Лучший ход: взять 3 камня, оставить 12 (проигрышную). Далее противник ходит (берёт 1), остаётся 11. Теперь берём 3 → остаётся 8 (проигрышная). Противник ходит (берёт 1), остаётся 7, а затем выигрываем.
Выигрышная последовательность:
15 → 12 (берём 3) 12 → 11 (противник берёт 1) 11 → 8 (берём 3) 8 → 7 (противник берёт 1) 7 → 4 (берём 3) 4 → 3 (противник берёт 1) 3 → 0 (берём 3) – победа.
117 Найди выигрышную стратегию в игре Камешки (начальная позиция 14, разрешается брать 1, 3 или 4 камешка). Можешь воспользоваться числовой линейкой, уже раскрашенной в ходе решения задачи 116. Выясни, у кого из игроков есть выигрышная стратегия в этой игре, сформулируй выигрышную стратегию.
Воспользуемся уже определёнными выигрышными и проигрышными позициями.
14 — выигрышная, так как можно пойти на 11 (проигрышную).
Стратегия:
14 → 11 (берём 3) 11 → 10 (противник берёт 1) 10 → 7 (берём 3) 7 → 6 (противник берёт 1) 6 → 3 (берём 3) 3 → 0 (берём 3) – победа.
118 Найди выигрышную стратегию в игре Камешки (начальная позиция 214, разрешается брать 1 или 2 камешка). Для решения необязательно раскрашивать числовую линейку от 0 до 214 целиком. Вместо этого можно:
1) раскрасить позиции от 0 до 15;
2) найти закономерность расположения проигрышных позиций на числовой прямой;
3) определить, какой будет начальная позиция, а значит, выяснить, у кого из игроков есть выигрышная стратегия;
4) сформулировать выигрышную стратегию, не перечисляя проигрышные позиции, а описывая их.
Играем в «Камешки», где можно брать 1 или 2 камня. Определяем выигрышные и проигрышные позиции.
Шаг 1. Определяем проигрышные позиции (раскрашиваем от 0 до 15) Проигрышная позиция — та, из которой любой ход ведёт к выигрышу соперника.
0 камней — проигрышная (ходить нельзя). 1 камень — можно взять 1 и оставить 0 → выигрышная. 2 камня — можно взять 2 и оставить 0 → выигрышная. 3 камня — можно взять 1 и оставить 2 (выигрышная) или 2 и оставить 1 (выигрышная) → проигрышная. 4 камня — можно взять 1 и оставить 3 (проигрышная) → выигрышная. 5 камней — можно взять 1 и оставить 4 (выигрышная) → выигрышная. 6 камней — можно взять 1 и оставить 5 (выигрышная) → выигрышная. 7 камней — можно взять 1 и оставить 6 (выигрышная) или 2 и оставить 5 (выигрышная) → проигрышная. 8 камней — можно взять 1 и оставить 7 (проигрышная) → выигрышная. 9 камней — можно взять 1 и оставить 8 (выигрышная) → выигрышная. 10 камней — можно взять 1 и оставить 9 (выигрышная) → выигрышная. 11 камней — можно взять 1 и оставить 10 (выигрышная) или 2 и оставить 9 (выигрышная) → проигрышная. 12 камней — можно взять 1 и оставить 11 (проигрышная) → выигрышная. 13 камней — можно взять 1 и оставить 12 (выигрышная) → выигрышная. 14 камней — можно взять 1 и оставить 13 (выигрышная) → выигрышная. 15 камней — можно взять 1 и оставить 14 (выигрышная) или 2 и оставить 13 (выигрышная) → проигрышная. Шаг 2. Закономерность проигрышных позиций Проигрышные позиции: 0, 3, 7, 11, 15, ... Видим, что они образуют арифметическую последовательность: 0, 3, 7, 11, 15, … с шагом +4.
То есть любая позиция вида 4n + 3 (где n — целое число) является проигрышной.
Шаг 3. Определяем, выигрышная ли позиция 214 Проверяем, попадает ли 214 в проигрышные: 214 = 4 × 53 + 2.
Так как оно не вида 4n + 3, значит, 214 — выигрышная позиция.
Шаг 4. Выигрышная стратегия Первый игрок может перевести соперника в проигрышную позицию (4n + 3). Ближайшее к 214 проигрышное число — 211.
Выигрышный ход: взять 3 камня (214 → 211).
После этого соперник окажется в проигрышной позиции, и, следуя стратегии, первый игрок всегда сможет оставить его в такой ситуации.
Вывод: первый игрок выигрывает, если в первом ходе берёт 3 камня, оставляя 211. Далее он каждый раз переводит соперника в следующую проигрышную позицию.
119 Робот находится в центре коридора без боковых выходов, идущего в неизвестном направлении: вертикальном (идущего вверх-вниз) или горизонтальном (идущего вправо-влево).
Составь алгоритм, выводящий Робота из коридора, если известно, что сейчас он находится на расстоянии не больше 15 шагов до каждого из двух выходов коридора.
нач если сверху свободно то нц 15 раз вверх кц иначе если снизу свободно то нц 15 раз вниз кц иначе если слева свободно то нц 15 раз влево кц иначе если справа свободно то нц 15 раз вправо кц все кон
120 Реши задачу.
Пятеро друзей встретились и обменялись рукопожатиями каждый с каждым. Сколько всего был рукопожатий?
Каждый из 5 друзей пожимает руку всем остальным, но при этом каждое рукопожатие учитывается дважды (один раз для каждого участника). Поэтому количество рукопожатий рассчитывается по формуле для сочетаний:
Количество рукопожатий = C(n, 2) = n! / (2!(n - 2)!)
Подставляем n = 5:
C(5, 2) = 5! / (2!(5 - 2)!) = (5 × 4) / 2 = 10
Ответ: 10 рукопожатий.
121 Даны правила игры Сотня.
Правила игры Сотня
Начальная позиция. Число 0.
Возможные ходы. На каждом ходу игрок прибавляет к имеющемуся числу любое целое число от 1 до 9 включительно.
Как определить победителя. Игра заканчивается, если позиция оказывается равной 100. При этом выиграл тот, кто прибавил последнее число.
Устройте соревнование с соседом по парте — сыграйте 4 партии в Сотню.
Начинайте игру по очереди: пусть один из вас играет Первым в партиях с чётными номерами, а другой — с нечётными. Заполни таблицу соревнования (образец такой таблицы дан в задаче 94, вырежи такую таблицу из вкладыша тетради проектов). За каждую победу игрок получает 1 очко, а за поражение — 0 очков. Сколько раз в вашем соревновании выиграл Второй?
Разбор стратегии: Ключевой момент — кто окажется в позиции 91. Если игрок делает ход и получает число 91, он гарантированно выигрывает, потому что следующим ходом может прибавить число от 1 до 9 и получить 100.
Чтобы попасть в 91, нужно встать на 82 (потому что 82 + любое число от 1 до 9 даст 91). Чтобы попасть в 82, нужно встать на 73, и так далее.
Выигрышные позиции: 91, 82, 73, 64, 55, 46, 37, 28, 19, 10.
Кто выиграет?
Если Первый игрок ходит идеально, он всегда ставит Второго в проигрышную позицию и выигрывает. Если Первый игрок делает ошибку, Второй может воспользоваться выигрышной стратегией и победить.
122 Найди выигрышную стратегию в игре Сотня.
Для этого:
1) начни раскрашивать числовую линейку, начиная с заключительной позиции — от 100 до 78 (можно вырезать заготовку числовой линейки со вкладыша тетради проектов);
2) найди закономерность расположения проигрышных позиций на числовой прямой;
3) определи, какой будет начальная позиция — выигрышной или проигрышной, а значит, выясни, у кого из игроков есть выигрышная стратегия;
4) сформулируй выигрышную стратегию.
Для поиска выигрышной стратегии нужно определить выигрышные и проигрышные позиции.
Шаг 1. Определяем проигрышные позиции Проигрышная позиция — это такая, из которой любой ход приводит противника в выигрышную позицию.
Начнем с конца:
100 — это победа. Значит, 99–91 — выигрышные позиции, потому что можно прибавить 1–9 и выиграть. 90 — проигрышная позиция, потому что любой ход приведет в 91–99, где противник победит. Двигаемся дальше:
89–81 — выигрышные, так как можно попасть в 90. 80 — проигрышная. 79–71 — выигрышные (можно поставить противника в 80). 70 — проигрышная. Общая закономерность: проигрышные позиции — это числа 90, 80, 70, 60, 50, 40, 30, 20, 10.
Шаг 2. Определяем начальную позицию Число 0 — начальная позиция. Оно не совпадает с найденными проигрышными числами, значит, начальная позиция выигрышная. Это означает, что у Первого игрока есть выигрышная стратегия.
Шаг 3. Формулируем стратегию Если игрок оказывается в проигрышной позиции (10, 20, 30 и так далее), он всегда проигрывает при правильной игре противника. Выигрышная стратегия: поставить противника в ближайшую проигрышную позицию. Для этого на каждом ходу надо делать так, чтобы сумма чисел становилась равной 10, 20, 30 и т. д.
Пример:
Если число 76, надо прибавить 4, чтобы получить 80 (проигрышную позицию для противника). Если число 63, надо прибавить 7, чтобы получить 70. Так можно выигрывать гарантированно.
123 Построй последовательность бусин Г длины не меньше пяти, такую, чтобы все следующие утверждения не имели смысла для этой последовательности:
В последовательности Г седьмая бусина — красная треугольная.
В последовательности Г следующая бусина после каждой круглой — квадратная.
В последовательности Г предыдущая бусина перед каждой квадратной — треугольная.
Чтобы первое утверждение не имело смысла, в последовательности должно быть меньше семи бусин. Чтобы второе утверждение не имело смысла, в ней не должно быть круглых бусин или после круглой не должно стоять квадратной. Чтобы третье утверждение не имело смысла, в ней не должно быть квадратных бусин или перед квадратной не должно стоять треугольной.
Пример подходящей последовательности из пяти бусин:
Синий круг, красный треугольник, красный треугольник, синий круг, красный треугольник.
Здесь:
Всего пять бусин, а значит, утверждение о седьмой бусине теряет смысл. После каждой круглой бусины нет квадратной — утверждение не имеет смысла. Перед каждой квадратной нет треугольной, так как квадратных бусин вообще нет.
124 Дерево игры Ползунок (см. задачу 112) на поле 5 × 4 очень большое, оно не помещается на странице. Дерево L — это часть полного дерева игры, состоящая из некоторого элемента (т. е. позиции) А и всех элементов, в которые из А идут последовательности. Та ким образом, L есть дерево перебора всех возможных окончаний игры из позиции А.
Определи, какой игрок — Первый или Второй — должен ходить в позиции А. Затем определи, у кого из игроков есть выигрышная стратегия. Для этого:
1) перерисуй дерево L в тетрадь, заменив позиции их именами;
2) исследуй все позиции дерева L в учебнике и в тетради, имя каждой выигрышной позиции обведи красным, а проигрышной — синим;
3) определи, у кого из игроков есть выигрышная стратегия, и запиши эту стратегию в виде последовательности позиций.
Для решения этой задачи нужно:
Определить, чей ход в позиции A. Это можно узнать из условий задачи 112 (см. учебник). Перерисовать дерево L, заменив конкретные позиции их условными именами (например, A, B, C и т. д.). Определить выигрышные и проигрышные позиции. Выигрышные позиции обвести красным. Это те позиции, из которых игрок может попасть в проигрышную позицию противника. Проигрышные позиции обвести синим. Это те, из которых игрок вынужден оставить противнику выигрышную позицию. Определить, у кого из игроков есть выигрышная стратегия. Если A — выигрышная позиция, то выигрышная стратегия у Первого. Если A — проигрышная, то выигрышная стратегия у Второго. Записать выигрышную стратегию в виде последовательности позиций, например: A → B → C → ... → победа.
125 Даны правила игры Пешка.
Правила игры Пешка Начальная позиция. Игра ведётся на шахматной доске, пешка стоит на одном из полей (на каком именно поле — устанавливается дополнительными правилами). Возможные ходы. На каждом ходу игрок передвигает пешку на одно поле влево или на одно поле вниз. Как определить победителя. Игра заканчивается, если пешка оказывается в левом нижнем углу доски — на поле а1. Выигрывает тот игрок, который сделал последний ход. Исследуй игру Пешка. Попытайся объяснить, почему в этой игре выигрышная стратегия не нужна: победа не зависит от того, насколько умело играют игроки. При каких начальных позициях в игре Пешка выигрывает Первый и при каких — Второй?
Почему стратегия не нужна? Так как игроки могут только двигать пешку в одном из двух направлений, то у них нет возможности избежать поражения, если изначально проигрышная позиция.
Кто выигрывает? Первый игрок выигрывает, если пешка находится не на краю доски (то есть не на крайнем левом или нижнем ряду). В этом случае он может двигать пешку так, чтобы оставить Второму проигрышную позицию. Второй игрок выигрывает, если пешка изначально стоит на крайнем левом или нижнем ряду (но не в углу). Тогда Первый игрок сразу вынужден сделать ход, после которого Второй гарантированно приведёт пешку в угол a1. Если пешка уже находится в углу a1 в начале игры, то Первый игрок сразу побеждает, так как ему принадлежит первый ход.
126 а) Нарисуй, как разрезать многоугольник Q, чтобы получилось четыре одинаковых многоугольника.
б) Нарисуй, как разрезать многоугольник G, чтобы получилось два одинаковых многоугольника.
Смотри вложение вверху.
127 За один ход фишка может сдвинуться на одно поле влево или на одно поле вверх. Сколькими различными путями фишка может пройти по шахматной доске из поля с5 на поле а8, если будет двигаться только влево или вверх?
Фишка должна сделать 5 шагов: 2 влево и 3 вверх. Число способов расположить 2 шага влево среди 5 шагов вычисляется по формуле сочетаний:
C(5,2) = 5! / (2!(5-2)!) = (5 × 4) / (2 × 1) = 10.
Ответ: 10 путей.