Счёт вслепую. Занятие 4

Пользуясь цифрами 0 и 1, несложно записать натуральное число. Сложение в столбик позволяет прибавить к этому числу единицу. Такой способ записи и изменения числа требует в некоторых ситуациях прочитать и изменить все цифры.
А если число большое и мы хотим читать и писать поменьше цифр, но можем быстро запросить любые цифры числа «вразбивку»? Разумеется, придётся изменить представление числа. С середины 20-го века известны коды Грея; нам всё равно потребуется иногда читать число целиком, зато менять надо будет лишь по одной цифре за раз.
А можно ли прибавить к числу единицу, не читая всего числа? Оказывается, можно. Известен способ, при котором увеличение числа из $n$ двоичных цифр на каждом из $2^n$ шагов оставляет непрочитанной одну цифру. Можно ли лучше? Наверное чуть лучше можно, точно не знаю. Но хотя бы половину цифр прочитать придётся. Причём увеличить запись, тратящую $n+1$ цифру на числа от 1 до $2^n$, можно прочитав лишь около $\log n$ цифр, но вот если использовать все комбинации, то придётся читать не меньше $\dfrac12 n$.
Конструкции — после того, как они были один раз предъявлены — объясняются совсем просто; а для нижней оценки надо пошаманить с перестановками и их чётностью, чем мы и займёмся.
Предварительных знаний не потребуется. Я надеюсь, что всем слушателям удастся понять из рассказанного не меньше, чем они пожелают.