El problema de los pistoleros

Pedro Crespo

Noviembre 2002

El número 74 de CAROLLIA, de septiembre de 2002, presenta (página 27) cinco problemas elegidos por M. A. Lerma de los propuestos en news sci.math, el último de los cuales se enuncia así:

Sea un grupo de n pistoleros. Cada uno elige al azar a cualquiera de los otros, y a la señal de «ya» todos disparan y matan al individuo elegido. El proceso continúa hasta que sólo queda un pistolero vivo o hasta que todos han caído muertos. ¿Cuál es el límite, para n tendiendo a infinito, de la probabilidad de que al final quede un superviviente?

-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o

1.  Notaciones

Distinguiremos entre etapa o ronda, nombre con el que nos referiremos a cada tanda de disparos al unísono, y transición, palabra que reservaremos para referirnos a cada uno de los cambios específicos que puede sufrir en cada caso el grupo de n pistoleros.

El número total de transiciones posibles en una ronda para un número inicial de n pistoleros es igual a (n-1)ⁿ, puesto que cada individuo del grupo puede apuntar a cualquier otro de los restantes, pero no a sí mismo. Este número alcanza rápidamente valores muy elevados: bastan 19 pistoleros para que el correspondiente número de transiciones sea del orden del número de Avogadro ( » 6×10²³, moléculas por gramo-mol).

También es fácil demostrar que es posible cualquier transición (n, m) que pasa de un grupo de n pistoleros a otro de m, siempre que se cumpla 0 £ m £ (n - 2).

2.  Primeros valores

La evolución del problema exhibe las características de un proceso estocástico, que suele tratarse mediante matrices markovianas, cuyos coeficientes son las probabilidades de transición elementales, con la particularidad en este caso de que el vector de estado es de dimensión variable, n.

La tabla 1 muestra los valores de las probabilidades finales x¹, correspondientes al estado final de un pistolero vivo, para un número inicial de pistoleros desde n = 0 hasta n = 11, calculadas mediante ordenador. El programa efectúa el recuento de todas las transiciones elementales posibles, obteniendo así las probabilidades de transición, es decir los coeficientes de las matrices de transición; a continuación aplica al correspondiente vector de estado dicha matriz hasta alcanzar la fase final de un pistolero vivo, o de ninguno en su caso. La segunda columna de la tabla 2 indica el número máximo de etapas. Llevar más adelante este método de recuento no resulta cómodo en la práctica contando con los recursos de un ordenador personal: para n = 11 es necesario examinar cien mil millones de casos.

n	etapas	x^1
11	5	0.55678
10	5	0.55475
9	4	0.53225
8	4	0.48904
7	3	0.43886
6	3	0.41614
5	2	0.46875
4	2	0.59259
3	1	0.75
2	1	0
1	0	1
0	0	0

Tabla 1: Vector de estado final hasta n = 11.

3.  Descenso del número de pistoleros.

Para el cálculo del número más probable de pistoleros que quedan vivos por etapa podemos suponer que la elección de pistoleros apuntados (elegidos como blanco) se lleva a cabo de modo sucesivo en lugar de simultáneo (el resultado ha de ser el mismo), y que los disparos se distribuyen proporcionalmente al número de pistoleros apuntados en relación con los que quedan sin apuntar en cada caso.

En cuanto a la restricción que prohíbe los «suicidios» (imagen brindada por Josep Maria Albaigès), hay que considerar que tiene carácter simétrico, pues afecta por igual a todo el conjunto de pistoleros. También es posible suponer que los disparos son libres (es decir, se permiten los suicidios) puesto que entre su número y el anterior existe la relación nⁿ/(n -1)ⁿ, que tiende rápidamente al número e, y puede considerarse por tanto como un factor constante, independiente del número de pistoleros.

Razonando en términos de las proporciones de disparos y de pistoleros vivos con respecto al número total al inicio de la ronda, para un incremento Dx de la proporción de disparos, suficientemente pequeño, el aumento de la proporción y de pistoleros no apuntados obedecerá a una relación del tipo

Dy = - y Dx

que como es sabido responde, en un modelo continuo, a la función

y = e^-x

Como en nuestro caso la proporción de disparos es x = 1 (tantos disparos como pistoleros), el número más probable de pistoleros vivos será del orden de n/e » 0.37.n, siendo n el número inicial de pistoleros. El número más probable de rondas antes de alcanzar el estado final, r será por consiguiente tal que verifique

donde k deberá ser un número próximo a la unidad. Ajustando este parámetro a partir del resultado de simulaciones estadísticas, tenemos que el número r(n) más probable de etapas para un número inicial n de pistoleros se corresponde con la fórmula

Los valores etf calculados mediante la fórmula anterior están en muy buen acuerdo con los obtenidos mediante simulaciones, ets, como puede verse en la tabla 2. El número de ensayos empleados en las simulaciones se ha calculado para un intervalo de confianza de a = 99%, con un error del 1%; para los valores señalados con asterisco se ha relajado el intervalo de confianza al 95%, para ahorrar tiempo de cálculo. Como puede verse, la correspondencia se mantiene válida incluso para el valor n = 11; este caso se confirma por la vía del recuento exacto.

Pistoleros	etf	ets
11	3.73	3.77
10^3	6.73	6.75
10^4	9.04	9.04
10^5	11.34	11.33
5.10^5	12.95	12.96
10^6	13.64	13.65
(*) 1.5.10^6	14.05	14.05
(*) 2.10^6	14.33	14.33

Tabla 2: Números promedio de etapas calculados según fórmula y obtenidos mediante simulación.

3.1  Propagación de las probabilidades.

Acabamos de ver que estadísticamente el descenso del número de pistoleros tras cada ronda de disparos se lleva a cabo según la razón 1/e. Los valores mostrados en la tabla 1 resultan suficientes para establecer la pauta general que siguen las probabilidades en todo el rango de los números enteros. Podemos considerar el proceso de etapas o rondas de disparos como el de una aplicación que se efectúa repetidas veces, ronda tras ronda, hasta terminar en un estado estable, con un solo individuo vivo o bien con todos eliminados. Dado que 4.e » 11, el intervalo de valores conocidos de la probabilidad buscada, comprendido entre n = 4 y n = 11, actúa a modo de «trampa» a la que se ve conducida la mayor parte de las transiciones que se inician con un número cualquiera de pistoleros, por grande que éste sea. Los valores finales de la probabilidad serán en cada caso valores próximos a los del referido intervalo.

También podemos considerar la aplicación inversa del mencionado producto de aplicaciones, como si contempláramos filmada y presentada al revés en el tiempo la cascada de descensos que sufre un número inicial n de pistoleros, a través de las rondas sucesivas. En tal caso podemos concluir que el intervalo de valores conocidos de la probabilidad buscada, comprendido entre n = 4 y n = 11, se proyecta hacia los valores crecientes de los enteros n en intervalos cuya amplitud va aumentando según el factor e. Puesto que los valores de la probabilidad que exhiben los elementos del intervalo 4-11 difieren del valor de referencia 0.5, podemos enunciar que

Los valores de la probabilidad buscada al crecer n no convergen nunca, sino que oscilan a modo de una onda cuya amplitud varía poco, tomando valores comprendidos aproximadamente entre 0,45 y 0.54, y cuya «longitud de onda» crece según el factor e aplicado a los intervalos correspondientes a los «valles» y a los «montes». Debido a que en el tramo final se impone la característica discreta del rango de números (y por tanto de los valores de su probabilidad), existirán fluctuaciones, pero tendrán valores pequeños comparados con los de la tendencia general.

	N0	amplitud	ratio
	4.8
valle		3.7
	8.5
monte		5.5
	14
valle		10	10/3.7 = 2.7
	24
monte		15	15/5.5 = 2.72
	39
valle		26	26/10 = 2.6
	65
monte		42	42/15 = 2.8
	107
valle		70	70/26 = 2.69
	177
monte		119	119/42 = 2.8
	296
valle		191	191/70 = 2.73
	487
monte		333	333/119 = 2.79
	820

Tabla 3: Cocientes de amplitudes valles/montes,

hasta n = 820.

La tabla 3 muestra los valores calculados a partir de simulaciones de los puntos que definen aproximadamente los límites de los valles y los montes de la curva sinuosa antes descrita (para valores pequeños de n se ha interpolado para obtener puntos más representativos). Tal como se ha dicho antes, el tamaño de la muestra se ha calculado para un intervalo de confianza del 99% con un error del 1%; dicho tamaño vendrá dado por

donde z_a/2 es el valor z de la curva normal tipificada para la que el área que resta de la curva sea 0.005 (es decir, 1-a = 0.99). Este valor es 2.58. Por otra parte, p^* es una aproximación al valor real de la probabilidad p, que hemos estimado en 0.5. Finalmente, E es el valor del error que aceptamos como límite, en este caso del 1%. Tendremos un tamaño de la muestra, por tanto de

Se ha trabajado en general con 20.000 pruebas. En cuanto al número de pistoleros, se han efectuado simulaciones hasta el valor n = 2 ×10⁶. Lo anterior se aprecia gráficamente en la figura 1, resultado de parte de las simulaciones comentadas.

Figura 1: Frecuencias desde 1 hasta 840 pistoleros.

La tabla 4 deja ver los resultados obtenidos mediante 20.000 simulaciones para diversos valores del número inicial de pistoleros, hasta 10⁶. Se indica la frecuencia hallada (p’), así como los límites inferior y superior del intervalo de confianza (para una muestra algo menor, de 16.641 simulaciones); se anotan también los valores del promedio del número de etapas, m_e y de la desviación tipo de los correspondientes valores. A partir de 10⁶ pistoleros, se ha ampliado el intervalo de confianza al 95%, tal como se ha comentado antes.

Pistoleros	Inf.	p’	Sup.	me	s etapas
10^3	0.4668	0.4759	0.4851	6.7500	0.4966
10^4	0.5018	0.5109	0.5201	9.0422	0.4609
10^5	0.5174	0.5265	0.5356	11.3333	0.4996
5.10^5	0.4892	0.4983	0.5074	12.9561	0.4671
10^6	0.4760	0.4851	0.4942	13.6526	0.5116
(2) 10^6	0.4736	0.4827	0.4918	13.6545	0.5123
(*) 1.5.10^6	0.4897	0.4995	0.5093	14.0514	0.4610
(*) 2.10^6	0.5186	0.5284	0.5381	14.3343	0.5039

Tabla 4: Resultados de simulaciones.

4.  Conclusión

Somos conscientes de que la solución de carácter rigurosamente matemático del problema pasa por la obtención y el estudio de la expresión analítica de la probabilidad final que se busca. Estimamos, sin embargo, que se trata de una tarea muy difícil, por no decir imposible, ya que no es cuestión meramente de hallar el valor general de la probabilidad de una transición determinada, sino que hace falta encontrar y tratar la expresión multilineal de todos los productos posibles de probabilidades que conducen a un pistolero superviviente. Creemos, no obstante, que el resultado hallado puede valer como una respuesta suficientemente razonada al problema. Los ejemplos obtenidos mediante simulación no han de considerarse elementos del argumento, sino que su papel es meramente ilustrativo o de confirmación. En cuanto a los valores hallados para los primeros números mediante el cómputo por ordenador, sí consideramos que forman parte de la demostración, ya que el correspondiente código del programa (ver punto 5) suple al razonamiento; de otro modo no se considerarían probados el teorema de los cuatro colores (Kenneth Appel y Wolfgang Hallen, 1976) ni el del problema de Kepler del empaquetamiento de esferas (Thomas Hales y Samuel Ferguson, 1998), aunque en honor a la verdad es obligado reconocer que a lo que parece quedan

matemáticos puristas que se manifiestan renuentes a aceptar la validez de las demostraciones apoyadas por el recurso al cómputo.

5.  Información ampliada

Un artículo más detallado acerca de este problema, en formato Post-Script está a disposición de aquellos que deseen examinarlo. Además de diversos enfoques del problema, contiene el listado (BASIC y Java) de los programas empleados, y algunas tablas y gráficos adicionales. Tiene 34 páginas y ocupa cerca de 600 KB. Puede solicitarse a la dirección e-mail pcrespo@eic.ictnet.es.

6. Agradecimiento

La ayuda de Josep María Albaigés, con el cual hemos comentado este problema desde buen principio, ha sido inestimable, tanto que sin sus intuiciones y sugerencias estas notas no hubieran sido posibles.