|
|
 |
Условие
В стране 64 города, некоторые пары из них соединены дорогой, но нам неизвестно, какие именно. Можно выбрать любую пару городов и получить ответ на вопрос “есть ли дорога между ними?”. Нужно узнать, можно ли в этой стране добраться от любого города до любого другого, двигаясь по дорогам. Докажите, что не существует алгоритма, позволяющего сделать это менее чем за 2016 вопросов.
Решение
Переформулируем задачу.
Дан полный граф на 64 вершинах с белыми рёбрами (их всего 2016). Играют двое. Петя указывает белое ребро, а Вася удаляет его или делает чёрным. Перед последним ходом Петя предсказывает, какой в итоге получится граф – связный или нет. Докажем, что Вася может опровергнуть любое предсказание Пети.
Всё время рассматриваем граф всех вершин и оставшихся белых и чёрных рёбер. Если указанное Петей ребро содержится в каком-то цикле, то Вася удаляет его, иначе – делает чёрным. При этом связность графа сохраняется, а чёрные рёбра в циклы не входят.
Перед последним ходом остаётся лишь одно белое ребро. Значит, циклов не осталось, и граф – дерево. Поэтому Вася может как удалить это ребро, нарушив связность, так и сохранить вместе со связностью.
Замечания
8 баллов
