Problema de color salmón de Moshe Rosenfeld

Question

Como una diversión al inicio de esta charla, Moshe Rosenfeld plantea la siguiente pregunta.

Supongamos que hay n salmón comienzan en puntos distintos en una unidad de círculo, cada uno frente a la derecha o en sentido contrario. A una señal, cada salmón se mueve alrededor del círculo en su dirección elegida a una velocidad constante (la misma para todo el salmón). Cuando dos salmón conocer, al instante atrás. Si alguno de salmón nunca vuelve a su punto de partida, se muere. (Si dos salmón reunirán en uno de sus puntos de partida, hay una muerte y no hay cambio de dirección; como Rosenfeld, dice, "la Muerte llega en primer lugar.")

1. Es cierto que todo el salmón morirán?
2. (suponiendo que la respuesta a la parte 1 es sí) Dar un algoritmo para encontrar el último sobreviviente.

He pasado una cierta cantidad de tiempo en autobuses y aviones jugando con este. Es muy fácil demostrar que cada configuración es preperiodic, como un comienzo. Tengo algunas ideas acerca de cómo podría terminar. Finalmente decidí sólo para buscar más información sobre el problema, sin éxito.

Uno de los temas de su charla es cómo algunos de los problemas se vuelven populares y algunos recoger el polvo en la estantería. Es esto último lo que le sucedió a este problema?

Su segunda pregunta es un poco misterioso. El problema de instalación en sí es algorítmica en la naturaleza, entonces, ¿qué significa? Hay algo además de la "elegancia" que distinga el tipo de respuesta que debe tener en la mente de un estúpido respuesta como que "sólo ver el salmón"? ("Tiempo de funcionamiento" podría ser una respuesta, pero parece probable que simplemente dejar que el salmón nadar no tomaría mucho tiempo.)

Realmente estoy formulando tres preguntas sobre este tema.

1. Hice esta pregunta nunca se resuelven o se toman en serio? Si es así, ¿dónde?
2. Hay una natural, nonvacuous interpretación de la segunda parte de a la pregunta?
3. ¿Cuál es la solución? (Esto es en realidad el subquestion soy menos interesado en el, pero se sintió mal no de preguntar.)

(Por favor, siéntase libre de re-tag, que todavía tiene que acostumbrarse a que las cosas aquí).

Answer 1

Ah, la ironía. Ahora que he pidió públicamente a la pregunta, yo prácticamente viaje a través de una referencia.

Acabo de encontrar este papel de Rosenfeld de 2008, que tiene gran superposición con la charla mencionado en mi post original. En el documento se muestra que hay configuraciones iniciales que no conducen a la extinción, a pesar de que poco se avanza en cómo uno podría reconocer estas configuraciones especiales de antemano.

(Todavía estoy interesado en las respuestas a la subquestion 2 anterior).