Es que siempre hay una solución para este embalaje problema con las limitaciones de colisión

Question

Tengo seis cajas de diferentes tamaños. Dos cajas son de color rojo, dos cajas son de color azul y las dos cajas son de color verde.

Sólo hay una dimensión que importa. Deje $r$ $r'$ ser el tamaño de los cuadros de color rojo. Asimismo, para $b$$b'$, e $g$$g'$.

Yo sé que:

$\begin{align*} r + b + g &= 1\\ r' + b' + g' &= 1\\ r + r' &\le 1\\ b + b' &\le 1\\ g + g' &\le 1 \end{align*}$

I want to put boxes of size r, g and b in "line", one after the other. I also want to put r', b' and g' in line, one after the other. These two lines formed by the two sets of boxes are to be put in parallel, side by side, touching each other.

Example:

 _____________________________________________
|            |                       |        |
|     r      |           g           |   b    |
|____________|_______________________|________|
|       |             |                       |
|   g'  |      b'     |          r'           |
|_______|_____________|_______________________|

Can I always (for all values of $r,r',g,g',b,b'$ respetando las condiciones arriba) encontrar una disposición que no tiene casillas de un mismo color se toquen entre sí (como en el ejemplo de arriba) ?

Gracias,

Un

Answer 1

** EDIT: Mi algoritmo original tenía una falla, pero ahora está corregido

El diseño que se utiliza es

En lugar de un ancho total de 1, lo hice 1000 para que yo pudiera ver mejor los cuadros en mi pantalla. Se puede convertir de nuevo al dividir cada cuadro de ancho por 1000.

Se me ocurrió el siguiente algoritmo que ordena los cuadros para que no se toquen.

Si cualquier color + su primer equivale a 1

1. Puesto que el color en las posiciones 1 y 6

2. Rellene los otros colores en cualquier forma.

Otra cosa

1. Encontrar el mayor cuadro de color. Si está en la Fila 1, el nombre de L, más el nombre de L'. (Si dos o más cuadros son igualmente el más grande, el nombre de cualquiera de uno de ellos.) Si se nombra a L, entonces el nombre de ese mismo color en el cuadro de otras fila L'. Si se nombra a L', entonces el nombre de ese mismo color en el cuadro de otras fila L.

2. En la misma fila que el más grande de la caja de color (L o L'), encontrar el más pequeño cuadro de color. Si usted está en la Fila 1, el nombre de S, otro nombre S'. Si se nombra a S, entonces el nombre de ese mismo color en el cuadro de otra fila de S'. Si se nombra a S', entonces el nombre de ese mismo color en el cuadro de otras fila S.

3. En la misma fila que el más grande de la caja de color (L o L'), encontrar el cuadro sin nombre. Si usted está en la Fila 1, el nombre de M, otro nombre es M'. Si se nombra a M, entonces el nombre de ese mismo color en el cuadro de otra fila de M'. Si se nombra a M', entonces el nombre de ese mismo color en el cuadro de otras fila M.

4. Si la fila con el mayor cuadro de color es la Fila 2, a continuación, vaya al #5

Si M es mayor o igual a L", a continuación, utilizar este arreglo

Otro uso de esta disposición:

Skip #5 - hecho el trabajo.

5. Si M es mayor o igual a L, a continuación, utilizar este arreglo

Otro uso de esta disposición:

He creado un programa de C# para calcular valores aleatorios de acuerdo con las condiciones, aplicar el algoritmo anterior, y mostrar el resultado. (Nota: La fila con el mayor cuadro muestra siempre en la parte superior (Fila 1), incluso si la mayor caja era de un primo.)

Aquí hay algunas capturas de pantalla:

Me encontré con una simulación con más de 2 millones de pistas, y no hay contra-ejemplos fueron encontrados.