Una eliminación regular, repetida en círculo, acaba escondiendo una estructura sorprendentemente limpia. El patrón tarda un poco en asomar, pero cuando lo hace ya no admite dudas.
Una eliminación cíclica
Enunciado
Las posiciones de un círculo se numeran del 1 al \(n\).
Se elimina primero la posición 2, luego la 4, luego la 6, y así sucesivamente, continuando de forma circular entre las posiciones que sigan vivas, hasta que solo queda una.
¿Qué posición sobrevive al final?
Ver solución
Solución
Respuesta: Si
$
n = 2^m + l
\qquad\text{con}\qquad
0 \le l < 2^m,
$
entonces la posición superviviente es
$
2l+1.
$
La pauta se aprecia enseguida en los primeros casos:
$
1\to1,\quad 2\to1,\quad 3\to3,\quad 4\to1,\quad 5\to3,\quad 6\to5,\quad 7\to7,\quad 8\to1.
$
Cada vez que el número de posiciones es una potencia de 2, sobrevive la posición 1.
¿Por qué? En la primera vuelta desaparecen todas las posiciones pares y sobreviven exactamente las impares:
$
1,3,5,\dots
$
Si se renumeran como \(1, 2, 3, \dots\), el problema resultante es del mismo tipo, solo que con la mitad de participantes.
Al escribir \(n = 2^m + l\), la parte \(2^m\) se consume en estas reducciones sucesivas y el exceso \(l\) determina cuánto se desplaza el superviviente desde la posición 1. De ahí que el resultado sea \(2l+1\).
Existe también una regla binaria equivalente: toma la escritura binaria de \(n\), desplaza el primer bit al final, e interpreta el resultado de nuevo en binario.