Aquí está una feria de secuenciación del problema que no coincidan con los habituales de la feria-problemas de división. Creo que, como aquellos, la respuesta también debe ser el Thue-Morse secuencia ("equilibrado alternancia"), porque el mismo razonamiento heurístico que sugiere que es la manera más justa no funciona aquí como bien, pero el problema no parece reducir a ellos, por lo que no es obvio. (Ver aquí para más información sobre el uso de Thue-Morse para la feria de la división, o la anterior MathOverflow pregunta.)
De todos modos, el problema se encuentra en la etapa de sorprendente (como se usa en ciertas competitivo de los juegos de video para la selección del escenario :) ). Hay dos jugadores y $n+1$ objetos ("etapas"). Los dos jugadores tienen diferentes preferencias respecto a las etapas (idealmente, frente preferencias, pero vas a ver a continuación por qué no asumimos que). Los dos jugadores se turnan (en algún orden, por lo que la pregunta) extracción ("notable") etapas que no han sido afectadas; una vez que una única etapa es la de la izquierda, la etapa en la que está seleccionada (ambos jugadores "get" es). La pregunta, entonces, es ¿cuál es el mejor orden para la etapa sorprendente; como se mencionó anteriormente, sospecho que debe ser Thue-Morse (un jugador golpea a 0, el otro jugador golpea a 1), por las mismas razones por las que esta es la respuesta al viejo problema de lo que para tomar turnos en una justa división.
Por supuesto, esto plantea la cuestión de cómo estamos formalización de este y lo que queremos decir por "justo". Voy a presentar aquí la formalización del problema de que (después de discutir esto con otras personas) creo que es lo mejor, pero las respuestas a otras maneras de formalizar también sería ACEPTAR siempre que no trivializar el problema.
Así que ... tenga en cuenta que si los jugadores asignar las etapas de valores opuestos (es decir, están de acuerdo acerca de que las etapas de cómo dar mucha ventaja a oms), como era de esperar, luego de la sorprendente orden es irrelevante, siempre y cuando ambos jugadores tienen el mismo número de golpes, sin importar el orden, la mediana de la etapa serán seleccionados. Así que en lugar de tener que asumir los jugadores pueden estar en desacuerdo acerca de que las etapas ventaja que. También, ya que sólo puede lidiar con el orden de las etapas aquí, no vamos a permitir que ellos tengan arbitraria de valores numéricos como en la feria de la división problema; más bien, vamos a suponer que cada jugador se le asigna el $n+1$ etapas, los valores de $0, 1, \ldots, n$, por lo que el valor de una etapa a un jugador sólo depende de donde cae en la preferencia de pedidos.
Ahora, desde la información perfecta hace que el problema trivial, vamos a ir todo el camino en la dirección opuesta -- cada jugador preferencias son uniformemente al azar; o más bien, cada jugador ve la otra preferencias como uniformemente al azar. Lo que queremos comparar, entonces, y para hacer tan iguales como sea posible, es el valor esperado de que el jugador 1 obtiene (cuando el jugador 2 huelgas de forma aleatoria), vs el valor esperado de que el jugador 2 recibe (cuando el jugador 1 golpea al azar).
(Estoy bastante seguro de que, en esta formulación, se puede asumir que cada jugador siempre huelgas su preferido de menos el escenario en cada paso, y que no hay ninguna ventaja de que se aparta de esta. Pero obviamente me corrija si estoy equivocado, no...)
Así, por ejemplo, en este modelo, si $n=2$, entonces el primer jugador a la huelga obtiene un valor esperado de $3/2$ (eliminar sus menos preferido escenario y conseguir uno de los dos restantes al azar), mientras que el segundo jugador a la huelga obtiene un valor esperado de $5/3$ (tienen un $2/3$ probabilidad de su preferencia etapa no es eliminada, y un $1/3$ probabilidad de que tiene que conformarse con la mediana). Así que tenemos una diferencia de $1/6$. Ves?
Así que la pregunta es, entonces, es el Thue-Morse llamativo el fin de la feria? O es algo más? Es por lo menos el más hermoso cuando se $n$ es una potencia de $2$, incluso si no podría ser de otra manera?
EDIT: en Realidad, un pensamiento-tal vez debería ser inversa de Thue-Morse? (Como en, si $n=12$, iría $011001101001$ en lugar de $011010011001$; usted acaba de invertir la secuencia, y luego, si es necesario, cambiar los roles de los jugadores con el fin de iniciar con un $0$.) Esto parece posible, porque aquí se va más tarde, en lugar de ir antes, que parece conferir una ventaja. Por supuesto, si $n$ es una potencia de dos, esta distinción es irrelevante, como revertir la secuencia sería simplemente intercambiar los roles de los jugadores.
