Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Задача состоит из трёх пунктов, условия которых чуть отличаются. Каждый пункт оценивается в отдельности. Оценивается текст решения, постарайтесь представить максимально подробное обоснование.
7.1 Вдоль длинной улицы расположены дома, в каждом из которых живёт по одному человеку. Каждый из жителей улицы является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается со всеми своими соседями (с одним соседом, если человек живёт в на краю улицы и с обоими соседями в остальных случаях). За ночь он обдумывает полученную от них информацию, и если оказывается, что двое его соседей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Верно ли, что когда-нибудь политические взгляды жителей улицы стабилизируются?
7.2 Вокруг круглой площади расположены 2017 домов, в каждом из которых живёт по одному человеку. Каждый из жителей площади является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается с обоими своими соседями. За ночь он обдумывает полученную от них информацию, и если оказывается, что оба его соседа являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Верно ли, что когда-нибудь политические взгляды жителей улицы стабилизируются?
7.3 Вокруг круглой площади расположены 2018 домов, в каждом из которых живёт по одному человеку. Каждый из жителей площади является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается с обоими своими соседями. За ночь он обдумывает полученную от них информацию, и если оказывается, что оба его соседа являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
Верно ли, что когда-нибудь политические взгляды жителей улицы стабилизируются?
7.1 Ответ: верно. Рассмотрим кол-во пар соседних жителей, таких что они имеют разные политические взгляды. Заметим, что каждую ночь кол-во таких пар не увеличивается, потому что если два соседа сторонники одной политической партии, то они не поменяют свои взгляды (у каждого из них по крайней мере один сосед сторонник той же партии, что и он, значит нет двух соседей противоположной партии). Причём если кто-то меняет свои политические взгляды, можно пронумеровать дома с одного краю улицы до другого, и для человека с наименьшим номером дома, который поменял полит. взгляды, оба его соседа имели противоположные полит. взгляды, причём тот, дом которого имеет меньший номер не поменял полит. взгляды (они теперь будут сторонники одной партии!), так как мы взяли человека с наименьшим номером дома. Значит, если кто-то меняет полит. взгляды, то кол-во пар соседей с разными полит. взглядами строго уменьшается хотя бы на один. Так как такое кол-во не может быть отрицательным, с какой-то ночи никто больше не будет менять полит. взгляды и положение стабилизируется. 7.2 Так как 2017 нечётно, политические партии, сторонниками которых являются жители не могут чередоваться по всему кругу. Значит, какие-то два соседа являются сторонниками одной и той же полит. партии и никогда не поменяют свои взгляды. Тогда можно считать, что дома расположены не по кругу, а по прямой, начиная с первого из найденных соседей и заканчивая вторым из найденных соседей, потому что наши соседи всё равно не поменяют полит. партии и теперь как крайние они снова никогда не поменяют полит. партии. По задаче 7.1 в данном случае положение стабилизируется. 7.3 Нет, неверно. Если полит. партии жильцов будут чередоваться в порядке обхода по кругу (а это возможно, потому что 2018 -- чётное число), то каждую ночь каждый житель будет менять свою партию на противоположную. То есть через две ночи Жильцы вернутся к исходным партиям и процесс повторится, то есть зациклится.