Раскраска диска для определения направления его вращения

Представьте себе вращающийся диск, например DVD. У вас есть в распоряжении черная (Ч) и белая (Б) краски. На краю диска установлен небольшой датчик, который определяет цвет под ним и выдает результат в виде сигнала. Как бы вы раскрасили диск, чтобы было возможно определить направление вращения по показаниям датчика?

Дадим небольшое пояснение к задаче. Первое, что нужно иметь ввиду, это то, что нельзя наблюдать за самим диском. Например, вы сидите в офисе, а диск вращается в закрытой лаборатории. Единственная возможность определить направление вращения — использовать оцифрованные показания датчика, и ничего больше.

Датчик фиксирует цвет точки в непосредственном месте установки в последовательные моменты времени. Показания представляются в виде «ЧЧЧББ...». Задача сводится к такой раскраске диска, где последовательность показаний отличается при вращении в прямую и в противоположную стороны, то есть последовательность не должна быть палиндромом.

Палиндромы — это такие слова или фразы, которые читаются задом наперед так же как и обычным образом. Например: топот, ротор, «лезу в узел». Придумать палиндром не так легко, в то время как привести пример асимметричной фразы очень просто. Может показаться, что так же легко придумать такую раскраску диска, однако возникает две сложности. Во-первых, в постановке задачи мы ограничиваемся только 2 буквами Ч и Б. Во-вторых, нам нужно избавиться от циклического палиндрома, так же, как и от обычного.
Например, нельзя покрасить половину диска в белый цвет, а вторую половину в черный. Показания будут как «ЧБЧБЧБЧБЧБ». В обычном смысле это не палиндром, но это циклический палиндром. То есть, если соединить начало и конец последовательности, то получим одинаковые показания при вращении как по часовой стрелке, так и против. При наблюдении за бесконечным потоком показаний нельзя сказать, в каком направлении вращается такой диск.

Не все регулярные последовательности являются циклическими палиндромами. Если бы нам были доступны 3 цвета: черный (Ч), белый (Б) и красный (К), то можно нарисовать 3 одинаковых по площади сектора разных цветов. Тогда по часовой стрелке показания были бы вроде «ЧЧЧКККБББ», а наоборот «ЧЧЧБББККК». В данном случае они легко различимы. В первых показаниях красный сразу следует за черным, а на вторых показаниях красный следует за белым.

Изначальная постановка задачи не допускает использование третьего цвета, но позволяет взамен использовать раскраску «зебру». Один из трех секторов можно закрасить множеством тонких полос с чередованием черного и белого цветов. Тогда хорошо заметно, когда частые полосы идут после черного сектора (по часовой стрелке) или после белого сектора (против часовой стрелки).

Это решение можно улучшить. Ведь вам не сказано, насколько быстро вращается диск и с какой частотой датчик в состоянии регистрировать изменения цвета (грубо говоря, задержка экспозиции). Диск может вращаться настолько быстро, что датчик будет регистрировать цвет только одного места на диске и пропускать все остальные. Это может ввести в заблуждение при интерпретации полученных показаний.

Очевидно желание сделать меньшее число полос, а сами полосы шире, насколько это возможно. На самом деле достаточно 2 полосы в «полосатом секторе», если, конечно, они противоположного цвета, по отношению к смежным секторам.

При такой раскраске и при условии возможности снятия 6 показаний за 1 оборот, поворот по часовой стрелке будет давать последовательность вроде «ЧЧБЧББ», а против часовой стрелки, эта последовательность будет идти в обратном порядке.

Также представляет интерес похожая задача, где диск уже раскрашен на две половинки в черный и белый цвета. Допускается установка неограниченного числа фиксированных датчиков у края диска. Вопрос: сколько датчиков требуется установить для определения направления вращения?

Все что мы может получить с одного датчика (при новой постановке задачи) — это соотношение черного и белого в покраске, что и так известно (50/50). Если мы возьмем 2 датчика и разместим их диаметрально противоположно, то вновь не получим ничего полезного, так как второй датчик всегда будет давать противоположное показание.

Вместо этого, можно разместить 2 датчика рядом, например первый датчик в произвольном месте, а второй в 10 градусах по часовой стрелке от первого. Большую часть времени оба датчика будут давать одинаковые показания, однако, при смене цветов, один датчик заметит изменение раньше, чем другой.

Показания датчиков могут выглядеть следующим образом:
Датчик 1: ЧЧБББ
Датчик 2: ЧЧЧББ

Такие наблюдения означают, что переход Ч-Б фиксируется первым датчиком раньше, чем вторым. В этом случае переход Ч-Б и сам диск должен вращаться по часовой стрелке. Если это изменение, наоборот, фиксируется вторым датчиком раньше чем первым, то вращение происходит против часовой стрелки.

Разбор взят из книжки «Are You Smart Enough to Work at Google?».