El problema
Los enteros positivos entre $1$ et $10$ están celebrando unas elecciones. Están sentados alrededor de una mesa circular - $1$ entonces $2$ entonces $3$ y así sucesivamente en el sentido de las agujas del reloj. Empezando por $1$ y en el sentido de las agujas del reloj, cada número entero vota públicamente por un presidente (entre $1$ et $10$ ). Después de todo $10$ enteros han votado, el jugador con más votos gana la elección. El número entero más alto gana en caso de empate.
Cada entero se prefiere a sí mismo para ganar; pero si no puede ganar, prefiere a los otros enteros en orden contrario a las agujas del reloj desde sí mismo. Por ejemplo, el 3 se prefiere a sí mismo, luego el 2, luego el 1, luego el 10, luego el 9, luego el 8, y así sucesivamente. Cada número entero es perfectamente racional y sabe que todos los demás números enteros se comportarán también de forma perfectamente racional.
¿Quién gana las elecciones?
Pensamientos
Este es un rompecabezas curioso, y parece mucho más complicado de lo que parecía inicialmente. Escribí un programa que calcula la respuesta (suponiendo que no haya errores), pero no he podido probarlo.
El reto es que este es un juego con más de dos jugadores, y los argumentos estándar a los que estoy acostumbrado con dos jugadores no parecen aplicarse. Además, muchas de mis intuiciones acaban siendo erróneas. Por ejemplo:
-
Incluso si un conjunto mayoritario de jugadores prefiere el resultado $A$ al resultado $B$ , eso no implica que $A$ sucede y no $B$ . Esto es cierto incluso si el conjunto de jugadores es consecutivo.
-
Tenía la intuición de que votar por el jugador $P$ en su turno debería ayudar siempre al jugador $P$ ganar; en otras palabras, si tienes al menos un movimiento que hace que el jugador $P$ ganar, entonces votar por $P$ es uno de esos movimientos. Pero esto no es cierto. Consideremos el mismo juego con cuatro jugadores $1, 2, 3, 4$ y supongamos que $1$ vota por $2$ . Entonces, si $2$ vota por $2$ , $3$ votará por $3$ et $3$ ganará. Pero si $2$ vota por $1$ entonces $3$ votará por $2$ et $2$ ganará. Así que en este caso, $2$ pueden ganar votando a alguien que no sea ellos mismos.
-
Además, los argumentos basados en la "agrupación de votos" no parecen funcionar. Por ejemplo, la respuesta de joriki argumenta que $n = 1$ no puede ganar, porque aunque $1$ a través de $5$ todos votan por $1$ , $6$ a través de $10$ pueden unir sus votos y votar por $6$ para frustrarlas. Sin embargo, esta intuición no funciona. Por ejemplo, considere $n = 3$ personas en lugar de $10$ El argumento diría que $1$ no puede ganar, porque aunque $1$ vota por $1$ , $2$ et $3$ pueden unir sus votos y votar por $2$ para frustrar $1$ . Sin embargo, $1$ realmente gana en este caso. El problema es que aunque $2$ vota por $2$ , $3$ votará por $3$ en lugar de $2$ -- $3$ no tiene un incentivo para unirse con $2$ .
Nota sobre el origen del problema
Este problema es una variante menor de un problema que acaba de aparecer en el Olimpiada de Matemáticas de Utah 2020 (problema 6), del que fui uno de los redactores del problema. En el concurso se pedía quién ganaba en caso de que las preferencias estuvieran en en el sentido de las agujas del reloj orden, y aquí pregunto por las preferencias en sentido contrario a las agujas del reloj en su lugar.
Tenemos múltiples pruebas para la versión de las agujas del reloj. Por ejemplo, puedo argumentar que (a grandes rasgos), WLOG cada jugador que no gana puede simplemente "pasar" su voto al siguiente jugador, ya que suponiendo que no gane, la preferencia del siguiente jugador es tan buena como la suya. Esto hace que el jugador $6$ ganadora. Sin embargo, no he encontrado un argumento análogo aquí. Las preferencias de los jugadores adyacentes no parecen "alinearse" de la misma manera.
