Конкурс "Математические игры" традиционно был адресован учащимся восьмого и более младших классов, и ребята с интересом играли между собой и с ведущими в тех местах проведения Турнира, где подобную интерактивность удалось организовать. Однако, задания в этом году оказались довольно сложными и представили бы интерес и для старшеклассников. Как обычно, у маленьких участников конкурса возникли сложности с изложением стратегии, в огромном большинстве работ просто написано, кто победит по мнению автора работы, приведены примеры партий. Невольно соотнося предлагаемые в задании достаточно условные и схематично-упрощённые математические игры с реальными, более богатыми возможностями, ребята ставили исход игры в зависимость от психологии и интеллекта игрока, взаимоотношений соперников. Вот характерные строки из работ: "Скорее всего ты проиграешь, если играешь с умным соперником", "Ошибка соперника и Ваша внимательность - ключ к успеху".
В результате проверки работ участникам выставлялись баллы как за полные решения задачи или её пунктов, так и за определённые продвижения в решении. Набравшие не менее 15 баллов стали победителями, получившие от 10 до 14 баллов были признаны достигшими в конкурсе неплохих результатов.
Эта игра исследуется так называемым методом выигрышных и проигрышных позиций. Позицией в игре служит данное первоначально или же названное только что соперником число. Ясно, что все однозначные числа проигрышны, так как нельзя сделать ни одного хода по правилам. Числа от 10 до 18 включительно выигрышные, так как есть возможность назвать однозначное число. Число 19 представляет из себя проигрышную позицию, поскольку мы вынуждены называть двузначное число, а потом наш соперник выиграет, назвав однозначное. Аналогично числа от 20 до 298 выигрышные (мы можем назвать 19). Число 299 проигрышное. Следующее проигрышное число определяется как наименьшее с суммой цифр более 299. Оно 34-значное, первая цифра в нём тройка, а остальные девятки. Все числа от 300 до этого числа выигрышные, в том числе и заданное в условии в качестве примера число 999. Стало быть, при первоначальном 999 победит первый игрок. Он должен назвать 299, затем после любого хода соперника назвать 19, а потом 9. Конечно, порой можно победить и быстрее, но указанный алгоритм сработает наверняка.
За полное решение задачи давалось 15 баллов, упомянувший число 299 получал по крайней мере 10 баллов, за упоминание числа 19 давалось 2 балла, также как и за соображение "однозначные числа проигрывают".
Эта игра, привлекающая простотой правил и интересным ответом, может быть дана и как остроумная олимпиадная задача. Ясно, что в случае нечётного N первый выигрывает, деликатно беря 1 конфету. Для чётного числа так делать нельзя, более того, никто из игроков не должен брать нечётное число конфет, иначе второй выиграет, беря 1 конфету. Значит, все ходы будут состоять во взятии чётного числа конфет. Тогда разделим конфеты на пары и "склеим" конфеты по две. Такая процедура не помешает никому делать ходы и сведёт задачу ко вдвое меньшему числу "двойных конфет". Тем самым случай 2N конфет сводится к N конфетам (первый победит, беря две, то есть одну пару). А случай 1000 конфет последовательно сводится к 500 (сдвоенных), 250 (счетверённых), 125 ("свосьмерённых") конфет, соответственно, первый победит, беря 8 конфет. Итак, при чётном N нужно брать первым ходом 2k конфет, где 2k - максимальная степень двойки, на которую делится N. Далее оба соперника будут брать по стольку, а первый, кто отступит от этого правила, будет наказан соперником, который возьмёт число конфет, равное меньшей степени двойки, перейдя тем самым на "стратегию более низкого уровня". Может показаться, что первый победит всегда, но это не так: если N само является степенью двойки, первый не сможет следовать указанной стратегии (тогда пришлось бы нарушить правило честности) и проиграет, так как на ход второго это правило уже не распространяется.
За полное решение задачи ставилось 20 баллов, 15 баллов получали те, кто не учитывал, что 2k - исключение, за пункт в) как и за идею брать степени двойки без обработки начислялось 10 баллов, за пункт б) давалось 5 баллов, а если его решение переносилось на все чётные N, то 4 балла, пункт а) оценивался в 3 балла.
Почему-то очень многие участники решили, что игроки красят клетки полоски подряд. Из условия это никак, однако, не следует, а игра при таком предположении становится совсем неинтересной.
В пункте а), как и вообще при любом нечётном n первого игрока выручает симметричная стратегия. Первый игрок должен красить центральную клетку и симметрично отвечать на ходы партнёра (то есть красить симметричную клетку тем же цветом). Тогда новый тюбик всегда будет начинать второй игрок.
При n=4k (например для пункта б) ) известна стратегия для второго игрока. Именно, пусть начинающий сделал первый ход. Одну из крайних клеток он не закрасил, дадим ей номер 1, соседней 2 и так далее до 4k. Тогда отделим мысленно клетку 1, и на оставшемся поле ответим и будем в дальнейшем отвечать сопернику симметрично относительно середины оставшегося поля - клетки с номером 2k+1, причём клеткой, симметричной клетке 2k+1 будем считать клетку 1. При этом отвечать будем тем же цветом, а при ходе в 1 или 2k+1 - цветом с минимально возможным номером (цветом N 1 или N 2). При такой игре второй проиграть теоретически может только выбирая цвет N 2 первым. Но это значит, что либо клетки 2 и 2k+1, либо клетки 1 и 2k покрашены в цвет 1. Однако обе пары разной чётности, поэтому третий цвет непременно потребуется.
Для случая n=4k+2 составители задания полного решения не знают. Перебором можно убедиться, что второй игрок побеждает при n=10.
По 5 баллов начислялось за каждый пункт, 5 баллов добавлялось за обобщение а) на любое нечётное n.
В прямоугольнике 4*n побеждает второй, если будет красить в тот же цвет, что и противник, клетку в том же столбце через одну строку.
Симметричная стратегия относительно центральной клетки работает для любых прямоугольников с нечётными сторонами. Прочие варианты составителями задания не исследованы.
Присуждалось 5 баллов за нечётносторонние прямоугольники, 15 баллов за разбор случая 4*n.
Играя в эту игру, в первую очередь замечаешь, что некоторые куски шоколадки (с размерами 2*2, 2*3, 3*3) ломать нельзя, иначе твой соперник немедленно выиграет. И вообще, нельзя ломать шоколадку поперёк стороны длиной 2 или 3. Соответственно, в пункте а) есть только два (с точностью до симметрии) возможных первых хода, после чего у противника остаётся ровно один безопасный ход, далее первому можно сдаваться. В пункте б), как и вообще в случае, когда хотя бы одна сторона шоколадки чётная и отличная от двух, первый для победы может воспользоваться симметрией: сначала сломать шоколадку пополам, а потом зеркально повторять ходы противника, сделанные на одной половине шоколадки, на другой её половине. В случае двух нечётных сторон решение составителям неизвестно. В пункте в) первый может сделать два различных начальных хода, но в любом случае после этого на одной части шоколадки останется 2, на другой 5 безопасных ходов, так что последний ход будет за соперником, и первый проиграет.
Соображения о том, что куски 2*2, 2*3, 3*3 ломать невыгодно, оценивалось в 2 балла, случаи а), б), в) оценивались в 3, 4 и 5 баллов соответственно, за разбор общего случая шоколадки с нечётной стороной к пункту б) добавлялось 5 баллов.
Эта игра стала самой популярной, про неё написали практически все. Но как ни старались авторы в условии ясно написать, что каждый игрок вправе ставить любой знак - и крестик, и нолик! - многие этого не поняли, и играли по обычным правилам "крестиков-ноликов", что на таком большом поле позволяет крестикам легко выиграть. По указанным же правилам побеждает первый игрок, который ставит первый знак (всё равно какой) в центр, а дальше ставит тот же знак, что и противник, в симметричную относительно центра поля клетку, если только он своим ходом не может сразу выиграть (если может, то выигрывает, конечно). При этом ничья не возникает: допустим, что доска заполнена, в центре ход сделан крестиком, тогда ни в какой клетке вокруг центральной не может быть крестика (тогда первый игрок сразу поставил бы крестик напротив и победил), а значит там нолики, а тогда есть три нолика в ряд.
За неясные (но не явно неверные) соображения о симметрии автор работы получал 3 балла, 5 баллов давалось за описание центрально-симметричной стратегии без слов о том, что нужно ей изменить при возможности немедленно выиграть, 6 баллов, если такое действие описано, 8 баллов, если ещё есть и доказательство отсутствия ничьих.
Поскольку эта задача стала самой популярной, большинство забавных высказываний школьников тоже относится к ней. Приведём некоторые из них: "Крестик из атаки пошёл в оборону, и так будет всегда", "Победит тот, кто ходит первым, стратегии особой не надо", "Крестик ходит первым и может поставить себя в любом месте". Очень запомнилась работа на двойном листе, испещрённом примерами партий без каких-либо пояснений, а внизу крупными буквами надпись: "СМЫСЛ В ЛОГИКЕ".
Составители согласны, что в логике заключён глубокий смысл, желают читателям побед в играх и не только, будут очень признательны, если кто-то сообщит им решения игр, не разобранных в этой статье, и в заключение называют авторов предложенных заданий: игру N 1 предложил Беньямин Коган, игру N 2 - Варвара Даревская, игры NN 3, 4 - Александр и Михаил Шаповаловы, игру N 6 - Александр Чеботарёв. Игра же N 5 - математический фольклор - она известна давно, и автор её забыт.