Всесиб 2023, 11 класс, задача 5

Ответ. За вопросов.

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

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

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

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

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

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

База индукции - случаи графов с и вершинами - очевидна.