¿QUIÉN ES EL TURCO?
Un
problema clásico para determinar, entre un grupo de n personas capturadas en un
abordaje de piratería, cuál debía ser arrojada al mar, consistía en colocarlas
en círculo e ir contándolas de k en k, eliminando cada vez a la que coincidía
con el final de la cuenta. Cada persona eliminada no era contada de nuevo, y se
proseguía hasta que quedaba una sola, que pasaba a ser la designada por el
sorteo.
Por
ejemplo, sean 7 personas, y contemos de 4 en 4. Las que van quedando tras cada
conteo son:
1234567, 123567,
23567, 2357, 237, 23, 2.
Entre
estas personas siempre había un turco, y la “gracia” del problema era colocarlo
(en segunda posición en este caso) de modo que a él le correspondiera alimentar
a los tiburones.
Llamaremos pues “el turco” a la persona destinada mediante este tipo de sorteo, que es fácilmente simulable por ordenador. Obsérvese que el procedimiento guarda alguna semejanza con los residuos modulares, pero los resultados son mucho más imprevisibles.
Empecemos
analizando los resultados para valores bajos de n. Cuando n = 2, al variar k,
el turco va ocupando las posiciones 12121212...
Obsérvese
que la longitud de este ciclo vale precisamente 2. ¿Se producirán ciclos
similares para valores superiores de k? Así es, como podemos ver a
continuación:
n=3
El
ciclo tiene longitud 2 ´
3, y es 332-211.
n=4
Longitud:
3 ´ 4. Ciclo: 4112 2323 3441
n=5
Longitud:
12 ´ 5. Ciclo: 53412 44124 53251 34113 41254 23513 35134 21452 35523 51431
24522 45231
n=6
Longitud:
10 ´ 6. Ciclo: 651514 335243 314131 251515 546363 414132 262625 646364
435242 362621
n=7
Longitud:
60 ´ 7. Por simplicidad, no reproducimos el ciclo.
La
longitud de los ciclos oscila muy irregularmente, pero al final de cada uno el
turco ha correspondido un número igual de veces a cada persona.
¿Cuál
es el enfoque teórico del problema para determinar previamente la posición del
turco?
SOLUCIÓN A
¿QUIÉN ES EL TURCO?
Recuerdo
que el problema del turco salió a colación durante una de las reuniones de
Mensa Madrid hace años. Conozco una fórmula que da el lugar del turco en el
caso k = 2. Consiste en restar a 'n' (número de personas) la mayor potencia de
2 que no supera n, la diferencia se multiplica por 2 y se suma 1, y ése es el
lugar del turco. Por ejemplo, si hay
digamos 47 personas restamos 32 (mayor
potencia de 2 que no es mayor que 47): 47 - 32 = 15, y el lugar del turco es 15 × 2 + 1 = 31.
La
justificación no es difícil. Primero se comprueba que si el número de personas
es una potencia de 2, entonces el turco está en el lugar número 1. Si no es una
potencia de 2 entonces empieza a
eliminar personas hasta que quede una potencia de dos y la siguiente persona
será la primera de un ciclo con un
número de personas igual a una potencia de 2, y por lo tanto esa persona será el turco.
No
sé de ninguna fórmula que dé directamente el lugar del turco t(k,n) para otros valores de k, pero no es difícil obtener
una fórmula recursiva para t(k,n):
t(k,1) = 1
t(k,n) = (t(k,n-1) + k) mod n para n > 1
donde x mod n =
resto de dividir x por n (resto cero se interpreta igual a n). Por ejemplo para
k = 4 y valores de n = 1,2,3,4,... obtenemos los
siguientes valores de t(k,n) (calculados a mano
usando la fórmula recursiva):
1 1 2 2 1 5 2 6 1 5 9 1 5...
Miguel A. Lerma