Así que esta pregunta está inspirada en el siguiente hilo: https://forums.factorio.com/viewtopic.php?f=5&t=25008
En él, el cartel examina un $8$ -(de la que hablaremos más adelante) que no satisface una propiedad deseable, a la que denominó rendimiento universal ilimitado.
¿Qué es un $n$ -¿equilibrador de correa? Es una configuración de correas (que mueven artículos alrededor), y divisores (que toman dos correas adentro y balancean sus artículos en las dos correas en el lado de la salida), que balanceará la entrada de todos los $n$ cinturones de entrada en todos $n$ correas de salida. Se utilizan con frecuencia en las grandes fábricas para mover grandes cantidades de artículos a una variedad de áreas diferentes de una manera en la que no hay un valor de cinta de artículos que se acumula (más artículos que llegan a ella de lo que puede utilizar) resulta en otros proyectos que no reciben rendimiento completo (o al menos tanto como pueden utilizar).
La propiedad deseada denominada rendimiento universal ilimitado es la siguiente: Supongamos que sólo $k$ de la $n$ las cintas de entrada están recibiendo entrada (se supone que la entrada es completa; es decir, se supone que las cintas de entrada están saturadas), y que todas menos $k$ de las cintas de salida están atascadas y no tienen caudal (ya están llenas de artículos y nada se mueve en esas cintas). Entonces la entrada completa en esas $k$ cinturones de entrada se pueden proporcionar a través de la $k$ cintas de salida (que tienen el mismo rendimiento máximo, por lo que ninguna cinta de salida puede gestionar un rendimiento superior al de una cinta de entrada). Esto significa básicamente que $n$ -el equilibrador de banda nunca es un cuello de botella, independientemente de las limitaciones actuales de entrada o salida (qué carriles están recibiendo entrada/están disponibles para la salida).
La pregunta que tengo es la siguiente: ¿Siempre es posible crear un $n$ -equilibrador de correas que satisface la condición de rendimiento universal ilimitado para cualquier $n$ ? No, para que $n$ ¿Es posible? (claramente, $n=2$ funciona debido al comportamiento de los divisores)
Tengo algunas ideas sobre cómo enfocar este problema, pero no estoy ni cerca de tenerlo resuelto. La primera idea es cómo representar el problema: Podemos representar las cintas de entrada y las cintas de salida como vértices de un grafo dirigido. Las entradas son fuentes (grado de entrada=0) y las salidas son sumideros (grado de salida=0). El equilibrador son los vértices de entrada y salida junto con un conjunto de intermedio vértices que representan divisores que tienen $1\leq$ grado de entrada,grado de salida $\leq$ 2 (una o dos aristas dirigidas apuntan a ellas y una o dos proceden de ellas) y las aristas dirigidas asociadas. Mirando el problema de esta manera, es fácil ver que a necesario es que la entrada de cualquier cinta pueda llegar a cualquier cinta de salida (es necesaria porque si no, considere el caso de toda la entrada en una cinta de entrada y todas menos una cinta de salida atascadas con rendimiento 0; en tal caso, si no puede dirigir la entrada de esa cinta de entrada a la cinta de salida no obtendrá ningún rendimiento), pero esta condición no es suficiente (se ha demostrado teórica y experimentalmente que múltiples ejemplos que satisfacen esta condición no tienen la propiedad deseada de rendimiento ilimitado universal).
Una cosa importante a tener en cuenta es que las correas se pueden enrutar en otros cinturones a través de cinturones subterráneos, por lo que no es necesaria la planitud del gráfico descrito. El hecho de que los divisores tengan un comportamiento muy específico es importante para este problema: siempre intentarán equilibrar las salidas si no hay retrasos, por lo que, en un escenario sin retrasos, la salida de cada cinta que sale de un divisor es la mitad de la salida de cada cinta que sale de un divisor. total en sus dos cintas de entrada. Sin embargo, si una de las cintas de salida está atascada y no hay producción, toda la producción se fusionará en la cinta "libre". hasta su límite de rendimiento. Si, en este caso, más de una cinta entra en un divisor, entonces ambos las cintas de entrada empezarán a formar cuellos de botella (el rendimiento efectivo de cada cinta será la mitad del máximo, porque esa es la cantidad de cinta de salida saturada que procede de la cinta de entrada dada). A veces, un retraso es sólo un reducción en el rendimiento (debido a un cuello de botella en algún punto de la línea) en tal caso, un divisor seguirá dividiendo la entrada por igual hasta el rendimiento reducido en la cinta de menor rendimiento, después de eso, todos El caudal restante se lanza a la cinta con capacidad adicional hasta que ésta se satura, y si hay alguna entrada más que llegue al divisor dado, entonces ambos de sus correas de entrada empezará a atascarse.
Este fenómeno de acumulación puede dar lugar a algunos comportamientos muy sutiles. Lo que hace que la simple asignación de pesos a las aristas dirigidas en el gráfico descrito anteriormente (restringido a un valor de $[0,1]$ donde $1$ está saturado y $0$ no hay rendimiento) es inadecuado para describir el problema. Por ejemplo, un divisor que provoque un atasco con cierto caudal, pero no suficiente para evitar el atasco, puede provocar una reducción del caudal para otro de la cinta de salida del divisor, desplazando una mayor parte de su entrada a la otra cinta de salida (lo que podría provocar que un divisor situado más adelante en esa cinta se convirtiera de repente en un cuello de botella y se acumulara, etc.).
Mi sospecha de experimentar un poco, así como algunos trabajos teóricos mirando cómo divisores están dividiendo las entradas me lleva a conjeturar que no es posible que todos los $n$ y que los candidatos más probables son potencias de $2$ . Incluso entonces, para potencias superiores a $1$ todavía podría ser imposible debido a impar #s de cinturones que tienen entrada necesaria para llegar al mismo número de cinturones de salida (y si el equilibrio impar #s de cinturones no es posible, entonces la condición universalmente rendimiento ilimitado podría no ser satisfactoria debido a estos casos).
