Cerchi e punti colorati

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Cerchi e punti colorati

Messaggio da Lasker »

Premetto che non ne conosco la dimostrazione, anche se dovrebbe essere un vecchio TST del Kazakistan, quindi sperabilmente essa esiste (la fonte da cui l'ho preso non cita con precisione il testo originale, quindi non posso garantirlo al 100%, e sinceramente spulciando fra quei problemi non l'ho trovato).

Ci sono $m$ punti rossi $r_1,r_2,...,r_m$ ed $n$ punti blu $b_1,b_2,...,b_n$ (ovviamente con $m,n\in\mathbb{N}$) disposti su un piano di riferimento cartesiano in modo che la distanza fra ogni coppia di punti di colore diverso $(r_i, b_j)$ sia strettamente minore di $1$. Dimostrare che esiste un cerchio di diametro $\sqrt{2}$ che copre tutti i punti rossi oppure tutti i punti blu.

Lo propongo principalmente perché il testo mi ha incuriosito, nonostante io non sopporti la combinatoria :mrgreen:
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Cerchi e punti colorati

Messaggio da Triarii »

Procediamo per induzione.
Il passo base è 1 punto blu, per il quale la tesi è banalmente vera.
Il passo induttivo lo dividiamo in 2 case: se aggiungo un punto blu o se aggiungo un punto rosso (ovviamente li aggiungo rispettando la regola che la distanza fra ogni coppia di punti di diverso colore è strettamente minore di $1$.
Come ipotesi induttiva, esiste un cerchio di diametro $\sqrt 2$ che contiene wlog tutti i punti blu.
Caso 1) Aggiungo un punto rosso (sempre in modo lecito).
La tesi continua ovviamente ad essere vera perchè continua ad esistere la circonferenze che contiene tutti i punti blu.
Caso 2) Aggiungo un punto blu.
Consideriamo la coppia di punti blu $A,B$ con distanza massima ( ne prendo una a caso se ci sono più coppie con distanza massima).
Sia $t$ questa distanza. Se $t<\sqrt 2$ esiste una circonferenze di diametro $d= \sqrt 2$ che contiene tutti i punti blu (questo grazie al fatto che già esisteva una circonferenza che conteneva tutti i blu eccetto quello aggiunto).
Se $t\ge \sqrt 2$, allora non esiste più una circonferenza chje contiene tutti i punti blu.
Affinchè l'aggiunta del nuovo punto blu sia lecita, i punti rossi devono giacere nell'intersezione dei due cerchi di raggio unitario e centri $A, B$. (e già qui si nota che t<2, altrimenti non c'è l'intersezione dove possano stare i punti rossi, ma questo fatto non è davvero rilevante ai fini del problema). Si noti che la distanza massima $r$ fra 2 punti dell'intersezione nel caso di $t>\sqrt 2$ è proprio quella fra i 2 punti di intersezione. Questa distanza inoltre diminuisce all'aumentare di $t$ (basta vedere che la funzione che lega le 2 grandezze in questione è decrescente). Stesso discorso lo si può fare per l'area dell'intersezione, ma qui credo che sia ridondate. Quindi $r$ assume valore massimo per $t=\sqrt\Rightarrow r=\sqrt 2$ (è il caso in cui si AB è una diagonale del quadrato mentre $r$ è l'altra diagonale). Pertanto visto che la distanza massima è minore di $qrt 2$, l'intersezione è sempre ricopribile da un cerchio con tale diametro, e quindi tutti i punti rossi, che sono contenuti in questa intersezione, sono contenuti da tale cerchio, che è la tesi.
Edit: c'era un errore nella parte $t\le \sqrt 2$ che spero di aggiustare domani (l'idea è sempre quella comunque)
"We' Inge!"
LTE4LYF
Rispondi