Variación del problema de Josephus

Question

Supongamos que tenemos un círculo de $2n$ de las personas, donde las primeras personas de $n$ son buenos y el % de personas $n+1$$2n$son malos. Podemos escoger siempre un número entero $q$, tal que si ejecutamos a sucesivamente cada persona de $q$-th en el círculo, sobrevivirá a los buenos de la $n$.

He intentado resolver algunos casos simples y encontrar los siguientes ejemplos: $$\begin{array}{c|cccc} n & 1 & 2 & 3 & 4 \\ \hline q & 2 & 7 & 5 & 30 \end{matriz}$$ pero aún no he encontrado un enfoque general. ¿Cómo abordarlo?

Answer 1

Esto no necesariamente producirá el más pequeño número entero $q$, pero produce un número entero que funciona: que $q=\text{lcm}(n+1,n+2,\ldots,2n)$. Tal $q$ tocará de los malos en orden inverso, empezando por persona $2n$ y terminando con persona $n+1$.

Nota: Si no importa un número mucho mayor, o no quieren molestarse informática un mínimo común múltiplo, $q=(2n)!$ hará el truco.

Answer 2

Por cierto, creo que el problema hace un IMPRESIONANTE rompecabezas/enigma, y es posible que desee enviar esta de más a la desconcertante página de Pila.

Así, aunque esto no es una fórmula, como Cipra la respuesta, creo que es una solución novedosa y reduce en gran medida el trabajo necesario para resolver el problema. Me considera una configuración como la siguiente imagen, yo también espero que sea útil mi explicación:

Comenzamos con un sencillo pero potente observación acerca de cómo el voto de obras:

1. En cada iteración, una persona, llamada grupo de dos ($n+1, ..., 2n$), deben ser votados.
2. Por lo tanto, en la última iteración, tenemos un nodo a la izquierda en el grupo dos.
3. Y podemos empezar a contar lo que en este punto de dos maneras: (a) desde el último nodo en sí, o (b) desde el siguiente nodo es decir, la primera persona en el círculo.

Desde aquí podemos ver que cualquiera que sea el número de $q$ es decir, debe ser de la forma $b(n+1)$ o $b(n+1)+1$ algunos $b \in \mathbb{N}$ (żpor Qué?). Así, tenemos una relación muy estrecha lista de elección para empezar.

Pero, que podemos hacer mejor; sabemos que para cualquier adivinar $x$ de $q$, $x \not\equiv 1,2,3,...,n$ (mod $2n$). Esto es debido a que acabaríamos en uno de los nodos en el grupo uno, ($1, ..., n$).

Además, incluyendo Cipra la respuesta, usted puede obtener esta lista a muy pocas posibilidades.

Yo soy, también, todavía tratando de encontrar una mejor manera, así que puede editar esto con un método más rápido.