Top.Mail.Ru
? ?
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

олимпиада: 2019/P3 [июл. 26, 2019|01:31 am]
Anatoly Vorobey
[Tags|, ]

Продолжаем решать задачи Международной Математической Олимпиады-2019. Задачу P2 не решил никто. Сегодня задача P3.



Как и раньше, прошу постить только собственные идеи/решения. Комменты скринятся на сутки, потом открываю.

Update: Комментарии открыты. Решение есть только одно, от emhanik, зато правильное (насколько могу судить), браво!
СсылкаОтветить

Comments:
[User Picture]From: pigmeich
2019-07-26 01:38 am
Ощущение, что все 1010 пользователей дружат только с 1009 пользователями.

Раскрашивать муторно, но думаю, где-то даже теорема по этому поводу есть.
(Ответить) (Thread)
[User Picture]From: avva
2019-07-26 07:35 am
Т.е. граф дружбы complete bipartite: каждый из 1009 дружит с каждым из 1010 и наоборот. Я придумал док-во для случая, когда это так; к сожалению, по-видимому это не так - по крайней мере для игрушечных примеров с разбивкой на группы из 2 и 3 или из 3 и 4 игроков я смог нарисовать графы, где это не так (но задача все равно имеет решение, разумеется).
(Ответить) (Parent) (Thread)
From: ichthuss
2019-07-26 08:10 pm
При каждой перестройке число ребер графа уменьшается на 1. Соответственно, любая последовательность применения преобразования будет конечной. Возьмём одно из конечных состояний. В этом состоянии нет пользователей, имеющих более одного друга, иначе преобразование было бы применимо. ЧТД.
(Ответить) (Thread)
[User Picture]From: alex_levit
2019-07-27 10:59 am
> В этом состоянии нет пользователей, имеющих более одного друга

Это не так. Например, могут быть три пользователя, которые дружат только друг с другом и кроме них никто ни с кем не дружит. В общем виде в конечном состоянии все пользователи разбиты на клики, внутри клики все дружат со всеми, а между членами разных клик дружбы нет.
(Ответить) (Parent) (Thread)
From: emhanik
2019-07-27 11:50 pm
Исходный граф связный, неполный, и в нем есть вершины нечетной степени. Количество таких вершин не меняется при перестройках.
Будем выполнять произвольные перестройки, не нарушающие связность, пока не придем к ситуации, когда любая следующая перестройка нарушила бы связность.
Если полученный граф окажется деревом, дальнейшая перестройка очевидна.
Допустим, он не дерево, т.е. содержит цикл.
Выберем простой цикл максимальной длины A[1],...,A[k].
Так как граф связен и в нем есть цикл и вершины нечетной степени, то в цикле есть вершина степени >2.

Заметим, что среди вершин цикла со степенью >2 найдется такая, в окружении которой есть пара несмежных вершин.
[Допустим, это не так. Пусть A[i] имеет степень >2. Тогда A[i+1] смежна не только с A[i], но и со всем ее окружением, а значит, имеет степень >2. Тогда A[i+2] смежна со всем окружением A[i+1] и т.д. Получим, что все вершины цикла попарно смежны. Тогда, поскольку граф связен и не полон, найдется вершина B вне цикла, смежная с какой-то вершиной A[j] цикла. По предположению, B должна быть смежна с A[j+1]. Но тогда ее можно добавить в цикл, что противоречит его максимальности.]

Заметим, что если в окружении какой-либо вершины степени >2 есть пара несмежных вершин, то никакие две вершины в ее окружении не смежны.
[Действительно, пусть вершина T смежна с вершинами X, Y и Z (возможно, с какими-то еще), причем X и Y не смежны. Тогда Y и Z не смежны, иначе бы перестройка «(TZ, TY) -> XY» не нарушала связность.]

Итак, некоторая вершина цикла A[m] смежна, помимо вершин A[m-1] и A[m+1], с некой вершиной C и никакие две вершины из ее окружения не смежны. Выполним перестройку «(A[m]C, A[m]A[m+1]) -> A[m+1]C». Двигаясь из A[m] назад по циклу, можно прийти какую-либо из вершин C или A[m+1] (в зависимости от того, принадлежит ли C циклу), затем в другую. Связность не нарушена — противоречие.
(Ответить) (Thread)
From: emhanik
2019-07-27 11:53 pm
Т.е. после максимального числа перестроек, не нарушающих связность, обязательно получим дерево.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2019-07-28 07:45 am
По-моему все верно. Очень круто!
(Ответить) (Parent) (Thread)
[User Picture]From: Евгений Смирнов
2019-07-28 11:14 pm
Не очень понял, а почему в полученном графе будут вершины нечётной степени? Почему не может получиться просто цикл?

И ещё: а как показать что исходный граф связный?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2019-07-28 11:26 pm
Ничего если я отвечу?

1. Операция изменения графа, когда мы удаляем AB и AC и добавляем BC, не меняет четности степеней ни одной вершины (А теряет 2 ребра, B и C сохраняют четность). Поскольку вершины нечетной степени есть в исходном графе, они там всегда будут оставаться.

2. Тут мы пользуемся тем, что в исходном графе у каждой вершины степень не меньше 1009. Если есть две вершины, которые не соединены и у которых нет общего соседа, это дает уже как минимум 2+1009+1009 разных вершин, что больше числа вершин в графе. Так что у каждых двух несоединенных вершин есть общий сосед.
(Ответить) (Parent) (Thread)
[User Picture]From: Евгений Смирнов
2019-07-28 11:35 pm
Спасибо! Теперь наконец понятно, зачем нужно было это странное условие про 1010 вершин степени 1009 и 1009 степени 1010. Но вообще, конечно, безобразие, что это условие нужно только для связности графа. Оно очень запутывает: ты ожидаешь, что требуемое свойство верно только для этого уникального графа (что-то вроде того, о чем выше писал pigmeich), а оказывается, что это условие нужно только для связности... Очень разочаровывает.

Edited at 2019-07-28 23:37 (UTC)
(Ответить) (Parent) (Thread)