Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
В некоторой компании у каждого человека по 3 друга. Каждый из них является сторонником одной из двух политических партий: красной или синей. Каждый день каждый человек общается со всеми своими друзьями. За ночь он обдумывает полученную от них информацию, и если оказывается, что большинство его друзей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Докажите, что для любой компании существует исходное распределение политических взглядов при котором в дальнейшем стабилизации политических взглядов не происходит.
Автоматическая проверка задачи не производится. Будет оцениваться текст решения. Манипулятор можно использовать для иллюстрации своих рассуждений.
Пусть вершинам графа соответствуют люди и между двумя вершинами есть ребро тогда и только тогда, когда соответственные люди дружат. Тогда степень каждой вершины в таком графе хотя бы три. Пусть мы нашли цикл чётной длины в этом графе, тогда можно чередуя присвоить партии людям этого цикла дружбы. Тогда у каждого из человека этого цикла будет хотя бы 2 друга противоположной партии, то есть большинство. Значит, ночью они поменяют свои полит. взгляды. Второй ночью по тем же причинам они снова сменят партию и процесс зациклится. Осталось доказать, что такой цикл всегда есть. Рассмотрим все максимальные по включению подмножества вершин такие, что если выкинуть все остальные вершины, то оставшийся граф будет связанный и без мостов. Заметим, что такие подмножества не пересекаются и каждая вершина принадлежит хотя бы одному из множеств. Рассмотрим другой граф, в котором вершинам соответствуют рассматриваемые подмножества вершин, а рёбрами будут соединятся те вершины, для которых существует ребро (мост) в первом графе между вершинами из данных множеств. Тогда получается дерево. Значит существует висячая вершина. Ей соответствует какое-то множество вершин, степень каждой за исключением не более одной (из которой ведёт мост) равна трём. Тогда там хотя бы три вершины (есть вершина степени хотя бы 2).В нём есть ребро. Так как этот граф без мостов, в нём есть цикл. Рассмотрим этот цикл, его длина хотя бы три. Если она чётна, то мы победили. Иначе рассмотрим рёбра из вершин этого цикла, не являющиеся частью цикла. Таких рёбер хотя бы 2, так как хотя бы две вершины имеют степень три.