Условие задачи (1981, № 2) Задача М670 // Квант. — 1981. — № 2. — Стр. 22; 1981. — № 10. — Стр. 36—37.
Дано несколько точек, некоторые пары которых соединены линиями (точки таких пар называются соседями). Число соседей у каждой точки нечётно. В начальный момент все точки раскрашены в два цвета — красный и синий. Затем каждую минуту происходит одновременное перекрашивание точек по следующему правилу: каждая точка, у которой большинство соседей имеет отличный от неё цвет, меняет свой цвет; в противном случае её цвет сохраняется.
Докажите, что наступит момент, начиная с которого у некоторых точек цвет не будет меняться, а у некоторых будет меняться каждую минуту.
- Останется ли это утверждение верным, если не предполагать, что у каждой точки число соседей нечётно?
Изображения страниц
Решение задачи (1981, № 10) Задача М670 // Квант. — 1981. — № 2. — Стр. 22; 1981. — № 10. — Стр. 36—37.
Текстовое представление решения задачи находится в процессе подготовки. С графическим представлением можно ознакомиться в опубликованном номере