abbinamento traminte segmenti senza intersezioni

rand · Messaggio da **rand** » 23 set 2009, 02:34

Ci sono N punti bianchi ed N punti neri nel piano tali che nessuna retta passa per più di 2 punti, bianchi o neri che siano. Dimostrare che comunque siano disposti i punti si possono sempre tacciare N segmenti con un estremo bianco e l'altro nero tali che nessuna coppia di segmenti si intersechi. (NB: ciò implica che due segmenti non hanno mai un estremo in comune)

Tibor Gallai · Messaggio da **Tibor Gallai** » 23 set 2009, 02:53

Sono abbastanza convinto che sia comparso su uno dei primissimi giornalini. A me lo raccontò il buon Abramo nel 2001, e sembra un classico sempreverde del problem solving.

Nonostante tutto, stranamente nel forum non l'ho trovato. Quindi buon lavoro!

dario2994 · Messaggio da **dario2994** » 23 set 2009, 19:22

Questo problema è stato proposto da Gobbino al senior di quest'anno :)