Решение. Солнечные и Лунные города страны Оз (#146)
Страну Оз можно представить в виде непересекающихся циклов из чётного числа городов, соединённых последовательно чёрными и белыми дорогами. Это мы знаем благодаря задаче Страна Оз (#72). Из каждого города дорога из жёлтого кирпича либо ведёт внутрь цикла, либо наружу.
1. Внутрь каждого цикла ведёт чётное число дорог из жёлтого кирпича. (Это следует из леммы о рукопожатиях и того, что по условию никакие дороги не пересекаются.)
2. Если дорогу из жёлтого кирпича, ведущую внутрь, заменить на наружную, то разность числа Солнечных и Лунных городов изменится на два. (Это следует из того, что при такой замене Солнечный город становится Лунным и наоборот.)
3. Если все дороги из жёлтого кирпича ведут наружу, то разность числа Солнечных и Лунных городов равна нулю. (Это следует из того, что в таком случае в каждом цикле Солнечные и Лунные города будут чередоваться.)
Итак, заменим в стране Оз внутренние дороги из жёлтого кирпича на наружные. В силу замечания 1 мы сделаем чётное число замен, а в силу замечания 2 разность числа Солнечных и Лунных городов изменится на кратное четырём. В силу замечания 3 в итоге получится ноль, значит и изначально было кратно четырём.