Самая короткая строка битов, бесконечное повторение которой отличается после реверсирования

Marvin Minsky спросил меня следующий вопрос во время моего устного экзамена:

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

Пример: двоичное число муравья равняется 101 и, следовательно, муравей оставляет след, который похож на это: 101101101101101101101. Обратите внимание, что нет никакого способа сказать, какой путь муравей перемещается. Следовательно, это конкретное число не работает (но может быть три двоичных числа цифры, которые делают).

Пример: двоичное число муравья равняется 011 и, следовательно, муравей оставляет след, который похож на это: 011011011011011011. Снова, нет никакого способа сказать, какой путь муравей перемещается, не смотря на концы строки.

Что ответ к этому вопросу? Обратите внимание, что ответ не может только быть примером двоичного числа, которое работает. Ответ должен включать доказательство, что никакое двоичное число длины, меньше, чем n-1 будут работать, где n является длиной двоичного числа в качестве примера, которое работает. Доказательство исчерпывающим перечислением в порядке, но неприятное.:)

10
задан Gilles 'SO- stop being evil' 29 August 2012 в 22:36
поделиться

2 ответа

Другой подход - отойти от двоичных чисел. Перефразируйте вопрос так: «Какой самый короткий из возможных шаблонов является направленным, если разрешено использовать любое количество уникальных символов?»

Ответ здесь - 3 (например, A; B; C или #; &; @) т.к. 2 не работает. Итак, когда у вас есть образец, подобный ABC, становится ясно, в каком направлении идет муравей.

Либо ... CABCABCABCABCAB ... (слева направо) Или ... CBACBACBACBACBA ... (справа налево)

Теперь, сколько двоичных цифр нам нужно, чтобы записать шаблон из трех символов в троичной системе (основание-3)?

Две двоичные цифры позволяют вам запишите одну четвертичную (основание 4) цифру, которая является первой цифрой с основанием больше или равной 3.

Таким образом: (2 цифры на символ), умноженные на (3 символа) = 6 двоичных цифр.

6
ответ дан 4 December 2019 в 02:26
поделиться

ChssPly76 имеет правильный ответ (IMHO) в комментариях выше.

6 цифр, например 100110.

2
ответ дан 4 December 2019 в 02:26
поделиться
Другие вопросы по тегам:

Похожие вопросы: