Je me lance, bien conscient de ne pouvoir étonner que par la complexité

S'il y a 1 rouge et 1 noir, l'unique segment existe trivialement
Je suppose donc le problème résolu jusqu'à un certain nombre n de paires de points.

Considérons (n+1) paires de points et traçons le frontière de l'enveloppe convexe* de l'ensemble.
Dans la majorité des cas, les points colorés de cette ligne ne sont pas tous rouges ni tous noirs. Cela me permet de trouver un segment rouge-noir que je trace. Comme il ne reste que n paires de points, toutes du même côté du segment déjà tracé, je sais terminer comme je l'affirme dans mon hypothèse de récurrence.

Reste le cas d'un pourtour 100% rouge ou 100% noir. Disons qu'il est rouge.
Je me positionne sur l'un des points rouges du pourtour et je fais pivoter une droite autour de ce point pour balayer l'enveloppe convexe dans le sens des aiguilles d'une montre. Au départ, les rouges sont majoritaires parmi les points rencontrés mais ils sont minoritaires à la fin. Comme le nombre de points noirs rencontrés n'augmente que de 1 en 1 (jamais 3 points alignés), j'ai forcément obtenu au moins une fois une droite D passant par un noir et partageant équitablement le reste. Je retiens donc le segment rouge-noir correspondant et je termine par mes deux petits groupes équitables, chacun comportant moins de n paires et donc pour lequel je sais faire.

J'espère que mon galimatias est quand même lisible et j'attends impatiemment la solution en deux lignes

*enveloppe convexe : Dans un plan, l'enveloppe convexe peut être comparée à la région limitée par un élastique qui englobe tous les points qu'on relâche jusqu'à ce qu'il se contracte au maximum. (dixit Wikipedia)

Bonne et jolie réponse de scrablor

Il y a encore plus joli mais il faut vraiment y penser ( la solution n'est pas de moi ) . On relie deux à deux et au hasard les points rouges et noirs et on note S la somme des longueurs de tous ces segments . S'il n'y a pas de segments croisés , c'est fini et on a gagné . Sinon on prend au hasard deux segments croisés que l'on décroise comme sur l'illustration ci-dessous .

Bien sûr cette opération peut générer de nouveaux croisements mais par l'inégalité triangulaire on diminue strictement S . Les points étant en nombre fini , S ne peut pas décroitre indéfiniment donc en renouvelant la manoeuvre un nombre de fois suffisant on n'arrive à une situation où on ne peut plus réduire S : il n'y a donc plus de segments croisés .

Amusant , non ?

Vasimolo

Vraiment très jolie...
Ca fait beaucoup de calcul, et il faudrait évité les redondances, mais c'est exactes !