В первом случае побеждает Вася, а во втором — Петя.

В первом случае можно заметить, что среди красных шариков есть особенный (первый большой): он не самый маленький, но при этом не имеет непосредственно предыдущего по размеру. Синего шарика с таким свойством нет.

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

Заметим, что если в какой-то момент появились две пары шариков, в которых синие шарики идут не в том порядке, что красные, то Петя точно проиграл и игру можно прекратить.

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

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

Почему Пете всегда удастся поддержать такое условие? Будем рассуждать по индукции. Пусть до определенного момента условие выполнялось. Посмотрим, что мог сделать Вася на своем очередном ходу. Во-первых, он мог разбить конечное расстояние между шариками, выбрав шар между ними — тогда Петя берет шарик, делящий отрезок между соответствующими шариками второго цвета в том же отношении. Во-вторых, Вася мог взять шарик между двумя шариками, находящимися на бесконечном расстоянии. На какие отрезки он мог разбить этот бесконечный отрезок? Сразу отметем случай двух конечных отрезков — если они конечны на следующем ходу, то длина каждого из них меньше , а тогда длина всего отрезка меньше , то есть он конечен — противоречие.

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

Напомним, что множество натуральных чисел обозначается символом . Переформулируем правила игры (например, первого случая) более строго.

Есть два множества: (это наши синие шарики) и (это красные шарики; знак «» означает здесь, что берутся две копии множества и каждый элемент первой копии меньше любого элемента второй — как раз то, что было у нас с маленькими и большими шариками). Вася выбирает число ходов, а потом на каждом ходу Вася выбирает элемент из любого множества, а Петя выбирает ему в соответствие элемент другого множества. Условием победы Пети является то, что в конце пары соответствующих элементов расположены в одном порядке.

Описанная игра является частным случаем игры Эренфойхта (см.: Ehrenfeucht–Fraïssé game), описанной в 1960 г. Эта игра возникает в математической логике — разделе математики, изучающем саму математику — обозначения, формальные выражения и доказательства. Сейчас мы будем говорить о логике первого порядка, изучающей формулы: последовательности кванторов ( — «для любого» и — «существует»), связок («и», «или» и знак следствия), переменных и различных символов, сопоставляющих набору значений переменных логическое значение (истинное или ложное) — такие символы называются предикатами. Предикатом является, например, знак сравнения «», который на паре значений переменных принимает истинное значение, если первое из них меньше другого, и ложное в противном случае. Собственно, такие формулы и встречаются обычно в математических текстах.

Значение кванторов и логических связок всегда одно и то же, но вот значение предикатов можно определять по-разному. Допустим, мы ограничили набор используемых предикатов (скажем, разрешили использовать в формулах только знаки сравнения) — этот набор называется сигнатурой. Теперь нам нужно выбрать множество, в котором могут принимать значения переменные (пусть это будет множество натуральных чисел) и определить значения предикатов на каждом наборе элементов этого множества (то есть для каждой пары чисел нужно выбрать, какое из них больше — это делается естественным образом, но можно и как-нибудь по-другому). Совокупность множества значений переменных и правил, определяющих значения предикатов называется интерпретацией сигнатуры.

Пусть есть две интерпретации одной сигнатуры. Важный вопрос, ради которого все и затевалось: можно ли написать формулу, различающую эти интерпретации, то есть такую, которая истинна на одной интерпретации и ложна на другой? Если различающей формулы нет, то две интерпретации называются элементарно эквивалентными.

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

Чтобы было понятнее, посмотрим на нашу первую игру с этой точки зрения. Рассматривается сигнатура, состоящая из одного предиката — знака сравнения («»), и две ее интерпретации: натуральные числа с естественным порядком (то есть значение знака сравнения определяется как обычно: «» и «» — истинные утверждения) и множество с описанным выше порядком. То, что в итоге соответствующие элементы идут в одинаковом порядке как раз означает, что значения предиката сравнения на них совпадают. Так как Вася побеждает в этой игре, то эти интерпретации не являются элементарно эквивалентными, то есть существует формула, различающая их. В данном случае несложно ее привести:

.

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

Математики (как, впрочем, и не только они) очень любят игры: гораздо интереснее придумывать, как победить в игре, чем возиться, например, с формулами.