Игра Евклида Задачи

Правила — Игра Евклида

• В начале есть два числа.
• В свой ход вы вычитаете из большего числа кратное меньшего: один раз, два, три… сколько захочете.
• Результат не может быть отрицательным, поэтому число вычитаний ограничено.
• Побеждает тот, кто оставит ноль.

Уровни:

• Уровень 1 — числа до 25.
• Уровень 2 — числа до 60.
• Уровень 3 — числа до 200.

Против компьютера вы ещё выбираете, кто ходит первым. Это важно: из одних пар тот, кто ходит, выигрывает всегда, а из других — никогда.

Пара — 30 и 7. Меньшее число 7, значит можно убрать 7, 14, 21 или 28 — четыре разных хода, потому что 4 × 7 = 28 ещё помещается в 30, а 5 × 7 = 35 уже нет. Здесь выбран последний, и пара превращается в 7 и 2.

Откуда взялся выбор: большее число было больше меньшего более чем в четыре раза. Когда большее меньше двух меньших, ход всего один и решать нечего — игра идёт сама, пока отношение снова не вырастет.

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