cadena de bits más corta cuya repetición infinita es diferente después de la inversión

Marvin Minsky me hizo la siguiente pregunta durante mi examen oral:cadena de bits más corta cuya repetición infinita es diferente después de la inversión

Como una hormiga camina imprime un número binario (por ejemplo, 101) cada vez que se da un paso. ¿Cuál es la longitud mínima, en dígitos, el número binario puede ser para que sea posible decir en qué dirección está viajando la hormiga sin mirar al principio o al final de la cuerda? La hormiga te dice el número binario.

Ejemplo: número binario de la hormiga es 101 y, por lo tanto, la hormiga deja un rastro que se ve así: 101101101101101101101. Tenga en cuenta que no hay manera de saber de qué manera la hormiga está viajando. Por lo tanto, este número particular no funciona (pero puede haber un número binario de tres dígitos que sí lo hace).

Ejemplo: El número binario de la hormiga es 011 y, por lo tanto, la hormiga deja un rastro que se ve así: 011011011011011011. Una vez más, no hay forma de saber hacia dónde se dirige la hormiga sin mirar los extremos de la cuerda .

¿Cuál es la respuesta a esta pregunta? Tenga en cuenta que la respuesta no puede ser solo un ejemplo de un número binario que funcione. La respuesta debe incluir una prueba de que no funcionará ningún número binario de longitud inferior a n-1, donde n es la longitud del número binario de ejemplo que funciona. Una prueba por enumeración exhaustiva está bien, pero desagradable. :)

Fuente

2009-07-17 user128807

¿Está pidiendo una prueba matemática rigurosa, o simplemente la eliminación de nombres? – gbn

¿Por qué la primera pista no va "101101101101101"? –

Votado para cerrar como "no relacionado con la programación". Es posible que desee probar un foro de matemáticas para preguntas como esta –

Otro enfoque sería apartarse de números binarios. Vuelva a formular la pregunta como "¿Cuál es el patrón más corto posible que es direccional si se permite usar cualquier número de símbolos únicos?"

La respuesta aquí es 3 (por ejemplo A; B; C o #; &; @) ya que 2 no funciona. Entonces, cuando tienes un patrón como ABC, queda claro en qué dirección está caminando la hormiga.

O ... CABCABCABCABCAB ... (de izquierda a derecha) O ... CBACBACBACBACBA ... (de derecha a izquierda)

Ahora, cuántos dígitos binarios qué se necesita para escribir un patrón de 3 símbolos en Ternary (base-3)?

Dos dígitos binarios permiten escribir una sola cuaternario (-4 base) dígitos, que es la primera base mayor que o igual a 3.

Así: (2 dígitos-per-símbolo) multiplicado por (3 símbolos) = 6 dígitos binarios.

Fuente

2009-07-22 14:56:59

+1, muy intuitivo. –

Si bien esto obtiene la respuesta correcta, no estoy seguro de que sea el sonido. Primero, con 2 bits está desperdiciando el cuarto símbolo posible, por lo que "podría haber sido" que el patrón general se puede representar en menos de 2 * bits numSymbols. En segundo lugar, la inversión a nivel de bits y los cambios de un bit significan un código de dos bits simple se rompe: por ejemplo, si A = 00, B = 01, C = 10, entonces ABC ... es 000110 ... que no tiene la propiedad deseada. A = 00, B = 10, C = 11 es una instancia específica que no tiene este problema, pero no ha demostrado que esto funcione en general. –

La respuesta real es AB AB AB. – Joshua

ChssPly76 tiene la respuesta correcta (en mi humilde opinión) en los comentarios anteriores.

6 dígitos, ejemplo 100110.

Fuente

2009-07-21 18:58:29

cadena de bits más corta cuya repetición infinita es diferente después de la inversión

Respuesta

Cuestiones relacionadas