Условие
Два маляра красят забор, огораживающий дачные участки. Они приходят через день
и красят по одному участку (участков 100 штук) в красный или зелёный цвет.
Первый маляр дальтоник и путает цвета, он помнит, что и в какой цвет он сам
покрасил, и видит, что покрасил второй маляр, но не знает, в какой цвет.
Первый маляр добивается того, чтобы в наибольшем числе мест зелёный участок
граничил с красным. Какого наибольшего числа переходов он может добиться (как
бы ни действовал второй маляр)?
Замечание.
Считается, что дачные участки расположены в одну линию.
Решение
Покажем сначала, как первому маляру обеспечить не менее 49 переходов.
Разобьём участки на пары:
(1, 2),(3, 4),...,(99, 100). Тогда первый маляр
может добиться того, чтобы в каждой паре с чётным номером встречался красный
цвет, а в каждой паре с нечётным номером — зелёный. Для этого достаточно
действовать следующим образом: если второй покрасил какой-то участок, то первый
красит другой участок из той же пары так, чтобы в паре гарантированно встречался
нужный цвет; если же другой участки из пары уже покрашена, то первый красит
любой участок в нужный цвет. Таким образом, в каждой паре будет хотя бы один
участок нужного цвета, а значит, число переходов будет не менее 49.
Покажем теперь, как второму маляру обеспечить, чтобы число переходов
не превосходило 49. Для этого достаточно после каждого хода первого красить
участок из той же пары в тот же цвет. Тогда каждая пара будет одноцветна,
а значит, общее число переходов не будет превосходить 49.
Ответ
49 переходов.
Источники и прецеденты использования
