|
|
 |
Условие
В каждой из n стран правит либо партия правых, либо партия левых. Каждый год в одной из стран A может поменяться власть. Это может произойти в том случае, если в большинстве граничащих со страной A стран правит не та партия, которая правит в стране A. Докажите, что смены правительств не могут продолжаться бесконечно.
Подсказка
Как меняется количество пар граничащих стран, имеющих одну и ту же партию у власти?
Решение
Пусть власть сменилась в некоторой стране A, в которой правят левые (для определённости). Пусть среди граничащих с ней стран было k стран, где правят левые и m стран, где правят правые, k < m. При смене власти в стране A количество стран среди граничащих с ней стран, в которых правит та же партия, что и в А, возрастёт: 2(m – k) > 0. Таким образом, после смены власти в какой-либо из стран, число пар граничащих стран, имеющих одну и ту же партию у власти, возрастает. Это возрастание не может продолжаться бесконечно долго, поскольку число пар граничащих стран конечно.
Источники и прецеденты использования
| web-сайт | |
| задача |
