¿Cuántas porciones de pizza tenemos?

Question

Al principio, teníamos un trozo entero de pizza y dos personas. Así que cortamos la pizza en dos trozos del mismo tamaño. Pero al mismo tiempo, hay otro tipo se unió a nosotros. Tuvimos que volver a cortar la pizza en tres partes del mismo tamaño. Esta vez sólo tuvimos que cortar dos veces más. Pero esto aún no era el final, la gente seguía llegando una a una. Cada vez dividíamos la pizza en partes iguales con un mínimo de veces de corte. $^{1}$ Al final, vinieron un total de N personas. ¿Cuántas porciones de pizza tenemos? ¿Hay alguna forma de averiguarlo rápidamente?

$^{1}$ Los cortes no se pueden reorganizar para obtener un número menor de cortes. Cortamos la pizza en su sitio, en $n$ líneas igualmente colocadas, como en la imagen de abajo.

Answer 1

Podemos identificar los ángulos de los cortes con números reales entre $0$ y $1$ . En el paso $n$ cortamos en ángulos $0, \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}$ . (Como se aclara en los comentarios, el problema parece suponerlo. Nótese que hay una cuestión más interesante si se nos permite reordenar las piezas, o si se nos permite colocar los cortes en cualquier ángulo arbitrario siempre que las líneas estén igualmente espaciadas).

Por lo tanto, el número de rebanadas después de $n$ personas se han unido es igual al número de números racionales en el intervalo $[0,1)$ con denominador a lo sumo $n$ . El número con denominador exactamente $k$ es $\phi(k)$ , donde $\phi$ es la función totiente que cuenta cuántos números hay entre $0$ y $k-1$ (numeradores) son relativamente primos a los $k$ (el denominador).

Por lo tanto, el número total de rebanadas después de $n$ personas se han unido también se puede expresar como $$ a_n = \sum_{k=1}^n \phi(k). $$

La secuencia $a_n$ comienza $2, 4, 6, 10$ como en su foto. Puede encontrar más información sobre la secuencia en esta página de la Enciclopedia Online de Secuencias de Números Enteros .

Answer 2

En primer lugar, consideremos que los recortes son los $n$ -raíces de la unidad en el plano complejo y que $\phi(n)$ sea la función totiente de Euler. Afirmo que el número de cortes es $\sum_{k=1}^n\phi(k)$ . Para ver esto primero observamos que para algún primo $p$ el único divisor es $1$ debemos hacer $p-1$ nuevos cortes ya que esas raíces de la unidad no podrían ser cortadas todavía o implicaría un divisor de $p$ . Ahora para algunos compuestos $n$ a medida que atravesamos el círculo tomando múltiplos de $e^{2\pi i/n}$ entonces observamos que para algún corte $e^{2 \pi i k/n}$ que ya se ha hecho implica que $k$ divide $n$ . Esto significa que haremos un nuevo corte cuando $k$ es relativamente primo de $n$ . Sumando estos cortes para cada $n$ nos da el resultado.