Задача
COM-B2-M04-P014 Два цвета и максимальная цепь
В строке из \(n\) клеток каждая клетка окрашена в красный или синий цвет. Разрешается выбрать несколько непересекающихся соседних пар разных цветов. Множество выбранных пар максимально по включению. Докажите, что среди невыбранных клеток не бывает двух соседних клеток разных цветов.
Если две соседние невыбранные клетки разных цветов, их пара всё ещё доступна.
Пусть две соседние невыбранные клетки \(i\) и \(i+1\) имеют разные цвета. Тогда пара \((i,i+1)\) подходит по условию и не пересекается ни с одной выбранной парой, потому что обе клетки не выбраны.
Её можно добавить к текущему множеству пар, сохранив все условия. Это противоречит максимальности по включению. Следовательно, таких соседних невыбранных клеток нет.
Полезная неграфовая версия рассуждения о максимальном паросочетании.