Is there always a solution for this packing problem with collision constraints

Question

I have six boxes with different sizes. Two boxes are red, two boxes are blue and two boxes are green.

There is only one dimension that matters. Let $r$ and $r'$ be the size of red boxes. Similarly for $b$ and $b'$, and $g$ and $g'$.

I know that:

$\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'$ respecting the conditions above) find an arrangement that does not have boxes of the same color touching each other (such as the one in the example above) ?

Thanks,

A

Answer 1

** EDIT: My original algorithm had a flaw, but it is now corrected

The layout I used is

Instead of a total width of 1, I made it 1000 so that I could better see the boxes on my screen. It can be converted back by dividing each box's width by 1000.

I came up with the following algorithm that arranges the boxes so that they do not touch.

If any color + its prime equals 1

1. Put that color in positions 1 and 6

2. Fill in the other colors in any way.

Else

1. Find the largest colored box. If it is in Row 1, name it L, else name it L'. (If two or more boxes are equally the largest, name any one of them.) If you named L, then name that same colored box on the other row L'. If you named L', then name that same colored box on the other row L.

2. On the same row as the largest colored box (either L or L'), find the smallest colored box. If you are in Row 1, name it S, else name it S'. If you named S, then name that same colored box on the other row S'. If you named S', then name that same colored box on the other row S.

3. On the same row as the largest colored box (either L or L'), find the unnamed box. If you are in Row 1, name it M, else name it M'. If you named M, then name that same colored box on the other row M'. If you named M', then name that same colored box on the other row M.

4. If the row with the largest colored box is Row 2, then skip to #5

If M is greater than or equal to L', then use this arrangement

        Else use this arrangement:

Skip #5- You are done.

5. If M' is greater than or equal to L, then use this arrangement

        Else use this arrangement:

I created a C# program to calculate random values respecting the conditions, apply the algorithm above, and display the result. (Note: The row with the largest box always displays on top (Row 1), even if the largest box was a prime.)

Here are some screenshots:

I ran a simulation with over 2 billion runs, and no counter-examples were found.