Usted está organizando una fiesta. Sin embargo, el número de invitados a asistir a su fiesta, puede ser cualquier cosa, desde $a_1$, $a_2$, $\ldots$, $a_n$, donde el $a_i$'s son enteros positivos. Usted quiere estar preparado, por lo que desea cortar un pastel en trozos más pequeños. Las piezas no son necesariamente de igual tamaño. El requisito es que, no importa cómo muchos clientes vienen (que se han conocido antes de la distribución de la torta), usted será capaz de dar a cada uno de ellos algunos pedazos de la torta sin tener que cortar el pastel más para que todo el mundo va a obtener la misma cantidad de pastel. ¿Cuál es el mínimo número de piezas de su pastel que usted tendrá que cortar?
Trivialmente, si $n=1$, entonces la respuesta es $a_1$. La respuesta es también conocido por $n=2$, $a_1+a_2-\gcd\left(a_1,a_2\right)$ (si se preguntan por qué la teoría de grafos es en la etiqueta, es porque la única prueba de que sabe que a mí por la $n=2$ de los casos se realiza a través de un gráfico-teórico argumento). Suponemos que la respuesta, en general, es $$m:=\sum_{j=1}^n\,(-1)^{j-1}\,g_j\,,$$ donde $$g_j:=\sum_{1\leq k_1<k_2<\ldots<k_j\leq n}\,\gcd\left(a_{k_1},a_{k_2},\ldots,a_{k_j}\right)$$ para $j=1,2,\ldots,n$ ($g_1$es simplemente $a_1+a_2+\ldots+a_n$). Es fácil de cortar la torta en $m$ piezas para satisfacer las condiciones requeridas.
Al parecer, la conjetura es falsa para $n>2$ (ver Dividiendo el conjunto en una cantidad mínima de piezas para distribuir igualmente entre los diferentes grupos.). Sin embargo, espero que mi suposición no está lejos de la respuesta correcta.
EDIT: El $n=2$ caso $\gcd\left(a_1,a_2\right)=1$ apareció como un problema para la Primavera del Concurso, de Un Nivel, de el Torneo de las Ciudades de 1990. Ver https://keoserey.files.wordpress.com/2012/12/imtot-book-3.pdf.
Temas Relacionados:
http://puzzling.stackexchange.com/questions/19870/nine-gangsters-and-a-gold-bar/19881#19881
Respuestas
¿Demasiados anuncios?
Aquí está una sletch de la prueba de que si $\gcd(n,6)=1$, entonces usted puede satisfacer $3$, $4$, o $n$ a los huéspedes con $n+4$ piezas.
Imaginamos que la torta de tamaño $12n$. Lo cortamos en $n-4$ piezas, cada una de tamaño $12$, y lo que sobra se corta en ocho piezas, de los tamaños de las $1,2,4,5,7,8,10,11$ $n+4$ piezas en total, como se había prometido.
Ahora podemos compartir el pastel en partes iguales entre $n$ clientes: $n-4$ de ellos obtienen de una sola pieza de tamaño $12$, y cada uno de los otros cuatro invitados $11+1$ o $10+2$ o $8+4$ o $7+5$.
Si tenemos cuatro personas, queremos dividir la torta en cuatro porciones, cada una de tamaño $3n$. Si distribuimos la $n-4$ $12$ piezas entre nuestros cuatro invitados tan uniformemente como sea posible, vamos a tener tres huéspedes con $3n-9$, y uno de los invitados con $3n-21$, o vamos a tener tres huéspedes con $3n-15$ y un invitado con $3n-3$. [Por supuesto, esta afirmación requiere comprobación, pero en realidad es una simple cuestión de considerar los casos de $n=4k+1$$n=4k+3$, y haciendo la media aritmética.] En el primer caso, el déficit con $8+1$, $7+2$, $5+4$, y $11+10$. En el segundo caso, con $11+4$, $10+5$, $8+7$, y $2+1$.
Por último, si tenemos tres de los invitados, que desea dividir el bizcocho en tres partes, cada una de tamaño $4n$. De nuevo, distribuir el $n-4$ $12$ piezas tan uniformemente como sea posible. Terminamos con tres personas en $4n-16$, o bien con dos personas a $4n-20$ y uno de los invitados a $4n-8$ [y de nuevo me dejo a usted para comprobar la aritmética aquí]. En el primer caso, traemos a todos los invitados hasta el $4n$ por la distribución de $11+5$, $10+4+2$, y $8+7+1$. En el segundo caso, $11+5+4$, $10+8+2$, $7+1$.
EDIT: creo más en general, si $3<a<b$ son parejas coprime, entonces usted puede guardar $3$, $a$, o $b$ a los clientes contentos con $a+b$ piezas. No voy a tratar de escribir una prueba, solo presenta un ejemplo con $a\ne4$.
Para $3,5,7$, deje que el pastel se han tamaño de $3\times5\times7=105$. Dividir el bizcocho en siete pedazos de tamaño de $15$, luego se dividió en cinco de esos pedazos en $1$ y $14$, $2$ y $13$, $4$ y $11$, $5$ y $10$, $7$ y $8$ (que de todas las posibles divisiones, evitando sólo aquellos que no prime a $3$). En total, $5+7=12$ piezas.
Compartir entre siete personas es evidente.
Compartir entre cinco personas se logra por $15+5+1$, $15+4+2$, $14+7$, $13+8$, $11+10$.
Compartir entre tres personas se logra por $15+15+5$, $14+13+8$, $11+10+7+4+2+1$.
También podemos hacer $4,5,7$ en doce pedazos, el uso de dos $20$s y cada número impar de$1$$19$, inclusive.
Esta es una prueba para el caso de que $n=2$, según lo solicitado por vonbrand.
Considere la posibilidad de un bipartito gráfico $G\left(V_1\cup V_2,E\right)$ donde $V_1$ $V_2$ son bipartitas conjuntos con $\left|V_1\right|=a_1$ $\left|V_2\right|=a_2$ tal de que representan a los clientes que pueden asistir a la fiesta y $\left\{v_1,v_2\right\}$ $v_1 \in V_1$ $v_2\in V_2$ están en el conjunto de borde $E$ si y sólo si existe un trozo de este pastel, que será entregada a $v_1$ si $a_1$ invitados a venir tal que esta misma pieza se dará a $v_2$ si $a_2$ invitados a venir. Claramente, necesitamos al menos $|E|$ trozos de pastel. Se verificará que $|E|\geq a_1+a_2-d$ donde $d:=\gcd\left(a_1,a_2\right)$. Esto es suficiente para mostrar que existen en la mayoría de las $d$ componentes conectados en $G$.
Supongamos que $C$ está conectado a un componente de $G$. Escribir $C_1$ para el conjunto de vértices de $C$ $V_1$ $C_2$ para el conjunto de vértices de $C$$V_2$. Cada huésped en $V_1$ es de $\frac{1}{a_1}$ cantidad de pastel, mientras cada huésped en $V_2$ es de $\frac{1}{a_2}$ cantidad de pastel. Por lo tanto, la cantidad total de la torta dado a los huéspedes en $C_1$$\frac{\left|C_1\right|}{a_1}$, mientras que la cantidad total de la torta dado a los huéspedes en $C_2$$\frac{\left|C_2\right|}{a_2}$. Desde $C$ es un componente conectado, los huéspedes en $C_1$ deben consumir la misma cantidad de pastel que se consume por los huéspedes en $C_2$; de lo contrario, habrá un borde que va de $C_1$ o $C_2$ a un vértice fuera de $C$. Ergo, debemos tener $$\frac{\left|C_1\right|}{a_1}=\frac{\left|C_2\right|}{a_2}\text{ or }\frac{a_2}{d}\left|C_1\right|=\frac{a_1}{d}\left|C_2\right|\,.$$ Por lo tanto, $\frac{a_1}{d}$ divide $\left|C_1\right|$$\gcd\left(\frac{a_1}{d},\frac{a_2}{d}\right)=1$. De allí, $\left|C_1\right| \geq \frac{a_1}{d}$ (y de manera similar, $\left|C_2\right| \geq \frac{a_2}{d}$).
Por lo tanto, cada componente conectado de $G$ tiene al menos $\frac{a_1}{d}$ vértices en $V_1$. Por lo tanto, $G$ puede tener en la mayoría de $d$ de los componentes conectados. La prueba se ha completado.
P. S. Usted probablemente puede ver por qué este tipo de argumentos no funciona para $n>2$. Si tratamos de crear $n$-partita gráficos de la misma manera, entonces el número de piezas de pastel está relacionado con el número de $n$-camarillas de este gráfico. Sin embargo, no todos los $n$-las pandillas pueden ser asignados a un pedazo de la torta, y dos pedazos de pastel puede producir dos no-idéntico, pero de carácter discontinuo, $n$-camarillas. Por lo tanto, para $n>2$, creo que necesitamos una nueva forma de resolver el problema. Podríamos ser capaces de usar $n$-uniforme hypergraphs en la lucha contra el caso de $n>2$.
