Шоколадное занятие

Игорь Акулич
«Квантик» №7, 2019

— Уверен, что сегодняшнее занятие придётся вам по вкусу, причём в буквальном смысле. Потому что я принёс на него... посмотрите что?

— Шоколадку!

— И занятие, естественно, будет шоколадным. Сейчас разверну... Обратите внимание — это не просто шоколадка, а прямоугольная шоколадка, разделённая углублениями на одинаковые дольки. Шесть долек в длину и четыре в ширину — итого 24 дольки.

Но не думайте, что вы её съедите — и на этом всё. Сначала придётся потрудиться — так сказать, соединить приятное с полезным. А именно — поиграем.

Правила таковы. Играют двое, ходят по очереди. Сначала первый игрок разламывает шоколадку вдоль одного из углублений на две части, выбирает одну из частей и даёт её съесть второму, затем второй разламывает остаток шоколадки вдоль углубления на две части и даёт первому съесть одну из частей, и так они ломают по очереди, пока это возможно. Если осталась единственная долька, то она просто отдаётся на съедение сопернику, и на этом всё заканчивается. Цель каждого — съесть как можно больше долек. Требуется выяснить, кто победит и с каким перевесом, если оба будут играть наилучшим образом (перевесом будем называть разность количества съеденных долек у победителя и проигравшего).

Разумеется, дать ответ требуется для шоколадки произвольных размеров, у которой вдоль одной стороны помещается m долек, а вдоль второй — n долек (где m и n — натуральные, причём m ≥ n). Какие идеи?

— У второго есть преимущество! Он наверняка не проиграет!

— Это почему?

— А давайте разобьём ходы на пары. Второй игрок в ответ на каждый ход первого всегда может отломить и отдать сопернику кусок шоколадки, не больший того, который он только что от него получил. Ему надо лишь отломить кусок шириной в одну дольку вдоль той же стороны, вдоль которой только что ломал первый (а если ширина оставшегося куска равна одной дольке, то он должен отломить от него лишь одну дольку). То есть «по совокупности» при каждой паре ходов второму достанется не меньше долек, чем первому. Значит, и в целом за игру будет то же самое.

— А если число ходов нечётное? Тогда на пары не разобьёшь.

— И что? Здесь начинающему придётся сделать на один ход больше, но для него это лишь усугубляет ситуацию. Последнюю дольку он просто отдаст сопернику, ничего не получив взамен.

— Справедливо. Тогда поступим так. Обозначим через ƒ (m, n) разность количества долек, доставшихся второму, и долек, доставшихся первому (при наилучшей игре обоих). По сути, сейчас мы доказали, что ƒ (m, n) — число неотрицательное. Попробуете доказать ограничение с другой стороны: ƒ (m, n) ≤ m.

...Пауза...

— Не знаете, как подступиться? Ладно, подскажу. Пусть начинающий первым ходом отломит кусок шириной в одну дольку вдоль меньшей из сторон шоколадки. Тогда второй сразу же получает перевес в n долек, но дальше очередь хода уже за ним! Он как бы сам становится начинающим, и при дележе оставшейся части шоколадки уже его сопернику (то есть первому игроку) достанется не меньше долек, чем ему, и в итоге суммарный перевес второго никак не сможет превысить тот перевес, который был у него после первого хода начинающего — равный n.

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

...Долгая пауза...

— Есть ответ для квадратной шоколадки!

— И какой же он?

— ƒ (n, n) в точности равно n.

— Докажите.

— Опишем тактику второго, при которой он (при любой игре первого) получит перевес не меньше чем в n долек. А так как начинающий умеет добиваться, чтобы этот перевес был не больше n, при наилучшей игре обоих перевес будет ровно n.

Тактика может быть такая. Изначально шоколадка квадратная, и, отломив любой её кусок, начинающий нарушит эту «квадратность». Тогда второй должен её «восстановить», то есть отломить от перпендикулярной стороны кусок такой же ширины. Первый своим ходом снова её нарушит — а второй снова восстановит, и так до конца, пока не останется единичная долька, которую первый просто отдаст второму.

Рассмотрим пару ходов «нарушение-восстановление». Начинающий отламывает от любой стороны квадрата кусок шириной в Δ долек, а второй в ответ отламывает кусок шириной тоже Δ от меньшей стороны, снова получая квадрат (со стороной на Δ короче). Из рисунка видно, что за эту пару ходов перевес второго игрока увеличится на число долек квадрата Δ × Δ, что заведомо не меньше Δ. Тогда за всю игру перевес второго суммарно даст не меньше чем исходную величину стороны квадрата (так как сторона уменьшается от n до нуля). И чтобы перевес противника составил именно n (меньшего добиться невозможно), начинающий должен всё время отламывать полоску шириной в одну клетку.

— Отлично! Ещё есть достижения?

— По-моему, теперь можно доказать, что если m = n + 1, то ƒ (m, n) = 0. То есть игра закончится вничью!

— Выглядит удивительно. Давайте-ка подробней.

— Пусть шоколадка имеет размеры (n + 1) × n. Начинающий делает первый ход, отламывая кусок единичной ширины от короткой стороны, и сразу даёт второму перевес в n долек. Но шоколадка становится квадратной — n × n, а второй игрок — начинающим! И тогда первый, как описано выше, получит на квадратном остатке шоколадки перевес, равный тоже n, а в сумме n − n = 0. Вот и ничья!

— Эх, чуть не дотягивает для имеющейся шоколадки 6 × 4! А ещё успехи имеются?

— Да! Если n = 1, то ответ таков: ƒ (m, 1) = 1 для нечётных m и ƒ (m, 1) = 0 для чётных m.

— То есть здесь рассмотрена шоколадная «полоска» шириной в одну клетку.

— Да. И получается такая ситуация. В силу доказанного ранее, ƒ (m, 1) не превышает 1, то есть равно либо 0, либо 1. Пусть при некотором m величина ƒ (m, 1) = 1. Найдём ƒ (m + 1, 1). Здесь начинающий отламывает единичную дольку, давая второму перевес, равный 1, и второй превращается в начинающего, а первый становится вторым и далее «отыгрывает» этот перевес обратно. Поэтому ƒ (m + 1, 1) = 0.

Если же ƒ (m, 1) = 0, то для шоколадки (m + 1) × 1 первый может отломить кусок либо из одной дольки, либо из нескольких долек (двух или больше). Если он отломит одну дольку, то станет вторым, но перед ним «ничейная» плитка — перевеса на ней он не добьётся, и в сумме получится перевес второго, равный 1. Ну, а если он отломит не меньше двух долек, то перевес соперника сразу станет не меньше 2, и далее начинающий (ставший вторым) компенсирует из этого перевеса не больше 1, так что суммарный перевес соперника опять же не меньше 2 − 1 = 1. Получаются чередования: для шоколадки 1 × 1 — второй побеждает с перевесом 1, для 2 × 1 — ничья, для 3 × 1 — опять перевес второго равен 1, для 4 × 1 — снова ничья, и т.д.

— Что ж, для частных случаев мы рассмотрели немало. Складываются ли они у вас в какую-то систему? Что, не очень? Тогда не буду томить и сразу дам ответ: если m и n одной чётности и m ≥ n, то при наилучшей игре обоих игроков перевес второго равен n, а если m и n разной чётности, то будет ничья. При этом оптимальная стратегия каждого игрока — вполне логичное «жадное» поведение: при своём ходе отламывать полоску единичной ширины от меньшей стороны, чтобы соперник на этом ходу получил как можно меньше. Так что для нашей шоколадки перевес второго и составит ровно 4 дольки. Ну, кто готов сыграть со мной?

— Я!

— Я!

— ...

— Да, желающих куда больше, чем запасов продовольствия. Тогда просто поделим шоколадку на всех поровну. Как раз каждому по дольке и достанется.

Художник Алексей Вайнер