20
правок
Изменения
Нет описания правки
# Покажем, что в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление нуля или единицы) уже были использованы. Рассмотрим первое такое противоречие, то есть уже было два слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
# ЗаметимПокажем, что невозможно вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на 1 единицу и кончающиеся на 0ноль. Докажем, что 2-й второй группы группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность 1 единиц и 0нулей. Рассмотрим два словаЗаметим, которые могут быть от него образованы: {bc..yz}01 и что слово {bc..yz}00также не в коде. Они могли Оно могло быть получены получено из слов 1{abcbc..yz}0 и 0{(not a)bc..yz}0, одно из которых есть рассматриваемое {abc..yz}0. Но даже если второе другое слово встречается и встретилось в коде, то в коде не может быть более одного мы бы получили из рассматриваемых словнего {bc..yz}01, значит аторого не может быть вообще следуя алгоритму (так как алгоритм по возможности добавляет 1, а не 0причем это слово точно встретится в первый раз). То есть Таким образом, слово {bc..yz}00 тоже нет точно не в коде. Так эту Такую же цепочку рассуждений можно продолжить до провести и для слова 00{c..yz}000 , и так далее. На n-ом шаге мы бы получили утверждение, что слова из n нулей тоже нет в коде, и прийти пришли бы к противоречию. А раз 2-й группы нетЗаметим, то не может быть что исходя из третьего и четвертого шагов, все слова вида {abc..yz}1-йвстречаются строго раньше {abc..yz}0, так как если которые точно записаны в коде есть словокод. Таким образом, кончающееся на 0слов, то мы не можем получить егопопавших в код, если не было слова с таким же началом, но с единицей в конценет.
