Архив задач олимпиады по математике и криптографии
Шифр на графе
Для зашифрования натурального числа mиспользуется граф, представляющий собой множество вершин, некоторые из которых соединены друг с другом прямой линией. Вершины графа, соединенные друг с другом, называют соседними. Зашифрование состоит в выполнении следующих действий. В вершины графа записываются натуральные числа так, чтобы их сумма была равна m. Затем к числу в каждой вершине прибавляются числа в соседних вершинах. В результате получается граф, в котором «зашифровано» число m. Пример: для зашифрования числа 8 будем использовать граф на рис. 1. В его вершины поместим числа, сумма которых равна 8 (рис. 2). Затем к каждому числу прибавим числа в соседних вершинах. Результат зашифрования указан на рис. 3. На рис. 4 приведен результат зашифрования некоторого числа. Найдите его.
Граф, используемый в задаче, обладает следующим свойством: из множества всех его вершин можно выделить такое подмножество V(отмеченное на рис. 5 кружочками), что любая вершина графа лежит в окрестности ровно одной вершины из V. Окрестностью вершины графа называют множество соседних с ней вершин, включая её саму. Очевидно, что искомое число равно сумме чисел, расположенных в вершинах из множестваV: .
