Таблицы Брадиса

Останется одна или несколько связных

Останется одна или несколько связных

Элементы математики в задачах - Г. А. Мерзон

Выберем в графе произвольную вершину и пойдем из нее по какому-либо пути. В силу того, что входная полустепень каждой вер­шины равна выходной (это свойство называют законом Кирхгофа), мы рано или поздно попадем в вершину, в которой уже были. Таким образом, получаем замкнутый цикл (A^..An). Выкинем ребра этого цикла из графа. Останется одна или несколько связных компонент, к которым можно применить предположение индукции. Осталось склеить все получившиеся циклы в один, что мы можем сделать в силу предположения о связности исходного графа.

Задача 20 (цикл де Брюина). Для того, чтобы открыть кодовый за­мок (с кнопками от 0 до 9), необходимо набрать код из четырех цифр, причем не важно, что было нажато до набора правильного кода. За какое наименьшее количество нажатий его можно гарантированно открыть?

Решение. Нарисуем граф, в котором вершинами являются трехзнач­ные комбинации цифр, а стрелки ведут из вершин вида abc в вершины bcd, где a, b, c, d —произвольные цифры. Легко видеть, что ребра в этом графе соответствуют четырехзначным комбинациям на кодовом замке. Кроме того, граф удовлетворяет критерию из предыдущей задачи и, следовательно, является эйлеровым. Поэтому в нем суще­ствует цикл, проходящий по всем ребрам ровно по одному разу.

Всего трехзначных комбинаций 1000, полная степень каждой вер­шины равна 20 (обратите внимание на то, что наличие петли из вершины в себя увеличивает ее степень на 2). Таким образом, длина эйлерова пути равна | • 1000 • 20 = 10000. Чтобы получить ответ, осталось прибавить три первые цифры.

Ответ. 10003 нажатия.

Задача 21. 20 школьников решали 20 задач. Каждый решил ровно две задачи, и каждую задачу решили ровно двое. Докажите, что можно устроить разбор задач так, чтобы каждый рассказал одну решенную им задачу.