Построение дерева игры
Предмет: Математика, 5 класс
Автор: Вольфсон Георгий Игоревич

Всем привет!

Сегодня речь снова пойдёт о деревьях. Нет, не о тех, которые растут в парке, а о тех, которые помогают перебрать варианты. Как вы помните, именно с помощью дерева вариантов мы решали разные задачи на количество способов. А сегодня мы увидим, как дерево может помочь в математической игре. Сразу начнём с примера.

Задача 1. Хулиган Вася посетил лифт соседского 100-этажного дома, и теперь там работают только две кнопки: «–9» и «+7». Можно ли, пользуясь этим лифтом, попасть:
a) С 1-го этажа на 2-ой?
b) Со 2-го этажа на 1-ый?

Решение. Прежде всего, оговоримся. Речь идёт не совсем о классическом понимании математической игры. Здесь также есть правила, однако игрок лишь один и играет он сам с собой. Он может либо выиграть – попасть на нужный этаж, либо проиграть – не попасть. Как же решить такую задачу?

Давайте не особо мудрствовать! Разберём все варианты. Исходно (п. а) мы на 1 этаже. С него можно попасть только на 8. Оттуда – только на 15. Далее – либо на 22, либо на 6. Давайте изобразим это в виде дерева:

Обратите внимание, что одинаковые вершины я отмечал кружочками: действительно, если я смог один раз попасть на 13 этаж, то нет смысла вести от второго числа 13 такие же ветки, зачем повторяться?

Итак, мы сможем попасть с первого этажа на второй. Сделать это можно с помощью «ходов»: 1–8–15–6–13–4–11–2. Заодно, кстати, мы смогли попасть ещё на массу этажей: 4, 6, 8, 11, 13, 15, 18, 20, … Как видите, думать нам почти не пришлось, мы лишь перебрали все варианты. И думаю, вы со мной согласитесь, что с помощью дерева перебор стал гораздо более наглядным и простым.

Можно ли было поступить иначе, не рисуя дерево? Да, есть и другое решение. Можно, например, заметить, что комбинация «+7–9» уменьшает номер этажа на 2. Значит нужно просто попасть на любой чётный этаж (с 1 на 8 первым ходом), а затем 3 раза сделать последовательность «+7–9», попадая на 2 этаж. Красиво, конечно, но это ж поди придумай! А если рисуешь дерево всех вариантов – мимо правильного ответа не пройти!

Перейдем к пункту б). Сделаем аналогично:

Нашли ошибку? Конечно, минус второй этаж условием вряд ли предусмотрен, молодцы. А ещё заметьте, что я оформил дерево чуть иначе: совпадающие варианты я не обводил в кружочек, а сразу объединял в один. Кроме того, я сразу заметил, получив 10, что следующим ходом могу попасть на 1, так что рисовать остальные ветки мне уже не нужно. Кстати, как и в первом пункте, можно было решить и без дерева. Справитесь? А мы едём дальше. Давайте посмотрим, как работает идея полного дерева вариантов в математических играх с двумя игроками.

Задача 2. На столе лежит 5 спичек. За ход можно взять одну или две спички. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Решение. Нарисуем дерево этой игры.

Итак, получается 4 ветки. В двух из них выигрывает первый, а в двух других – второй. Что же из этого следует? А то, что первому, конечно, надо оставлять 3 спички! Ведь если он оставит 4. То второй возьмёт одну и попадет в одну из двух левых веток, в которых он выигрывает. А вот если первый берёт 2, то остаётся 3 спички. Второй берёт одну либо две, после чего первый выигрывает.

Разумеется, эту задачу можно было решить и с помощью анализа выигрышных и проигрышных позиций, после чего стратегия стала бы очевидной. Но можно решать и так, с помощью дерева. Впрочем, думаю, вы уже увидели основной минус такого хода решения: когда числа побольше, то вариантов будет слишком много. Скажем, будь спичек не 5, а 20 – дерево бы слишком разрослось… Кстати, на эту тему вот вам такая задачка:

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

Решение. На самом деле, ходов, конечно, больше 10: даже в начальной позиции, когда все фигуры закрыты, каждый игрок может сделать по два хода каждой пешкой и по два хода конём – итого 20 ходов. Но для простоты вычислений, сделаем более удобное число. Что же получается?

После первого хода первого игрока дерево содержит 10 веток. На каждый ход первого есть 10 ответов второго – уже 100 вариантов по правилу произведения. Дальше будет 1000, затем 10 000, и так далее. Сколько же получится всего? Нужно 10 умножить на себя столько раз, сколько ходов сделано (2 раза по 10, то есть 20). Значит, получится 100 000 000 000 000 000 000 веток! И это только первые десять ходов, при том, что мы сильно сократили количество вариантов для каждого игрока. Именно поэтому даже сейчас, когда компьютеры имеют огромные возможности, шахматы – не просчитанная игра, ведь перебрать столько вариантов не под силу даже самому быстрому компьютеру. Впрочем, это пока не под силу, кто знает, что будет через 10 лет?

Кстати, вы заметили небольшую неточность в моём рассуждении? На порядок величины это не влияет, и всё же. Мы не учитываем, что одна и та же позиция может получиться после разных ходов! Те самые «кружочки», в которые мы обводили одни и те же этажы, помните? Впрочем, повторюсь, мы сильно приуменьшили количество ходов каждого игрока, так что такую вольность мы вполне можем себе позволить.

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

3) Они не нашлись ни там, ни там. Тогда нужно вспомнить, где вы их видели в последний раз, поискать другие места, где вы могли их забыть

Таким образом, с помощью дерева всех вариантов у нас получается структурировать и систематизировать какие-то данные. И это, зачастую помогает, как в задачах – так и в жизни! Пользуйтесь! До встречи!

Дополнительная информация

Рекомендуемые тренажёры:

1. Хулиган Вася посетил лифт соседского 100-этажного дома, и теперь там работают только две кнопки: «–8» и «+5». Можно ли, пользуясь этим лифтом, попасть с 1-го этажа на 2-ой? Ответ: да.

2. На столе лежит 6 спичек. За ход можно взять одну или две спички. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре? Ответ: второй.

3. Предположим, что каждый раз у каждого игрока в шашки есть 5 вариантов ходов. Сколько веток будет у дерева игры в шашки после первых 5 ходов каждого из игроков? Повторением позиций можно пренебречь.

Рекомендуемые тесты:

1. Хулиган Вася посетил лифт соседского 100-этажного дома, и теперь там работают только две кнопки: «–12» и «+9». Можно ли, пользуясь этим лифтом, попасть с 1-го этажа на 2-ой? Ответ: нет.

2. На столе лежит 6 спичек. За ход можно взять одну или три спички. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре? Ответ: второй.

3. Два игрока ходят по очереди. Перед началом игры у них есть а) по две б) по три горошины. Ход состоит в передаче сопернику любого числа горошин. Не разрешается передавать такое количество горошин, которое до этого уже кто-то в этой партии передавал. Ноль горошин тоже передавать нельзя. Тот, кто не может сделать очередной ход по правилам, — считается проигравшим. Кто – начинающий или его соперник – победит в этой игре, как бы ни играл его партнёр? Ответ: в обоих случаях выиграет второй.