128 Исследуй все позиции игры Король с начальной позицией h8:
1) раскрась шахматную доску, начиная с заключительной позиции — с клетки а1;
2) определи, выигрышной или проигрышной будет начальная позиция, а значит, выясни, у кого из игроков есть выигрышная стратегия.
1) Раскрась шахматную доску, начиная с заключительной позиции — с клетки a1.
Представим, что игра заканчивается, когда король оказывается на клетке a1. Король может двигаться в любую сторону на одну клетку. Теперь будем раскрашивать доску по принципу выигрыша и проигрыша:
a1 — проигрышная позиция (король не может никуда пойти — ходить дальше нельзя — проигрыш).
Клетки, с которых можно попасть в a1 за один ход (например, a2, b1, b2) — выигрышные.
Из каждой выигрышной клетки можно попасть в проигрышную.
Клетки, с которых можно попасть только в выигрышные — проигрышные.
И так далее, по очереди помечаем все 64 клетки, чередуя выигрыш и проигрыш, как в классической игре "Ним".
2) Определи, выигрышной или проигрышной будет начальная позиция h8.
Если h8 попадает на ту же «волну», что и a1, по очереди — например:
a1 — проигрышная (0 шагов)
b2 — выигрышная (1 шаг)
c3 — проигрышная (2 шага)
...
h8 — находится на расстоянии 7 по вертикали и 7 по горизонтали → минимальное количество ходов = 7 (вниз) + 7 (влево) = 14
Раз 14 — чётное число, то h8 — проигрышная позиция.
Значит, у второго игрока есть выигрышная стратегия.
129 Даны правила игры Ладья.
Начальная позиция. Игра ведётся на шахматной доске, ладья стоит на од ном из полей (на каком именно — устанавливается допол нительными правилами).
Возможные ходы. На каждом ходу игрок передвигает ладью на сколь ко угодно полей вправо или на сколько угодно полей вверх.
Как определить победителя. Игра заканчивается, если ладья оказывается в правом верхнем углу доски — на поле h8. Выигрывает игрок, который сделал последний ход.
Сыграй с соседом по парте две партии в игру Ладья с начальной позицией a1 и две партии с начальной позицией a2. Нарисуй на шахматной доске путь, который прошла ладья в ходе одной из сыгранных вами партий.
Начальные позиции:
Партия 1: начальная позиция a1
Партия 2: начальная позиция a1
Партия 3: начальная позиция a2
Партия 4: начальная позиция a2
Как определить выигрышную стратегию:
Ладья может двигаться только вверх или вправо, и выигрывает тот, кто первым попадает в h8.
Эта игра работает по принципу координат: Если в клетке (x, y), то при ходе можно сделать (x', y') — где x' > x или y' > y.
Клетки, где x = y, например: a1 (1,1), b2 (2,2), c3 (3,3), …, h8 (8,8) — проигрышные, потому что с них можно попасть только на выигрышные (где x ≠ y). Значит:
a1 (1,1) — проигрышная
a2 (1,2) — выигрышная (можно сходить в a1 и заставить соперника проиграть)
Вывод:
В игре с начальной позицией a1 выигрывает второй игрок.
В игре с начальной позицией a2 выигрывает первый игрок, если играет правильно.
Путь ладьи в партии (пример): Для партии с начальной позицией a2:
Ходы: a2 → a4 → c4 → h4 → h8 (на каждом ходу — только вправо или вверх)
130 Определи, при каких начальных позициях в игре Ладья выигрышная стратегия есть у Первого и при каких — у Второго:
1) раскрась шахматную доску, начиная с заключительной позиции — поля h8;
2) постарайся коротко описать, при каких начальных позициях выигрышную стратегию имеет Первый и при каких — Второй;
3) сформулируй выигрышную стратегию для Первого в игре с начальной позицией на поле a2;
4) сформулируй выигрышную стратегию для Второго в игре с начальной позицией на поле a1
1) Раскрась шахматную доску, начиная с заключительной позиции — поле h8
Поле h8 — это конечная, проигрышная позиция, потому что игра на этом ходе заканчивается. Клетки, из которых можно попасть в h8 за один ход (например, g8, h7, f8...) — выигрышные. Клетки, с которых можно попасть только на выигрышные — проигрышные. Так чередуем доску: если из клетки есть ход только на выигрышные — это проигрыш, если есть хотя бы один ход на проигрыш — это выигрыш.
2) При каких начальных позициях выигрывает Первый, а при каких — Второй
Координаты каждой клетки можно записать как (x, y), где x — номер столбца, y — номер строки (от a до h, от 1 до 8).
Проигрышные позиции — где x = y (a1, b2, c3, ..., h8). С этих клеток можно попасть только на выигрышные. Значит:
Если вы начинаете с клетки, где x ≠ y, вы можете пойти в (x, x) или (y, y) — это проигрышная клетка.
Первый выигрывает, если начальная позиция x ≠ y.
Второй выигрывает, если начальная позиция x = y.
3) Выигрышная стратегия для Первого с начальной позиции a2
Координаты a2 — (1, 2), x ≠ y → значит, это выигрышная позиция. Стратегия: на первом ходу переместить ладью на клетку a1 (1,1) — проигрышную. Теперь Второй в проигрыше, у него только ходы на выигрышные клетки. Далее просто копировать все его действия: если он идёт вверх, вы — вправо, и наоборот, чтобы снова вернуть его на диагональ.
4) Выигрышная стратегия для Второго с начальной позиции a1
Координаты a1 — (1,1), x = y → проигрышная позиция. Первый с нее не может попасть на другую проигрышную клетку. Он сделает ход на любую клетку с x ≠ y. Второй должен пойти в клетку с равными координатами (например, с b2 или c3), чтобы снова поставить Первого в проигрыш. Таким образом, стратегия — всегда возвращать ладью на клетку с x = y после хода соперника.
131 Даны правила игры Ферзь.
Начальная позиция. Игра ведётся на шахматной доске, ферзь стоит на одном из полей (на каком именно — устанавливается до полнительными правилами).
Возможные ходы. На каждом ходу игрок передви-гает ферзя на сколько угодно полей: влево, вниз или по диагонали влево-вниз.
Как определить победителя. Игра заканчивается, если ферзь оказывается в левом нижнем углу доски — на поле а1. Выигрывает игрок, который сделал последний ход.
Найди выигрышную стратегию в игре Ферзь с начальной по-зицией g8 и в той же игре с начальной позицией h5:
1) раскрась все поля шахматной доски, начиная с заключи-тельной позиции — поля а1;
2) для каждой из двух начальных позиций (g8 и h5) определи, какой она будет — выигрышной или проигрыш ной, а значит, у кого из игроков есть в игре с этой начальной позицией выигрышная стратегия;
3) сформулируй выигрышную стратегию для каждой из этих двух начальных позиций.
Выпиши имена шести полей, с начальными позици ями в которых в игре Ферзь выигрышная стратегия есть у Первого. Выпиши имена ещё шести полей, с начальными позициями в ко-торых в игре Ферзь выигрышная стратегия есть у Второго.
1) Раскрась все поля шахматной доски, начиная с поля a1
Поле a1 — проигрышное (игра на нём заканчивается). Клетки, из которых можно попасть в a1 за один ход (например, a2, b1, b2) — выигрышные. Далее по тому же принципу:
если можно попасть хотя бы на одну проигрышную — клетка считается выигрышной.
если можно попасть только на выигрышные — клетка проигрышная.
Так по очереди заполняется вся доска.
2) Определи, являются ли позиции g8 и h5 выигрышными или проигрышными
Для этого нужно посчитать, можно ли дойти в a1, делая только ходы вниз, влево или по диагонали влево-вниз.
g8 — координаты (7,8). Разность между столбцом и строкой — 1. Можно двигаться по диагонали: g8 → f7 → e6 → d5 → c4 → b3 → a2 → a1 Значит, это выигрышная позиция — можно сразу двигаться к цели.
h5 — координаты (8,5). Разность 3 — путь по диагонали не ведет сразу в a1, но можно идти: h5 → a5 → a1 или h5 → h1 → a1 Это тоже выигрышная позиция.
Значит, и g8, и h5 — выигрышные позиции.
3) Сформулируй выигрышную стратегию для этих двух начальных позиций
g8 — стратегия: идти по диагонали влево-вниз: f7 → e6 → d5 → c4 → b3 → a2 → a1 Так вы попадете в выигрышные клетки, и в конце завершите игру на a1.
h5 — стратегия: первый ход — в a5 или h1. Оба варианта — позволяют попасть в выигрышные клетки, с которых путь до a1 можно продолжать.
Шесть полей, где у Первого есть выигрышная стратегия (x ≠ y): a2, b1, h5, g8, b3, c5
Шесть полей, где выигрывает Второй (x = y): a1, b2, c3, d4, e5, f6
132 Построй часть дерева игры Ползунок с данной позицией в элементе первого уровня. По образцу, приведённому на странице 78, дай всем элементам полученного дерева имена и найди выигрышную стратегию окончания игры из этой позиции.
Для этого проведи исследование, как в задаче 124.
133 Найди выигрышную стратегию в игре Две кучи камешков с начальной позицией (4; 5): раскрась поле, начиная с заключительной позиции — клетки (0; 0), и определи, какой будет начальная позиция — выигрышной или проигрышной, а значит, у кого из игроков есть выигрышная стратегия. Запиши последовательность позиций какой-нибудь партии, в которой один из игроков использует выигрышную стратегию, а другой на первом своём ходу берёт по одному камешку из каждой кучи, а на следующем берёт один камешек из одной из куч (позиции обозначай парами чисел).
Как работает игра
На каждом ходу можно:
убрать любое количество камней из одной кучи,
или убрать одинаковое количество камней из обеих куч.
1) Раскраска: начнем с (0; 0)
(0; 0) — проигрышная позиция. С неё нельзя сделать ход.
Дальше: Любая позиция, с которой можно попасть в (0; 0), будет выигрышной. Значит:
(1; 0), (0; 1), (1; 1) — выигрышные, так как можно одним ходом прийти в (0; 0).
С них можно прийти только в проигрыш (0; 0), поэтому они выигрышные.
Теперь ищем проигрышные: это те, с которых все ходы ведут только в выигрышные.
Пример: (2; 2) → можно пойти в (1; 1), (0; 0), (2; 1), (2; 0), (1; 2), (0; 2) Так как можно попасть в (0; 0), (1; 1) — выигрышные, значит (2; 2) — проигрышная.
На практике: проигрышные позиции в этой игре — те, где количество камней в кучах одинаковое. То есть (0; 0), (1; 1), (2; 2), (3; 3), (4; 4), (5; 5)...
Вывод: Позиция (4; 5) — выигрышная, потому что 4 ≠ 5. Значит, у Первого игрока есть выигрышная стратегия.
2) Пример партии
Начальная позиция: (4; 5) — выигрышная. Один игрок играет по стратегии, другой — делает ходы "наугад".
Партия:
Первый (играет правильно): ход в (4; 4) — убирает 1 камень из второй кучи. (4; 4) — проигрышная (оставляет Второго без хорошего хода).
Второй (играет "наугад"): берёт по 1 камешку из каждой кучи → (3; 3) Но (3; 3) — снова проигрышная! Ошибка.
Первый: идёт в (0; 0) — убирает 3 из каждой кучи.
Игра закончена — Первый выиграл.
Последовательность позиций:
(4; 5) → (4; 4) → (3; 3) → (0; 0)
Если изначально кучки неравны — выигрывает Первый.
Стратегия: перевести в (x; x), чтобы соперник оказался в проигрышной позиции.
134 Построй два разных множества, для каждого из которых истинны все следующие утверждения:
Все элементы этого множества — двузначные нечётные числа.
Сумма цифр каждого числа из этого множества равна 10.
Самое большое число из этого множества на 1 меньше суммы всех остальных чисел из этого множества.
Подходят числа: 19, 37, 55, 73, 91 — все двузначные нечётные, сумма цифр равна 10.
1 множество: 19, 37, 55, 91 Сумма остальных: 19 + 37 + 55 = 111 91 = 111 - 1 → условие выполняется
2 множество: 37, 55, 91 Сумма остальных: 37 + 55 = 92 91 = 92 - 1 → условие выполняется
Ответ: Первое множество: 19, 37, 55, 91 Второе множество: 37, 55, 91
135 Составь алгоритм со следующим заголовком:
алг переход в противоположный угол
дано | Робот стоит в каком-то углу поля
| размером 10 × 14 клеток, на поле
| стен нет
надо | Робот перешёл в противоположный
| угол
Составь алгоритм с заголовком алг переход в противоположный угол, если Робот стоит в одном из углов поля 10×14, и на поле нет стен.
алг переход в противоположный угол нач пока снизу свободно вниз пока справа свободно вправо кон
136 Робот находится внутри тупика: горизонтального коридора без боковых выходов, закрытого с одного из концов (право го или левого — неизвестно). Составь алгоритм, выводящий Робота из этого коридора, если известно, что в начальном состоянии он находится на расстоянии 10 шагов до выхода из коридора и в 10 шагах до закрытого его конца.
алг выход из тупика нач шаги ← 0 пока шаги < 10 и слева свободно влево шаги ← шаги + 1 если слева не свободно шаги ← 0 пока справа свободно вправо кон
137 Реши задачу, используя поиск выигрышной стратегии в игре.
Алёша Попович и Добрыня Никитич воюют с девятиглавым змеем. По очереди богатыри ходят к его пещере и отрубают 1, 2 или 3 головы. Как начавшему бой Алёше обрести славу победителя змея (отрубить последнюю голову)?
Алёше нужно оставить после своего хода количество голов, кратное 4. Это делает Добрыню уязвимым, так как как бы он ни ходил (1, 2 или 3 головы), Алёша снова вернёт ситуацию к числу, кратному 4.
Ход Алёши в начале: 9 - 1 = 8 голов
Теперь Алёша всегда отвечает так, чтобы сумма с Добрыней равнялась 4:
Если Добрыня отрубил 1 → Алёша рубит 3 Если Добрыня отрубил 2 → Алёша рубит 2 Если Добрыня отрубил 3 → Алёша рубит 1
Последнюю голову отрубит Алёша.
138 Найди выигрышную стратегию в игре Камешки (начальная позиция 10, разрешается брать 1, 2 или 3 камешка).
Для этого исследуй все позиции игры, раскрась числовую линейку. Выясни, у кого из игроков есть выигрышная стратегия.
Построй последовательность позиций такой партии, в которой игрок следует выигрышной стратегии, а его противник на каждом ходу берёт 2 камешка.
1. Раскраска позиций:
Начинаем с позиции 0 (нет камешков) — проигрышная, т.к. взять нечего. Позиции: 0 — проигрыш 1 — выигрыш (можно взять 1 и победить) 2 — выигрыш (взять 2 и победить) 3 — выигрыш (взять 3 и победить) 4 — проигрыш (после любого хода соперник попадает в выигрыш) 5 — выигрыш (берём 1 → 4 — проигрыш) 6 — выигрыш (берём 2 → 4) 7 — выигрыш (берём 3 → 4) 8 — проигрыш (любое действие → 5, 6, 7 — выигрыш) 9 — выигрыш (берём 1 → 8) 10 — выигрыш (берём 2 → 8)
Выигрышная стратегия с позиции 10:
Игрок-1: 10 → 8 (берёт 2) Игрок-2: 8 → 6 (берёт 2) Игрок-1: 6 → 4 (берёт 2) Игрок-2: 4 → 2 (берёт 2) Игрок-1: 2 → 0 (берёт 2 и выигрывает)
Ответ: Игрок, начинающий с 10, выигрывает, если сразу берёт 2. Последовательность ходов: 10 → 8 → 6 → 4 → 2 → 0.
139 Прочитай описание игры Назови 26.
Играют двое.
Первый игрок называет любое натуральное число, не превосходящее 4, т. е. одно из чисел 1, 2, 3, 4.
Второй игрок прибавляет к названному числу своё число, также не превосходя щее 4.
К этой сумме первый прибавляет какое-либо натуральное число, не превосходящее 4, и сообщает сумму и т. д.
Выигрывает тот, кто первым достигнет числа 26.
Сформулируй правила этой игры как игры с полной информацией. Найди выигрышную стратегию в этой игре.
Правила как для игры с полной информацией:
На старте — число 0. Игроки по очереди прибавляют к текущему числу любое число от 1 до 4. Побеждает тот, кто первым назовёт число 26.
Анализ стратегии:
Пусть выигрышная позиция — когда ты можешь своим ходом дойти до 26. Значит, 22 — проигрышная позиция (с неё соперник может добраться до 26, прибавив 4). Тогда 21, 20, 19, 18 — выигрышные (прибавляем 4, 3, 2, 1 и попадаем в 22). 17 — проигрышная. 16, 15, 14, 13 — выигрышные. 12 — проигрышная. ... и так далее.
Получаем, что проигрышные позиции: 0, 5, 10, 15, 20, 22 (каждые 5 шагов, начиная с 0, но с поправкой на 22 — ключевая проигрышная перед 26).
Выигрышная стратегия:
Первый игрок должен сделать так, чтобы после его хода получилось 5, 10, 15, 20 или 22. Тогда он вынудит второго попасть в проигрышную позицию.
Пример стратегии:
Первый называет 1. Соперник прибавляет 3 → 4. Первый прибавляет 1 → 5 (проигрышная позиция для второго). Соперник что ни возьми (до 4) — максимум будет 9. Первый прибавляет так, чтобы снова попасть в 10.
И так до 26.
Вывод: Побеждает тот, кто первым приводит игру к числам 5, 10, 15, 20 или 22. Выигрышная стратегия у Первого — начать с 1.
140 Нарисуй в тетради по клеткам два разных прямоугольных треугольника, площадь каждого из которых равна 12 ед. кв.
Площадь прямоугольного треугольника: (основание × высота) / 2 = 12, значит, основание × высота = 24.
Подходящие пары: 1 и 24 2 и 12 3 и 8 4 и 6 6 и 4 8 и 3 12 и 2 24 и 1
Например:
Основание — 6 клеток, высота — 4 клетки
Основание — 3 клетки, высота — 8 клеток