Олимпиадная задачка (по комбинаторике?)

[Vavilen]

Привет! Такая задачка - задана последовательность из 100 чисел от 1 до 100, расположенных в произвольном порядке. За один ход можно узнать являются ли два числа a, b соседями. За какое минимальное количество ходов можно гарантировано узнать хотя бы одну пару соседних чисел?

Придумал только перебор, то есть фиксируем любое число (например - 1) и проверяем все числа от 2 до 99, получается 98 ходов. Если число не первое и не последнее, то даже 97 хватит, но мы это гарантировать не можем, поэтому гарантировано все-таки 98. Есть идеи как можно улучшить?

[artempalkin]

Более интересен вопрос, а обязательно ли соседи найдутся. Если нет, тогда никакого минимального количества ходов не существует.

-- 11.05.2024, 10:12 --

Рассмотрим такое расположение 10 первых чисел: $162738495\overline{10}$. Как видно, пары рядом нет. Для ста чисел достаточно расположить его десятками таким образом (и некоторые десятки развернуть наоборот, чтобы "концы" не стояли рядом). Тогда пар не будет, а значит, сколько ни проверяй, никакой пары не найдешь.

-- 11.05.2024, 10:13 --

А, я, наверное, неправильно понял условие... Ну, оставлю как есть.

[Vavilen]

Имеются в виду произвольные числа a и b, которые стоят рядом в заданной последовательности, а не числа подряд вроде 1, 2

[mihaild]

Наивная комбинаторика дает оценку снизу в 50 ходов (51 если чуть-чуть еще помахать руками). Но вряд ли это достигается.

[Vavilen]

mihaild Можете пояснить про наивную комбинаторику? Как можно получить за 50 ходов ответ?

[TOTAL]

Vavilen в сообщении #1638718 писал(а):

mihaild Можете пояснить про наивную комбинаторику? Как можно получить за 50 ходов ответ?

Утверждение было не про достаточность $50$, а про необходимость $50$ ходов.

[svv]

$93$ ходов недостаточно.
Я применил теорему Оре (рус, англ), которая даёт достаточное условие гамильтоновости графа.

Возьмём полный граф $G$ со $100$ вершинами. Перенумеруем вершины от $1$ до $100$. Считаем, что все рёбра чёрные. Загаданной последовательности соответствует гамильтонов путь в графе. Допустим, мы задали $93$ вопроса и на каждый получили ответ «нет». Покрасим соответствующие рёбра в красный цвет. Возьмём две различные вершины $v$ и $w$, соединённые красным ребром. Пусть им инцидентны соответственно $r_v, r_w$ красных рёбер. Тогда $r_v+r_w\leqslant 94$ (одно красное ребро общее). Рассмотрим граф $G_1$, полученный из $G$ удалением красных рёбер. В нём
$\deg v=99-r_v$
$\deg w=99-r_w$
$\deg v+\deg w=198-(r_v+r_w)\geqslant 198-94=104\geqslant 100$
Условия теоремы Оре для $G_1$ выполнены, поэтому в $G_1$ существует гамильтонов цикл (нам достаточно гамильтонова пути, но такова теорема).

Теперь удалим из $G_1$ рёбра этого цикла. Получим граф $G_2$, в котором степень каждой вершины будет ещё на $2$ меньше. Но условия теоремы Оре выполнены и для $G_2$, поскольку $104-2\cdot 2\geqslant 100$. Вывод: в графе $G_1$ существует два разных гамильтоновых цикла, не пересекающихся по рёбрам. А это значит, что мы ни для одного ребра $G_1$ не знаем, входит ли оно в гамильтонов путь, соответствующий загаданной последовательности.

[DeBill]

svv

svv в сообщении #1638910 писал(а):

существует два разных гамильтоновых цикла, не пересекающихся по рёбрам.

Это, конечно, хватает, но - слишком оно обременительно. Заменим его другим; "каждое ребро не входит в какой-нить гамильтонов путь". И тогда Ваша метОда даст, что и 97 - недостаточно.
Действительно, пусть чел назвал 97 ребер, после чего заявил, что некоторое ребро - есть. Удалим из полного графа все эти 98 ребер, и покажем, что на оставшемся гамильтонов путь - есть. Это и дает ваша теорема - за исключением единственно случая, когда все 98 ребер торчат из пары вершин. Но в этом случае имеем полный подграф на 98 вершинах, и гамильтонов путь на всем графе таки есть...