{ "id": "inmo-2021-p4-detective-cards-hamiltonian-path", "title": "Детектив, карты и гамильтонов путь после удаления рёбер, INMO 2021 P4", "kind": { "primary": "olympiad_problem", "secondary": [ "graph_in_solution", "application" ] }, "language": "ru", "authors": [ { "name": "?", "status": "needs_human_review", "note": "Author name was normalized to '?' because previous value was not a person or author group (role_is_publisher_of_official_archive: HBCSE). Официальный PDF INMO 2021 с решениями не указывает индивидуального автора задачи." } ], "problem_profile": { "objects": [ "cards_numbered_1_to_52", "queries_about_consecutive_numbers", "complete_graph", "deleted_edges", "hamiltonian_path" ], "methods": [ "adversary_strategy", "complete_graph_deletion", "longest_path_argument", "degree_sum_common_neighbor" ], "transformations": [ "questions_to_deleted_edges", "safe_negative_answers_to_hamiltonian_labeling" ], "goal": [ "determine_minimum_number_of_queries" ], "auxiliary_graph_type": [ "dense_simple_graph" ], "invariants": [ "at_most_N_minus_2_deleted_edges", "existence_of_spanning_path" ], "keywords": [ "inmo_2021_p4", "detective_cards", "hamiltonian_path", "complete_graph_minus_few_edges", "official_solution_graph" ], "status": "ai_checked" }, "statements": { "original": [ { "id": "stmt-original", "title": "Официальное условие", "text": "Фокусник и Детектив играют в игру. Фокусник кладёт на стол лицом вниз карты, пронумерованные числами от \\(1\\) до \\(52\\). За один ход Детектив может указать на две карты и спросить, стоят ли написанные на них числа рядом. Фокусник отвечает правдиво. После конечного числа ходов Детектив указывает на две карты. Она выигрывает, если числа на этих двух картах соседние, и проигрывает иначе.\n\nДокажите, что Детектив может гарантировать победу тогда и только тогда, когда ей разрешено задать не менее \\(50\\) вопросов.", "source_id": "src-inmo-2021-official-solutions", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [], "distinct_from": [ "stmt-graph-hint" ] } ], "graph_theory": [], "graph_hint_reformulations": [ { "id": "stmt-graph-hint", "title": "Подсказочная графовая формулировка", "text": "Для нижней оценки замените \\(52\\) на произвольное \\(N>3\\). После каждого вопроса, на который Фокусник отвечает «нет», удаляйте из полного графа \\(K_N\\) ребро между соответствующими картами. Докажите, что после удаления любых \\(N-2\\) рёбер в оставшемся графе всё ещё есть гамильтонов путь. Тогда карты можно пронумеровать вдоль этого пути числами \\(1,2,\\ldots,N\\), и все отрицательные ответы будут правдивыми.", "status": "ai_checked", "self_contained": { "status": "ai_checked" }, "definition_ids": [ "simple_graph", "path", "complete_graph", "hamiltonian_path" ], "distinct_from": [ "stmt-original" ] } ], "olympiad_reformulations": [] }, "ideas": [ { "id": "idea-upper-strategy", "title": "Одна фиксированная карта даёт стратегию за 50 вопросов", "text": "Детектив выбирает карту \\(A\\) и спрашивает про пары \\(A\\) со всеми остальными картами, кроме одной. Если получен ответ «да», нужная пара найдена. Если все \\(50\\) ответов отрицательны, единственная не спрошенная карта должна быть соседней с \\(A\\).", "tags": [ "goal_strategy_game" ], "status": "ai_checked" }, { "id": "idea-negative-answers-as-deleted-edges", "title": "Отрицательные ответы кодируются удалёнными рёбрами", "text": "Если после \\(q\\) вопросов без ответа «да» можно пронумеровать карты так, чтобы все спрошенные пары не были соседними числами, то Фокусник мог правдиво отвечать «нет» все \\(q\\) раз. Для \\(q\\le N-2\\) такую нумерацию даёт гамильтонов путь в графе не спрошенных пар.", "tags": [ "graph_model" ], "status": "ai_checked" }, { "id": "idea-longest-path-after-few-deletions", "title": "Мало удалённых рёбер оставляет гамильтонов путь", "text": "В графе, полученном из \\(K_N\\) удалением не более \\(N-2\\) рёбер, любые две вершины имеют общего соседа, поэтому граф связен. Длиннейший путь затем замыкается в цикл с помощью соседей его концов; связность не позволяет оставить вершину вне этого цикла.", "tags": [ "hamiltonian_cycles" ], "status": "ai_checked" } ], "solutions": [ { "id": "sol-official-expanded", "title": "Решение через удаление рёбер из полного графа", "text": "Сначала покажем, что \\(50\\) вопросов достаточно. Детектив выбирает карту \\(A\\) и спрашивает, соседнее ли число на ней с числом на каждой из \\(50\\) других карт, оставляя непроверенной только одну карту \\(B\\). Если на каком-то вопросе Фокусник отвечает «да», Детектив сразу указывает найденную пару. Если все \\(50\\) ответов были «нет», то карта \\(B\\) обязана быть соседней с \\(A\\): у числа на карте \\(A\\) среди чисел \\(1,2,\\ldots,52\\) есть хотя бы один сосед, и все карты, кроме \\(B\\), уже проверены и не подходят.\n\nДокажем, что \\(49\\) вопросов недостаточно. Рассмотрим более общий случай с \\(N>3\\) картами. Построим граф на картах. Сначала это полный граф \\(K_N\\). Каждый вопрос, на который Фокусник хочет ответить «нет», удаляет ребро между двумя спрошенными картами. Если после не более чем \\(N-2\\) вопросов в оставшемся графе есть гамильтонов путь, то Фокусник нумерует карты вдоль этого пути числами \\(1,2,\\ldots,N\\). Тогда карты с соседними номерами соединены ребром пути, то есть такая пара раньше не спрашивалась; все ответы «нет» правдивы.\n\nОсталось доказать лемму: удаление не более \\(N-2\\) рёбер из \\(K_N\\) оставляет граф с гамильтоновым путём. Возьмём любые две вершины \\(a,b\\). Так как удалено не более \\(N-2\\) рёбер, имеем \\(\\deg a+\\deg b\\ge 2(N-1)-(N-2)=N\\). Поэтому у \\(a\\) и \\(b\\) есть общий сосед; иначе сумма их степеней была бы не больше \\(N-1\\). В частности, граф связен.\n\nПусть \\(P:u=u_0,u_1,\\ldots,u_k=v\\) — длиннейший простой путь. Все соседи концов \\(u\\) и \\(v\\) лежат на \\(P\\), иначе путь можно продлить. Запишем соседей \\(u\\) как \\(u_{i_1},\\ldots,u_{i_x}\\), а соседей \\(v\\) как \\(u_{j_1},\\ldots,u_{j_y}\\). Из \\(x+y=\\deg u+\\deg v\\ge N\\) следует, что найдётся индекс \\(i\\), для которого есть оба ребра \\(u u_{i+1}\\) и \\(u_i v\\). Иначе индексы соседей \\(u\\) и индексы, следующие за соседями \\(v\\), не пересекались бы и не поместились бы на пути.\n\nЭти два ребра замыкают все вершины пути \\(P\\) в цикл. Если бы существовала вершина \\(w\\), не лежащая на \\(P\\), то по связности из \\(w\\) был бы путь к этому циклу; пройдя от \\(w\\) до цикла, а затем почти весь цикл, мы получили бы простой путь длиннее \\(P\\). Противоречие. Значит, \\(P\\) содержит все \\(N\\) вершин.\n\nДля исходной задачи \\(N=52\\). После \\(49\\) вопросов удалено не более \\(49