|
|
 |
Условие
Имеются две страны: Обычная и Зазеркалье. У каждого города в Обычной стране есть "двойник" в Зазеркалье, и наоборот. Однако если в Обычной стране какие-то два города соединены железной дорогой, то в Зазеркалье эти города не соединены, а каждые два несоединённых в Обычной стране города обязательно соединены железной дорогой в Зазеркалье. В Обычной стране девочка Алиса не может проехать из города A в город B, сделав менее двух пересадок. Доказать, что Алиса в Зазеркалье сможет проехать из любого города в любой другой, сделав не более двух пересадок.
Решение
Из условия следует, что города A и B в Обычной стране не соединены дорогой и что любой другой город в Обычной стране не соединён либо с A, либо с B. Значит, двойники A' и B' городов A и B в Зазеркалье соединены дорогой, а каждый другой город Зазеркалья соединён либо с A', либо с B'. Следовательно, в Зазеркалье из каждого города можно доехать до одного из городов A' и B', затем при необходимости доехать до второго из них, а после доехать до любого другого города Зазеркалья. При этом требуется не более двух пересадок.
