Se numeran del 1 al n las posiciones de un círculo. Se elimina primero al 2, luego al 4, luego al 6, y así sucesivamente, continuando de manera circular entre las posiciones aún no eliminadas, hasta dejar una sola. ¿Qué número sobrevive en función de n?
Home > Riddles > Una eliminación cíclica
Una eliminación cíclica
Hints
Show hints
- Tras la primera vuelta quedan solo impares; renumera y reaparece el mismo problema.
- Prueba primero con n pequeñas y con potencias de 2.
- Si n=2^m + l, sobrevive 2l+1 (en binario: mueve el primer 1 al final).
Solution
Show full solution
Respuesta: si n = 2^m + l con 0 <= l < 2^m, el superviviente es 2l + 1.
Equivalente:J(n) = 2*(n - 2^floor(log2(n))) + 1.
Idea: en la primera pasada desaparecen los pares y quedan 1,3,5,.... Al renumerar esas posiciones como 1,2,3,..., obtienes el mismo problema a escala menor. Esa recurrencia lleva a la fórmula cerrada.
Lectura binaria elegante: escribe n en binario, mueve el primer 1 al final; ese binario es el superviviente.
Ejemplo: 13 = 1101_2 -> 1011_2 = 11.
Related riddles
Keep practicing
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.