Брат рассказал задачу
Mar. 1st, 2011 01:04 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
posicпо так наз. дискретной математике, что ли.
Имеется алфавит из m букв. Доказать, что можно расставить по кругу mn букв (существует циклическое слово такой длины в этом алфавите) так, чтобы отрезки длины n в этом слове (которых, естественно, mn штук) были ровно всеми словами длины n в нашем алфавите, по одному разу каждое.
Доказательство. Рассмотрим следующий ориентированный граф. Вершины соответствуют словам длины n−1. Ориентированное ребро идет из одной вершины в другую, если последние n−2 буквы в слове, нумерующем первую вершину, совпадают с первыми n−2 буквами в слове, нумерующем вторую вершину. Таким образом, ребра соответствуют словам длины n.
Лемма. Если в связном (т.е. не распадающемся в несвязное объединение компонент) ориентированном графе в каждую вершину входит столько же ребер, сколько из нее выходит, то существует ориентированный цикл, проходящий все ребра по одному разу.
Идея доказательства леммы: показать, что для любого ориентированного цикла, проходящего каждое ребро не более чем по одному разу, но оставляющего некоторые ребра непройденными, найдется более длинный ориентированный цикл, тоже проходящий каждое ребро не более чем по одному разу. С этой целью, разомкнуть исходный цикл в подходящей вершине и достроить к нему новый добавочный цикл, проходящий через эту вершину.
Имеется алфавит из m букв. Доказать, что можно расставить по кругу mn букв (существует циклическое слово такой длины в этом алфавите) так, чтобы отрезки длины n в этом слове (которых, естественно, mn штук) были ровно всеми словами длины n в нашем алфавите, по одному разу каждое.
Доказательство. Рассмотрим следующий ориентированный граф. Вершины соответствуют словам длины n−1. Ориентированное ребро идет из одной вершины в другую, если последние n−2 буквы в слове, нумерующем первую вершину, совпадают с первыми n−2 буквами в слове, нумерующем вторую вершину. Таким образом, ребра соответствуют словам длины n.
Лемма. Если в связном (т.е. не распадающемся в несвязное объединение компонент) ориентированном графе в каждую вершину входит столько же ребер, сколько из нее выходит, то существует ориентированный цикл, проходящий все ребра по одному разу.
Идея доказательства леммы: показать, что для любого ориентированного цикла, проходящего каждое ребро не более чем по одному разу, но оставляющего некоторые ребра непройденными, найдется более длинный ориентированный цикл, тоже проходящий каждое ребро не более чем по одному разу. С этой целью, разомкнуть исходный цикл в подходящей вершине и достроить к нему новый добавочный цикл, проходящий через эту вершину.
