grigliata mista

[sprmnt21]

Ogni punto di una griglia di un piano cartesiano e' colorato con uno di tre colori e per ogni colore c'e almeno un punto colorato con quello. Mostra che puoi sempre trovare un triangolo rettangolo in cui ogni coppia di vertici non e' monocromatica.

[jordan]

Ogni punto di una griglia di un piano cartesiano e' colorato con uno di tre colori e per ogni colore c'e almeno un punto colorato con quello. Mostra che puoi sempre trovare un triangolo rettangolo in cui ogni coppia di vertici non e' monocromatica.

Chiamiamo wlog $ A,B,C $ i tre colori del piano; esiste per ipotesi una riga $ r $ colorata con almeno $ 2 $ colori, wlog $ A \text{ e } B $ (altrimenti il piano sarebbe monocromatico): se $ r $ ha esattamente $ 2 $ colori allora abbiamo la tesi (in quanto un altro punto di colore C esiste per ipotesi), altrimenti $ r $ conterrà i $ 3 $ colori $ A,B,C $ in $ 3 $ punti distinti, rispettivamente $ x,y,z $; supponendo per assurdo che la tesi non sia verificata, allora concludiamo facilmente che la retta $ r_x $ perpendicolare a $ r $ e passante per $ x $ sarà tutta colorata di $ A $, e analogamente per $ r_y $ e $ r_z $; in particolare se $ p \in r $ allora ogni punto di $ r_p $ perpendicolare a $ r $ e passante per $ p $ è colorato dello stesso colore di $ p $. Ciò significa che se fissiamo un sistema di riferimento cartesiano allora possiamo assumere che esiste una funzione $ t:\mathbb{Z}^2 \to \{A,B,C\} $ tale che $ t(x,y)=t(0,y) $ per ogni $ (x,y) \in \mathbb{Z}^2 $ (è in pratica una funzione che definisce una colorazione a striscie del piano). Consideriamo una coppia $ (h,k) \in Z^2 $ tale che:
i)$ h<0<k $
ii)$ t(0,0),t(0,h),t(0,k) $ sia una permutazione di $ \{A,B,C\} $ (esistono per costruzione, per quanto detto prima).
Allora i punti $ (0,0),(h,-h), (k,k) $ formano un triangolo rettangolo con i colori dei tre vertici distinti.

[sprmnt21]

Chiamiamo wlog $ A,B,C $ i tre colori del piano; esiste per ipotesi una riga $ r $ colorata con almeno $ 2 $ colori

Non ho letto il seguito, ma forse e' meglio chiarire prelimirmante questo punto.

Perche' non possono esistere righe solo monocromatiche?

[julio14]

c'è scritto appena dopo... altrimenti il piano sarebbe monocromatico.

[Haile]

Chiamiamo wlog $ A,B,C $ i tre colori del piano; esiste per ipotesi una riga $ r $ colorata con almeno $ 2 $ colori

Non ho letto il seguito, ma forse e' meglio chiarire prelimirmante questo punto.

Perche' non possono esistere righe solo monocromatiche?

Se tutte le righe sono monocromatiche, basta prendere una colonna (che alla fine è sempre una riga... verticale)

[sprmnt21]

c'è scritto appena dopo... altrimenti il piano sarebbe monocromatico.

e' quello ceh non ho capito. Perche' se le righe sono monocromatiche, tutto il piano e' monocromatico?

[sprmnt21]

Chiamiamo wlog $ A,B,C $ i tre colori del piano; esiste per ipotesi una riga $ r $ colorata con almeno $ 2 $ colori

Non ho letto il seguito, ma forse e' meglio chiarire prelimirmante questo punto.

Perche' non possono esistere righe solo monocromatiche?

Se tutte le righe sono monocromatiche, basta prendere una colonna (che alla fine è sempre una riga... verticale)

e quindi ...? esponi il ragionamento per esteso, per favore.

[Haile]

Non ho letto il seguito, ma forse e' meglio chiarire prelimirmante questo punto.

Perche' non possono esistere righe solo monocromatiche?

Se tutte le righe sono monocromatiche, basta prendere una colonna (che alla fine è sempre una riga... verticale)

e quindi ...? esponi il ragionamento per esteso, per favore.

Supponi che tutte le righe del piano siano monocromatiche.

Considera il punto P(a,b), di un certo colore C. Se tutte le righe sono monocromatiche, anche la retta di equazione x = a è monocromatica ed è di colore C.

Poichè tutti i punti di x = a sono di colore C, anche tutte le rette perpendicolari a x = a (che sono righe) devono essere completamente di colore C, altrimenti non sarebbero monocromatiche.

Quindi tutte le rette di equazione $ y = r, ~ \forall r \in \mathbb{R} $ sono di colore C (perchè intersecano tutte una riga con colore C), il che equivale a dire che il piano è di colore C.

[sprmnt21]

Se tutte le righe sono monocromatiche, basta prendere una colonna (che alla fine è sempre una riga... verticale)

e quindi ...? esponi il ragionamento per esteso, per favore.

Supponi che tutte le righe del piano siano monocromatiche.

Considera il punto P(a,b), di un certo colore C. Se tutte le righe sono monocromatiche, anche la retta di equazione x = a è monocromatica ed è di colore C.

Poichè tutti i punti di x = a sono di colore C, anche tutte le rette perpendicolari a x = a (che sono righe) devono essere completamente di colore C, altrimenti non sarebbero monocromatiche.

Quindi tutte le rette di equazione $ y = r, ~ \forall r \in \mathbb{R} $ sono di colore C (perchè intersecano tutte una riga con colore C), il che equivale a dire che il piano è di colore C.

Non sono sicuro di aver capito bene l'inghippo. Ma forse e' bene esplicitare la seguente osservazione: righe (o colonne monocromatiche) vuol dire che ogni riga ha tutti i punti di un solo colore, ma righe monocromatiche (o colonne) diverse non sono necessariamente dello stesso colore.

[Haile]

Ma forse e' bene esplicitare la seguente osservazione: righe (o colonne monocromatiche) vuol dire che ogni riga ha tutti i punti di un solo colore, ma righe monocromatiche (o colonne) diverse non sono necessariamente dello stesso colore.

Ma questo è ovvio... se righe monocromatiche diverse fossero necessariamente dello stesso colore non ci sarebbe niente da dimostrare... è come dire che esiste un solo colore.

Sinceramente più chiaro di come l'ho scritto non saprei dirlo...

(definendo riga una retta di equazione x=a oppure y=b, con a,b reali)



1) Tutte le righe sono monocromatiche (tutti i punti di una data riga sono dello stesso colore)

2) Considero il Punto P di coordinate (a,b) e di un colore qualunque C

3) Per la (1), la riga x=a è di colore C

4a) Considero le righe di forma y=r, con r reale

4b) Esse intersecano tutte la retta x=a

5) Tutte le rette del punto (4a) sono monocromatiche per la (1) e hanno un punto di colore C per la (3) e la (4b)

6) Tutte le rette del punto (4a) sono di colore C

7) Le rette del punto (4a) coprono tutto il piano

8 ) Per la (6) e la (7) il piano è di colore C

[sprmnt21]

Ma forse e' bene esplicitare la seguente osservazione: righe (o colonne monocromatiche) vuol dire che ogni riga ha tutti i punti di un solo colore, ma righe monocromatiche (o colonne) diverse non sono necessariamente dello stesso colore.

Ma questo è ovvio... se righe monocromatiche diverse fossero necessariamente dello stesso colore non ci sarebbe niente da dimostrare... è come dire che esiste un solo colore.

Sinceramente più chiaro di come l'ho scritto non saprei dirlo...

(definendo riga una retta di equazione x=a oppure y=b, con a,b reali)



1) Tutte le righe sono monocromatiche (tutti i punti di una data riga sono dello stesso colore)

2) Considero il Punto P di coordinate (a,b) e di un colore qualunque C

3) Per la (1), la riga x=a è di colore C

4a) Considero le righe di forma y=r, con r reale

4b) Esse intersecano tutte la retta x=a

5) Tutte le rette del punto (4a) sono monocromatiche per la (1) e hanno un punto di colore C per la (3) e la (4b)

6) Tutte le rette del punto (4a) sono di colore C

7) Le rette del punto (4a) coprono tutto il piano

8 ) Per la (6) e la (7) il piano è di colore C

Continuo a pensare che ci sia qualche fraintendimento, ma non riesco amettere bene a fuoco dove.

Provo ad esplicitare alcune osservaziopni sperando di fare luce, magari per caso, su qualche punto oscuro .

Il senso del problema per come l'ho inteso io (l'ho trovato inversione inglese, quindi ...) tratta di una griglia discreta (quindi ci si puo' "limitare" sostanzialmente agli interi).

Quando parlo di riga intendo una linea retta "orizzontale", parallela all'asse x del piano cartesiano (O, x, y), con equazione (se vuoi, am secondo me non serve far riferimento ad equazioni) y = n intero; quando aprlo di colonna intendo una linea retta "verticale" con equazione x = m intero.


Io ho obiettato all'impostazione di Jordan, che non puo' (senza altro provare) escludere il caso di righe monocromatiche. Si possono benissimo avere righe tutte monocromatiche senza contraddizione alcuna con le ipotesi date.

[sprmnt21]

Ogni punto di una griglia di un piano cartesiano e' colorato con uno di tre colori e per ogni colore c'e almeno un punto colorato con quello. Mostra che puoi sempre trovare un triangolo rettangolo in cui ogni coppia di vertici non e' monocromatica.

Chiamiamo wlog $ A,B,C $ i tre colori del piano; esiste per ipotesi una riga $ r $ colorata con almeno $ 2 $ colori, wlog $ A \text{ e } B $ (altrimenti il piano sarebbe monocromatico): se $ r $ ha esattamente $ 2 $ colori allora abbiamo la tesi (in quanto un altro punto di colore C esiste per ipotesi), altrimenti $ r $ conterrà i $ 3 $ colori $ A,B,C $ in $ 3 $ punti distinti, rispettivamente $ x,y,z $; supponendo per assurdo che la tesi non sia verificata, allora concludiamo facilmente che la retta $ r_x $ perpendicolare a $ r $ e passante per $ x $ sarà tutta colorata di $ A $, e analogamente per $ r_y $ e $ r_z $; in particolare se $ p \in r $ allora ogni punto di $ r_p $ perpendicolare a $ r $ e passante per $ p $ è colorato dello stesso colore di $ p $. Ciò significa che se fissiamo un sistema di riferimento cartesiano allora possiamo assumere che esiste una funzione $ t:\mathbb{Z}^2 \to \{A,B,C\} $ tale che $ t(x,y)=t(0,y) $ per ogni $ (x,y) \in \mathbb{Z}^2 $ (è in pratica una funzione che definisce una colorazione a striscie del piano). Consideriamo una coppia $ (h,k) \in Z^2 $ tale che:
i)$ h<0<k $
ii)$ t(0,0),t(0,h),t(0,k) $ sia una permutazione di $ \{A,B,C\} $ (esistono per costruzione, per quanto detto prima).
Allora i punti $ (0,0),(h,-h), (k,k) $ formano un triangolo rettangolo con i colori dei tre vertici distinti.

Ho letto adesso tutta l'esposizione e, a parte l'affermazione iniziale sulle righe monocromatiche, mi pare ci siano tutti gli elementi della soluzione.


Riporto qua la mia:


Supponiamo che esistano almeno una colonna c e una riga r con almeno due punti colorati diversamente. Possiamo avere due casi: la coppia di colori diversi in r e c e’ la stessa; oppure abbiamo due coppie distinte.

Cominciamo a discutere il caso di due coppie diverse e, senza perdere di generalita’, supponiamo che A e B siano in r e A e C siano in c. Come si verifica facilmente, qualunque sia il colore del punto X intersezione di r e c, abbiamo un triangolo rettangolo tricolore (XAB; XAC; XBC).

c
|
|
r----X-----------A----------------------B------
|
|
C
|
|
|
|
A
|
| fig. 1

Discutiamo ora il caso in cui le due coppie su r e c siano uguali entrambe a, supponiamo, (A, B). Sia C un punto colorato con il rimanente colore (ne esiste almeno uno, per ipotesi) e sia P la proiezione di questo su c. Se P = A o P = B abbiamo il triangolo rettangolo tricolore con un cateto su c e l’altro su CP se, invece P = C, siamo ricondotti al caso precedente. In ogni caso, in definitiva abbiamo un triangolo rettangolo tricolore.

c
|
|
r----+-----------A-------------------B--
|
|
- - - P - - - - - - - - - - - - - C - - -
|
A
|
|
|
|
B
|
| fig. 2

Resta da discutere il caso complementare all’ipotesi di partenza, il caso cioe’ in cui tutte le righe o tutte le colonne siano monocromatiche.

Supponiamo siano le righe ad essere monocromatiche (nel caso delle colonne basta girare il tutto di 90°).
Siano r1, r2 e r3 tre righe di colore rispettivamente A, B e C (vedi fig. 3). Facciamo riferimento a una generica colonna c che intercetta i punti R1, R2 ed R3 sulle tre righe omonime. Prendiamo P su r3 tale che R3P = R3R2 e se Q e’ la proiezione di P su R2, prendiamo R su r2, dalla parte opposta ad R2 rispetto a Q, tale che QR = R1R3. Da semplici considerazioni geometriche si ha che R1PR e’ un triangolo rettangolo, tricolore per costruzione.



C
|
|
R1---------------------------------------------------- r1
|\
|#\
|##\
|###\
|####\
R2------\----Q------------R------------------------------ r2
|#####\##|####*
|######\#|###*
|#######\|##*
R3-----------P------------------------------------------- r3
|
|
…

fig. 3




PS

Con il font courier sul mio .doc, il disegno sembrava migliore, ma credo si capèiosca lo stesso.

[jordan]

Io ho obiettato all'impostazione di Jordan, che non puo' (senza altro provare) escludere il caso di righe monocromatiche. Si possono benissimo avere righe tutte monocromatiche senza contraddizione alcuna con le ipotesi date.

Ho letto adesso tutta l'esposizione e, a parte l'affermazione iniziale sulle righe monocromatiche, mi pare ci siano tutti gli elementi della soluzione.

Ma che è una presa in giro?
E comunque evita di quotare interi messaggi postati subito prima

[Tibor Gallai]

Porca miseria, jordan... Porta rispetto verso gli anziani, una volta nella tua vita.
Cioè, nemmeno dopo l'epic fail con Gobbino ti si placa la boria.

[EvaristeG]

Allora, calma e gesso.

Effettivamente, ad una lettura "accademica", la frase di apertura della soluzione di jordan non regge: "c'è una riga non monocromatica (altrimenti l'intero piano sarebbe monocromatico)" è un enunciato falso.
Visto che il problema non è di una difficoltà insormontabile (tra il resto, non capisco perché tu, jordan, ti ci sia fiondato sopra senza aspettare che lo provasse qualche imberbe forumista), sarebbe stata gradita una frase del tipo "esiste una riga o una colonna non monocromatica (altrimenti l'intero piano sarebbe monocromatico)" e magari una spiegazione più prolissa di quella tra parentesi.

D'altra parte, sprmnt21 avrebbe potuto proseguire la lettura oltre la riga incriminata e, magari prendendo per buono l'asserto, controllare il resto della soluzione e quindi la sua sostanza.

Insomma, ho capito che il caldo dà alla testa (anche se io sono in pantaloni lunghi e maglione, coi temporali che fa qui...), ma non sollevate polveroni per nulla, prego.