Questo e\' un problema abbastanza classico (magari e\' gia\' stato postato da qualcuno), la cui soluzione assomiglia vagamente a quella di un problema che ho visto sul forum non molto tempo fa (non vi dco quale perche\' altrimenti e\' troppo facile!)
<BR>Sia dati 2n punti sul piano a tre a tre non allineati. La meta\' sono bianchi e la meta\' sono neri. Dire se e\' possibile o no tracciare n segmenti tali che ciascun segmento collega un punto bianco ad un punto nero, tali che ogni punto dato sia il vertice di esattamente un segmento e tali che nessun segmento intersechi nessun altro.
<BR>Buon divertimento!
segmenti che si incrociano
Moderatore: tutor
il numero delle combinazioni di collegamenti possibili tra punti bianchi e neri e un numero finito. per ognuna di queste configurazioni si calcoli la sommatoria delle lunghezze dei segmenti.
<BR>ci sarà una configurazione la cui sommatoria è minima.
<BR>in questa configurazione certamente non ci sono segmenti che si intersecano, infatti se ci fossero due segmenti che si intersecano, presi gli stessi quattro estremi e uniti in modo da non intersecarsi, la somma delle loro lunghezze sarebbe minore di quella precedente e anche la sommatoria sarebbe minore della precedente, ma questo non è possibile perchè si era scelta la configurazione con sommatoria minima.
<BR>
<BR>ci sarà una configurazione la cui sommatoria è minima.
<BR>in questa configurazione certamente non ci sono segmenti che si intersecano, infatti se ci fossero due segmenti che si intersecano, presi gli stessi quattro estremi e uniti in modo da non intersecarsi, la somma delle loro lunghezze sarebbe minore di quella precedente e anche la sommatoria sarebbe minore della precedente, ma questo non è possibile perchè si era scelta la configurazione con sommatoria minima.
<BR>