When all else fails, linear momentum will be conserved. (Because we can ALWAYS define a closed system, then there is no net external force and hence momentum will be conserved.)

Take your system to be the spaceship of mass M. The explosion adds no net external forces on the mass. Thus we know that, since the spaceship was initially at rest:

0 = m1*v1 + m2*v2 <-- v1 and v2 are velocities and hence vectors

Now mechanical energy is NOT conserved, but we DO know how much kinetic energy was put into the system: E.

Since there was no initial kinetic energy to the system we know that the energy added by the explosion is equal to the kinetic energy of the pieces:

E = (1/2)m1*v1^2 + (1/2)m2*v2^2

So. From the momentum equation we get:

v2 = -(m1/m2)*v1

Thus

E = (1/2)m1*v1^2 + (1/2)m2*(m1/m2)^2*v1^2

E = (1/2)[m1 + m1^2/m2]*v1^2

E = (m1*m2+m1^2)/(2*m2)*v1^2

v1 = sqrt{(2*E*m2)/(m1^2 + m1*m2)}

Thus v2 = -(m1/m2)*sqrt{(2*E*m2)/(m1^2 + m1*m2)}

So

v1 + v2 = [1 - m1/m2]*sqrt{(2*E*m2)/(m1^2 + m1*m2)}

v1 + v2 = [(m2 - m1)/m2]*sqrt{(2*E*m2)/(m1^2 + m1*m2)}

Something I haven't mentioned yet, but should be obvious: M = m1 + m2 (we aren't relativistic here, presumably.)

Now, what bothers me here is the "minimum relative speed" of the particles. Written as it is in the question this is v1 + v2 where v1 and v2 are vectors. This makes sense, except that v1 + v2 is a relative velocity, not a relative speed. BUT the minimum relative velocity of the particles should be 0: if the explosion is perfectly symmetric m1 = m2 and the particles will have equal speeds. In fact, if you look at the equation I derived for v1 + v2 you will see that if m1 = m2, v1 + v2 is indeed 0.

I am suspecting the question is asking for something else, but I can't figure out what it is.

-Dan