[G] monocromaticità 2

Simo_the_wolf · Messaggio da **Simo_the_wolf** » 01 gen 1970, 01:33

Visto che si è sollevato il problema sui triangoli monocromatici vorrei proporre qusto (un vecchio cortona mi pare).
 
 Abbiamo che ogni punto del piano è o bianco o nero. Dimostrare che esistono:
 a) rettangoli aventi vertici del medesimo colore;
 b) triangoli equilateri aventi vertici del medesimo colore
 
 Have fun!
 <IMG SRC="images/forum/icons/icon_biggrin.gif">

Mag · Messaggio da **Mag** » 01 gen 1970, 01:33

non entro nel sito da un po\'...che sono i triangoli monocromatici?

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-26 23:00, Simo_the_wolf wrote:
 Abbiamo che ogni punto del piano è o bianco o nero. Dimostrare che esistono:
 a) rettangoli aventi vertici del medesimo colore;
 b) triangoli equilateri aventi vertici del medesimo colore
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Il punto a è già stato risolto nel forum da qualche parte, Pigeonhole di 7 rette parallele e 3 perpendicolari mi pare, ma non ricordo bene.
 
 Sono andato a rileggermelo e visto che non era spiegato bene, lo rifaccio. prendiamo 3 rette parallele e 7 rette perpendicolare a esse, abbiamo che ci sono 6 modi in cui si possono colorare i tre punti di intersezione di ogni retta delle 7 con le tre iniziali, quindi all\'aggiunta della settima retta abbiamo 2 intersezioni colorate allo stesso modo e quindi, dato che per il PigeonHole su 3 punti 2 sono monocromatici, un rettangolo.
 
 Per il punto B, nell\'attesa che qualcuno posti la soluzione concisa ed elegante posto la mia \"brute-force\" sperando che almeno sia corretta.
 
 Costruiamo nel nostro piano un triangolo equilatero ABC e tracciamo le congiungenti i piedi delle altezze. Abbiamo per il PigeonHole che almeno 3 punti sui 6 assegnati sono di uno stesso colore. Per essere comprensibile, rinomino i punti in senso orario partendo da quello in basso a sinistra A,M,B,N,C,O. Analizzeremo solo i \"casi base\" tutti gli altri sono uguali per simmetria. Abbiamo che per non formare un t.eq i tre punti monocromatici (prendiamo bianco per conv.) devono essere o ABO, o AON, o AOC. Analizziamo i tre casi:
 -AOC bianchi
 allora B nero, M nero, N nero, assurdo perchè si forma un triangolo eq.
 -ABO bianchi
 costruiamo il punto M\', simmetrico di M rispetto alla retta AC, abbiamo che C è nero, M è nero, comunque preso M\' si forma un t.eq
 -AON bianchi.
 costruiamo il punto N\', simmetrico di N rispetto alla retta AC, abbiamo che N è nero, M è nero, comunque preso N si ha un t.eq.
 
 EDIT: Aggiunta dimostrazione del punto a [ Questo Messaggio è stato Modificato da: Boll il 27-10-2004 22:30 ]

phi · Messaggio da **phi** » 01 gen 1970, 01:33

Mando anch’io la mia soluzione della b, anche se di certo è lontana dall’essere elegante o concisa... va be’, non è molto che mi dedico a questi problemi, per cui mi sarebbe difficile fare di meglio. Tra l’altro, devo ammettere che di questo PigeonHole non avevo mai nemmeno sentito parlare...
 Ah, premetto che B = bianco/bianchi e N = nero/neri. E quando dico ‘triangolo monocromatico’ intendo ‘triangolo con tutti i vertici dello stesso colore’, chiaramente.
 
 Si piastrelli il piano con esagoni regolari. Dati tre esagoni tutti con un lato in comune si ha, affinché il triangolo equilatero che ha per vertici i loro centri non sia monocromatico, che 2 centri hanno lo stesso colore e 1 ha colore diverso. Diciamo che ci sono 2 centri B e uno N. Detto e1 l’esagono con il centro N, e2, e3 gli altri esagoni, i 3 vertici che e1 ha in comune con e2 ed e3 sono, nell’ordine, NBN o BNB (se 2 consecutivi fossero dello stesso colore formerebbero un triangolo equilatero monocromatico col centro di e1 o di e2).
 - Se sono NBN, poiché non possono esserci in e1 vertici consec. N (altrimenti formano un triangolo equilatero col centro), si avranno 5 vertici consecutivi BNBNB; ma sarà quindi possibile disegnare un triangolo eq. che ha per vertici i p.ti B.
 - Se sono BNB, si consideri e2, che avrà un lato con estremi BN; il consecutivo del B sarà N, e, perché non formi un triangolo equil. monocromatico con il centro di e1, il suo opposto sarà B. e2 avrà perciò 5 vertici consecutivi NBNBN (il quinto non può essere B), e si formerà un triangolo equilatero monocromatico con i vertici N.
 
 Allora, funziona?

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

Nell\'attesa che qualcuno mi dica se la mia soluzione funge rilancio con la generalizzazione del problema:
 
 Problema: Dato un piano colorato di k colori:
 a) Dimostrare che esistono infiniti rettangoli monocromatici
 b) Dire quante rette bisogna prendere, al minimo, per dimostrare che ne esiste uno
 
 Del punto b) non conosco la soluzione.

phi · Messaggio da **phi** » 01 gen 1970, 01:33

La mia dimostrazione del primo punto (tra i due proposti da Boll) sarebbe questa:
 
 Si prendano k+1 rette parallele (r1, r2... rk+1). Intersecando ad esse una retta perpendicolare, tra i k+1 punti d’intersezione ve ne saranno almeno due dello stesso colore. Le (k+1)-uple ordinate possibili dei colori dei punti d’intersezione di una perpendicolare con le rette r1, r2, ... rk+1 sono in numero finito (sono le disposizioni con rip. di k elementi a k+1 a k+1), e quindi, necessariamente, date tutte le possibili rette perpendicolari (che sono infinite), ve ne saranno due (diciamo a e b) che generano la stessa sequenza di colori. Le intersezioni di a con due delle rette di partenza e le intersezioni di b con quelle rette hanno tutte lo stesso colore, e quindi si forma un rettangolo monocromatico. Ma notiamo che le perpendicolari che generano una stessa sequenza di colori sono infinite (se fossero finite le rette che generano ciascuna sequenza avremmo in totale un numero finito di perpendicolari, il che è impossibile) e quindi si formano infiniti rettangoli monocromatici.
 
 Per quanto riguarda il secondo punto, credo che la soluzione dipenda da cosa s’intende. Per dimostrare che c’è un rettangolo monocromatico bastano k + 3 rette, se, una volta che si è dimostrato che una retta con certe caratteristiche esiste, è lecito sceglierla rispetto a tutte le altre. (Cioè: prendi k+1 rette parallele, dimostri che esistono due rette perpendicolari ad esse che hanno la stessa sequenza di colori nei punti d’intersezione, le prendi e toh, è fatta).
 Altrimenti di certo ce ne vogliono di più, di rette. Se non puoi sceglierle in nessun modo ma solo dire se sono parallele o perpendicolari, avrei calcolato (e non c’è da fidarsi) che ci vogliono addirittura [k^2(k+1)]/2 + k + 2 rette per essere assolutamente certi di beccare un rettangolo monocromatico.
 Oppure, se fosse lecito scegliere le perpendicolari in base al colore della loro intersezione con r1, credo che ci vorrebbero [k(k+1)]/2 + k + 2 rette.
 Comunque intendiamoci, potrei aver sbagliato tutto. Qualcuno mi dica che cosa ne pensa...
 
 EDIT: errore di battitura (volevo scrivere 2, non 1...!) <IMG SRC="images/forum/icons/icon_confused.gif"> [ Questo Messaggio è stato Modificato da: phi il 29-10-2004 17:39 ]

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

@phi: La dimostrazione del punto a è uguale alla mia, non so se è giusta, se qualcuno di più esperto di me prima o poi si interessera a questo post sia io che te avremo le nostre risposte. Per il punto b si intende che non c\'è possibilità di scelta, bisogna dire quante rette bisogna prendere per essere assolutamente certi che esista un rettangolo monocromatico. Il problema è che non so come calcolare in quanti modi si possono disporre k oggetti in k+1 buchi senza che ce ne siano mai in nessun punto due che hanno un gruppo KK uguale nella stessa posizione, la risposta del quesito è questo conteggio +1 (spiegato da bestia, spero tu abbia capito). [ Questo Messaggio è stato Modificato da: Boll il 29-10-2004 14:18 ]

phi · Messaggio da **phi** » 01 gen 1970, 01:33

E\' esattamente il calcolo che ho cercato di fare io, e che mi risulterebbe [(k^2)*(k+1)]/2+k+2 (prima avevo semplicemente sbagliato a ricopiare il risultato... Il mio ragionamento sarebbe questo. Prendi le k + 1 rette, e ok. Poi, ci dovrebbero essere massimo k(k+1)/2 rette per ogni colore che non abbiano quello stesso colore ripetuto nelle stesse posizioni. (Prendi il colore cn ripetuto due volte; hai k+1 possibilità di metterlo una volta, te ne rimangono k dove metterlo la seconda volta; diviso due altrimenti hai anche il contrario di ciascun risultato; nota che devi prendere il colore ripetuto solo 2 volte e non di più, altrimenti è più \"facile\" trovarselo nella stessa posizione). Ci sono k colori, quindi k^2(k+1)/2. Aggiungi 1. Aggiungi k + 1. Quello è il risultato. Che ne dici, ti sembra che fili? A me è venuta una folgorazione stamattina durante una soporifera ora di storia... per cui non garantisco che sia giusto! <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 P.S. Secondo me è la parola \"dimostrare\" nell\'enunciato che potrebbe dar luogo a qualche equivoco...