Problema inverso de Josephus

Question

El problema de Josephus es bastante conocido - cada $m$ -a persona en el círculo de $n$ la gente es asesinada - la pregunta es ¿en qué parte del círculo estaba la última persona en pie?

Hagamos una inversión de ese problema y preguntemos

¿Cuál es el menor paso $m$ para lo cual $k$ -la última persona en pie en un círculo de $n$ personas ( $n$ y $k$ se dan)?

Hay dos preguntas lógicas que hacer:

¿Esta es la $m$ ¿siempre existen? (Conjetura: sí - las pruebas informáticas demuestran que es correcta hasta $n=300$ ).

¿Cuál es el límite superior de $m$ ? $\text{lcm}(1,2,\ldots,n)$ parece lógico, pero ¿hay algo más bajo (las pruebas informáticas muestran una serie de valores atípicos que dificultan la estimación de dicho límite).

Answer 1

Aquí está el máximo de $m$ sobre todo $k$ por el hecho de ser fijo $n$ trazado sobre $n$ junto con $nH_n$ el valor esperado para el el problema del coleccionista de cupones (donde $H_n$ es el $n$ -número armónico):

El hecho de que los valores parezcan dispersos en torno a este valor de expectativa indica que puede ser una buena heurística considerar que la última persona en pie es seleccionada uniformemente al azar, independientemente para todos $m$ . Si es así, la "probabilidad" de que haya algún contraejemplo más allá de $n=1000$ (hasta el que he probado) debería ser excesivamente pequeño. Es difícil cuantificar con exactitud cuán pequeño es, ya que la heurística podría no ser válida hasta $m=\operatorname{lcm}(1,\dotsc,n)$ pero incluso si sólo es válido hasta $n^2$ la "probabilidad" de que alguien sobreviva a todo $n^2$ atentados contra su vida serían más o menos

$$n\left(1-\frac1n\right)^{n^2}\approx n\mathrm e^{-n}\;,$$

por lo que el número esperado de contraejemplos más allá de $n=1000$ sería aproximadamente

$$\int_{1000}^\infty n\mathrm e^{-n}\mathrm dn=1001\mathrm e^{-1000}\approx5\cdot10^{-432}\;.$$