Configurazioni
buon caldo a tutti!!
allora...ho una configurazione di n punti "bianchi" e n punti "neri" in un piano...dimostrare che esiste sempre un modo di collegare ogni punto nero con un punto bianco in modo tale che due qualsiasi collegamenti (supposti rettlinei) non si inrocino mai
good luck
ciao
allora...ho una configurazione di n punti "bianchi" e n punti "neri" in un piano...dimostrare che esiste sempre un modo di collegare ogni punto nero con un punto bianco in modo tale che due qualsiasi collegamenti (supposti rettlinei) non si inrocino mai
good luck
ciao
Risposte
Mi sembra strano... Immagina di avere quattro punti in sequenza A, B, C, D su di una stessa retta. A e B sono neri, mentre C e D sono bianchi. E' ovvio che i collegamenti si sovrappongono.
Non ho capito bene, la linea deve essere un'unica linea spezzata che li unisce tutti? Senza alzare la matita dal foglio? Scusa, ma non è chiaro il problema.
"fields":
Mi sembra strano... Immagina di avere quattro punti in sequenza A, B, C, D su di una stessa retta. A e B sono neri, mentre C e D sono bianchi. E' ovvio che i collegamenti si sovrappongono.
Dice su di un piano, non su di una retta.
@laura
no la linea non è una spezzata...è semplicemente un segmento che unisce un solo punto bianco con un solo punto nero...e bisogna dimostrare che si può fare questo per ogni punto nero (e quindi anche ogni punto bianco) senza che vi siano due collegamenti che si intersecano...
@fields
sì il caso dei punti allineati è una cosa a parte...si potrebbe dire che quello è un caso 1-dimensionale...
no la linea non è una spezzata...è semplicemente un segmento che unisce un solo punto bianco con un solo punto nero...e bisogna dimostrare che si può fare questo per ogni punto nero (e quindi anche ogni punto bianco) senza che vi siano due collegamenti che si intersecano...
@fields
sì il caso dei punti allineati è una cosa a parte...si potrebbe dire che quello è un caso 1-dimensionale...
Cioè, ma tu dici "qualunque sia la configurazione"?
"jack":
@fields
sì il caso dei punti allineati è una cosa a parte...si potrebbe dire che quello è un caso 1-dimensionale...
Prendi 5 punti A,B,C,D,E sulla stessa retta in sequenza, con A,B neri e C,D,E bianchi. Prendi un punto nero $F$ fuori dalla retta. Ancora una volta non è possibile il collegamento senza intersezioni.
l' esempio postato è però equivalente al caso della retta...infatti escludendo il punto $F$ e un punto C D E qualsiasi, si ritorna al caso dei punti allineati...che ovviamente va scartato (questa è una imprecisione che non ho scritto, e che hai fatto benissimo a farmi notare), per il resto, si tratta di una configurazione qualunque...
ciao
ciao
Quindi devono essere a 3 a 3 non allineati?
oh yes 
Se si riuscisse a far vedere che per ogni configurazione esiste una retta che lascia dalla medesima parte un medesimo numero di punti bianchi e neri avremmo finito.... (la tesi seguirebbe per induzione)...
- questo è vero per n pari, ove vale addirittura l'esistenza di una linea che dimezza i punti neri e contemporanemante i punti bianchi, chiamata halving-line per l'appunto se non erro... (e con questo lemma, supposto noto, la tesi è dimostrata per tutte le potenze di 2,ndr )
- per n dispari... ancora non so... devo vedere... magari si riesce sempre a lasciare n bianchi ed n neri da una parte ed n+1 neri ed n+1 bianchi dall'altra, ma per ora è una congettura (andrò a vedere se la dimostrazione del lemma sopra si riesce ad adattare);
questa tra le vie che ho provato mi è parsa la più percorribile... che ne dici jack???... a proposito, bentornato
- questo è vero per n pari, ove vale addirittura l'esistenza di una linea che dimezza i punti neri e contemporanemante i punti bianchi, chiamata halving-line per l'appunto se non erro... (e con questo lemma, supposto noto, la tesi è dimostrata per tutte le potenze di 2,ndr
)- per n dispari... ancora non so... devo vedere... magari si riesce sempre a lasciare n bianchi ed n neri da una parte ed n+1 neri ed n+1 bianchi dall'altra, ma per ora è una congettura (andrò a vedere se la dimostrazione del lemma sopra si riesce ad adattare);
questa tra le vie che ho provato mi è parsa la più percorribile... che ne dici jack???... a proposito, bentornato
ciao thomas!
grazie per il bentornato, la tua sembra una via promettente (ua, si nu muostro ) anche se bisogna lavorarci un po'...la soluzione che conosco io segue una via differente, ma nenache di troppo...
buon lavoro
ciao
grazie per il bentornato, la tua sembra una via promettente (ua, si nu muostro
) anche se bisogna lavorarci un po'...la soluzione che conosco io segue una via differente, ma nenache di troppo...buon lavoro
ciao
Sono andato con una piccola ricerca (insomma, ci ho messo un pò) su internet a ritrovare la dimostrazione (o quasi) del lemma della retta "dimezzatrice"...
http://olimpiadi.ing.unipi.it/oliForum/ ... sc&start=0
avete letto un pò di quei post?
Beh così ad occhio mi pare che argomenti simili (prendendo le rette che lasciano alla loro destra n+1 punti neri), dimostrino anche la congettura che mancava che citavo. Infatti supponiamo che la retta con angolazione iniziale che lascia a destra n+1 punti neri ed a sinistra n punti neri, lasci a destra n+1+k punti rossi con k>0. Dopo un giro di 180° si riuscirà ad ottenere ancora la stessa retta con a destra ora $(2n+1)-n-1-k=n-k$ punti rossi. Visto che se $k>0$ vale $n-k
(naturalmente si deve distinguere il caso con k<0)
Se quanto sopra andasse bene (almeno, + o -) la dimostrazione sarebbe conclusa...
http://olimpiadi.ing.unipi.it/oliForum/ ... sc&start=0
avete letto un pò di quei post?
Beh così ad occhio mi pare che argomenti simili (prendendo le rette che lasciano alla loro destra n+1 punti neri), dimostrino anche la congettura che mancava che citavo. Infatti supponiamo che la retta con angolazione iniziale che lascia a destra n+1 punti neri ed a sinistra n punti neri, lasci a destra n+1+k punti rossi con k>0. Dopo un giro di 180° si riuscirà ad ottenere ancora la stessa retta con a destra ora $(2n+1)-n-1-k=n-k$ punti rossi. Visto che se $k>0$ vale $n-k
(naturalmente si deve distinguere il caso con k<0)
Se quanto sopra andasse bene (almeno, + o -) la dimostrazione sarebbe conclusa...
Dai su qualcuno che "checki" (ovvero controlli ed approvi) o smentisca la sol sopra...
così magari poi pensiamo a qualche altro metodo
... visto che ho utilizzato forse un lemma un pò pesante 
sempre che il caldo non lo impedisca!!
e poi provandoci avevo trovato un piccolo risultato non banale (ma facile!) utilizzando una tecnica utile in vari casi... (magari a te può essere utile jack per la normale )... che vi propongo a questione finita...
così magari poi pensiamo a qualche altro metodo
... visto che ho utilizzato forse un lemma un pò pesante sempre che il caldo non lo impedisca!!e poi provandoci avevo trovato un piccolo risultato non banale (ma facile!) utilizzando una tecnica utile in vari casi... (magari a te può essere utile jack per la normale
)... che vi propongo a questione finita...
uppiamo... io un pò di tempo ce l'avevo dedicato per trovare quanto sopra (e non parlo della ricerca su internet della dimostrazione del lemma, ma per trovare l'idea con cui utilizzare il lemma)...
... nessuno che sia in grado di dire se quanto ho fatto è corretto??
boh... se continua così jack posta pure la tua soluzione
... nessuno che sia in grado di dire se quanto ho fatto è corretto??
boh... se continua così jack posta pure la tua soluzione
up!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo