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