Casos Triviales
Si $n=1$ no necesitamos ningún volteretas. Si $n=2^k$ sólo tenemos que voltear una moneda no trucada $k=\log_2n$ veces.
El Uso De La Moneda De 1
Curiosamente, puede simular una $n$colindado mueren utilizando sólo con monedas de 1 y $\,3 \log n\,$ volteretas. La única salvedad es que no te puedo dar el sesgo de la moneda de forma explícita. Supongamos que tenemos una moneda con un sesgo $b$. Tenemos $n$ carpetas numeradas y queremos asignar cada secuencia individual de $f$ da vuelta a un bin de tal manera que cada contenedor tiene probabilidad de $1/n$. Hay ${f \choose k}$ secuencias que han $k$ cabezas. Para cada una de las $k$, mapa de $\left\lfloor {f \choose k}(n-1)^{-1} \right\rfloor$ de estos a la primera $n-1$ papeleras, y poner el resto en el último bin. Por construcción, la primera $n-1$ recipientes tienen la misma probabilidad, por lo que sigue siendo para mostrar que el último de reciclaje está llena de a $1/n$. Deje $R(b)$ la probabilidad de que el último de reciclaje. Entonces
$$
\begin{align}
R(b) &= \sum_{k=0}^f r_k \; b^k \; (1-b)^{f-k} \\ & \\
r_k &= \small{{f \choose k} \;\; (\text{mod } n-1)}
\end{align}
$$
Tenemos $\,R(0) = 1\,$ y si tomamos $f$ lo suficientemente grande tal que $\,R(1/2)<1/n$, luego por la continuidad y el teorema del valor intermedio debe haber un $b'$ tal que $\,R(b') = 1/n$. Tomando nota de la enlazado $\,R(1/2) < 2^{-f} f n\,$ nos encontramos con que $\,f-\log f > 2 \log n\,$ implica $\,R(1/2) < 1/n$. La elección de $\,f = 3\log n\,$ satisface la desigualdad y la hemos terminado.
Podemos hacer esta bonita si no nos preocupamos acerca de la minimización de $f$. Supongamos $n$ es uno más de una extraña primer y deje $f=n-1$. Entonces no hay restos desde $n-1 \choose k$ es siempre un múltiplo de $n-1$. Por lo tanto $R(b) = b^{n-1} + (1-b)^{n-1}$, lo que claramente tiene una solución $R(b) = 1/n$. Para los casos en que $n$ no es más que una extraña prime, el uso del Teorema de Dirichlet para obtener un múltiplo de $n$ que es.
El Uso De 2 Monedas
Lo mejor que puedo hacer con dos monedas es $\sim 2\log n$ volteretas. Deje una moneda justa y que una moneda tiene el sesgo de $1/n$. Deje $f$ ser tal que $2^f \geq (n-1)^2$. Voltear la moneda no trucada $f$ a veces y el $1/n$ moneda una vez. Hay $2^{f+1}$ total de los resultados, la mitad de los que tienen probabilidad de $\tfrac{1}{ 2^fn}$ y la otra mitad tiene probabilidad de $\tfrac{n-1}{2^f n}$. Etiqueta de la ex $L$ y $H$. Queremos agrupar estos resultados en bandejas de probabilidad $\tfrac{2^f}{2^fn}$.
Agregar la cantidad de $H$ resultados posibles para el primer bin y denotan el número de $h_1 \geq n-1$. Llena el resto con $t_1 < n-1 $ de la $T$ de los resultados. Repita la operación para el siguiente bin y luego el siguiente, y así sucesivamente. Debido a $h_i>t_i$, de $H$ resultados de la primera y se puede llenar el resto de los recipientes con $L$ de los resultados.
Comentarios
Unos más interesantes observaciones. Deje $F(n)$ es el mínimo número de lanzamientos necesarios utilizando un mutable de la moneda (usted puede cambiar el sesgo de cada flip). Si $n=ab$, entonces podemos "rollo" $a$ $b$colindado mueren y el resultado $b (r_a -1) + r_b$. También, si $n = a+b$, entonces podemos dar la vuelta a un $a/n$-sesgada de la moneda y, a continuación, rodar una $a$ o $b$colindado mueren dependiendo de si el tirón de la moneda cae cara o cruz. Así, obtenemos las relaciones de recurrencia
$$ \begin{align}
F(ab) &\leq F(a) + F(b) \\
F(a+b) &\leq 1 + \text{max}\{F(a), F(b)\} \\
\end{align}
$$
La segunda relación nos permite simular una $n=2^k + 2^{\ell}_{(k > \ell)}$colindado muere el uso de 2 monedas y $k+1$ volteretas.
