Все 16 городов Криптоландии в качестве названий имеют различные четырехразрядные комбинации, состоящие из нулей и единиц (например, «0011»). Все города попарно соединены непересекающимися дорогами, причем проезд из одного города в другой стоит столько криптов, в скольких разрядах различаются их имена (например, из «0011» в «1001» – 2 крипта). Путешественник, находящийся в «0000», хочет объехать все города страны и вернуться назад за минимальную цену. Как ему это сделать?
Одно из возможных решений указано в таблице
№ поездки | Город |
1 | 0001 |
2 | 0011 |
3 | 0010 |
4 | 0110 |
5 | 0111 |
6 | 0101 |
7 | 0100 |
8 | 1100 |
9 | 1101 |
10 | 1111 |
11 | 1110 |
12 | 1010 |
13 | 1011 |
14 | 1001 |
15 | 1000 |
16 | 0000 |
Номеру поездки соответствует город прибытия. Для того чтобы такая таблица соответствовала решению все комбинации, состоящие из четырех цифр, каждая из которых равна либо 0, либо 1, должны быть перечислены и последовательные комбинации должны отличаться в одном разряде.