Compartiendo un pastel entre un número indeterminado de personas.

Question

Esta es una pregunta inspirada en la pregunta "Nueve pandilleros y una barra de oro" en el Desconcierto de Intercambio de la Pila.

Supongamos que usted está lanzando una fiesta, y usted sabe que cualquiera de los 7, 8 o 9 de la gente llegará. Antes de que alguien llegue, quiero cortar la tarta en el menor número de piezas que usted puede dar a todos la misma cantidad.

En este caso, usted puede cortar la tarta en 18 piezas de los siguientes tamaños (esto es conjetura que es el mínimo número de piezas).

$$\frac{1}{168}, \frac{1}{72}, \frac{1}{56}, \frac{1}{36}, \frac{2}{63}, \frac{1}{28}, \frac{23}{504}, \frac{1}{21}, \frac{25}{504}, \frac{5}{84}, \frac{31}{504}, \frac{4}{63}, \frac{19}{252}, \frac{5}{63}, \frac{1}{12}, \frac{47}{504}, \frac{7}{72}, \frac{1}{9}$$

A continuación, puede dividirlo en nueve partes:

$$ \left(\frac{1}{168}, \frac{23}{504}, \frac{5}{84}\right), \left(\frac{1}{72}, \frac{7}{72}\right), \left(\frac{1}{56}, \frac{47}{504}\right), \left(\frac{1}{36}, \frac{1}{12}\right), \left(\frac{2}{63}, \frac{5}{63}\right), \left(\frac{1}{28}, \frac{19}{252}\right), \left(\frac{1}{21}, \frac{4}{63}\right), \left(\frac{25}{504}, \frac{31}{504}\right), \text{ y } \left(\frac{1}{9}\right). $$

En ocho partes: $$ \left(\frac{1}{168}, \frac{1}{28}, \frac{1}{12}\right), \left(\frac{1}{72}, \frac{1}{9}\right), \left(\frac{1}{56}, \frac{1}{21}, \frac{5}{84}\right), \left(\frac{1}{36}, \frac{7}{72}\right), \left(\frac{2}{63}, \frac{47}{504}\right), \left(\frac{23}{504}, \frac{5}{63}\right), \left(\frac{25}{504}, \frac{19}{252}\right), \text{ y } \left(\frac{31}{504}, \frac{4}{63}\right) $$

Y en siete partes: $$ \left(\frac{1}{168}, \frac{1}{72}, \frac{1}{21}, \frac{19}{252}\right), \left(\frac{1}{56}, \frac{1}{36}, \frac{1}{28}, \frac{31}{504}\right), \left(\frac{2}{63}, \frac{1}{9}\right), \left(\frac{23}{504}, \frac{7}{72}\right), \left(\frac{25}{504}, \frac{47}{504}\right), \left(\frac{5}{84}, \frac{1}{12}\right), \text{ y } \left(\frac{4}{63}, \frac{5}{63}\right) $$

---

La pregunta

Estoy interesado en un algoritmo que puede producir un mínimo de pastel de corte. En este caso, se necesitaría en el conjunto de los números posibles de los huéspedes, $\{7,8,9\}$, y la salida de la lista de las fracciones anteriores-o una lista diferente de longitud mínima.

Yo no se preocupan especialmente por la complejidad computacional del programa.

Estoy interesado en demostrar que el programa de salidas el número mínimo de "rebanadas".

---

Más ejemplos

$$ \begin{align*} f(\{2\}) = f(\{1,2\}) &= \left(\frac{1}{2},\frac{1}{2}\right) \\ f(\{n\}) = f(\{1,n\}) &= \underbrace{\left(\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}\right)}_n \\ f(\{2,3\}) &= \left(\frac{1}{3},\frac{1}{3},\frac{1}{6},\frac{1}{6}\right) \end{align*} $$

Answer 1

Es evidente que existe una solución que es de curso muy lento. Ya que usted dijo que usted no está interesado en la complejidad, esto no debería ser un problema.

Así, en primer lugar, hay una clara superior de la estimación para el número de fracciones. Deje $k_1, \ldots, k_r$ ser el posible número de invitados, y deje $N$ ser el mínimo común múltiplo de estos números. A continuación, puede resolver el problema con $N$ fracciones, el corte de la tarta en N porciones iguales.

Introducir $N$ variables $x_1, \ldots, x_N$. Producir todas las particiones de estas variables en $k_1, \ldots, k_r$ subconjuntos. Una variación de estas particiones se compone de una partición en $k_1$ subconjuntos, ..., de una partición en $k_r$ subconjuntos.

Producir un sistema de ecuaciones lineales como sigue: dada la partición en $k_1$ subconjuntos, para cada subconjunto, escribe la ecuación que la suma de las variables en ese subconjunto es $1/k_1$. Mismo para todos los otros $k_i$.

Por último, introducir las restricciones que todas las $x_i$ son no-negativos.

Resolver con el método simplex. Si usted encuentra una solución para cualquiera de las variaciones de las particiones, entonces usted disminuye $N$, y repetir. Supongo que esta última parte se podría hacer más inteligentemente (de alguna manera mirar más profundamente en el método simplex y encontrar una solución con tantos ceros como sea posible?), pero, de nuevo, que sólo están interesados en una teoría correcta del algoritmo, así que hay que ir.

Lo siento si esto no era útil. Solo dime, y luego borro la respuesta.