Punti del piano

[axpgn]

Disponiamo $n$ punti sul piano e colleghiamo ognuno di essi al più vicino con un segmento.
Assumiamo che le distanze siano tutte differenti cosicché non ci siano dubbi su quale sia il punto più vicino a ciascuno di essi.

Dimostrare che la figura risultante non contiene poligoni chiusi né segmenti che si intersechino.



Cordialmente, Alex

[jas1231]

Traccia

"axpgn":Disponiamo $ n $ punti sul piano e colleghiamo ognuno di essi al più vicino con un segmento.
Assumiamo che le distanze siano tutte differenti cosicché non ci siano dubbi su quale sia il punto più vicino a ciascuno di essi.

Dimostrare che la figura risultante non contiene poligoni chiusi né segmenti che si intersechino.

Svolgimento

Chiamo "percorso" la spezzata composta da un numero qualsiasi di segmenti che congiungono un punto al più vicino.

Lemma 1
Immagino, quando costruisco un segmento, di associare ad esso un disco con centro sul punto di partenza e raggio pari alla distanza di quest'ultimo dal punto di arrivo, allora affermo che nessuno degli $ n $ punti sul piano è contenuto in questo disco, perché se così non fosse il segmento costruito non sarebbe quello di minima lunghezza possibile.

Lemma 2
Affermo che partendo da un punto e procedendo a costruire un percorso si disegneranno segmenti sempre più brevi.
Dimostrazione per assurdo:
suppongo che il segmento che parte dal k_esimo punto (in ordine di costruzione dei segmenti) ed arriva al k+1_esimo (che chiameremo k-esimo segmento) sia più lungo del k-1_esimo allora il k-1_esimo punto appartiene al k_esimo disco (perché la sua distanza dal k_esimo punto è minore del raggio del disco) il che è assurdo per il lemma 1.



Punto 1

Tesi: la figura risultante non contiene poligoni chiusi.

Dimostrazione

Affermare che la figura non contiene poligoni chiusi corrisponde ad affermare che la figura non contiene percorsi che tornano su sé stessi.

Allora poniamo arbitrariamente che il primo punto del percorso sia il punto dal quale parte il segmento più lungo, poniamo che l'ultimo punto sia il primo punto tale che il suo successivo apparteneva già al percorso e chiamiamo k_esimo punto il punto in cui il percorso torna su sé stesso (cioè il successivo all'ultimo punto).

Per il Lemma 2 possiamo affermare che il segmento che parte dall'ultimo punto (ultimo segmento) è minore del segmento che parte dal k_esimo punto (k_esimo segmento), ma allora la distanza dell'ultimo punto dal k_esimo è minore del raggio del k_esimo disco e quindi l'ultimo punto appartiene al k_esimo disco, il che è assurdo per il Lemma 1.



Conclusione punto 1

Abbiamo dimostrato che nessun percorso può tornare su sé stesso, quindi la figura non può contenere poligoni chiusi.

Punto 2

Tesi: la figura risultante non contiene segmenti che si intersechino.

Dimostrazione

Supponiamo di avere 4 punti distinti $ A,B,C,D $, sul piano, per cui il segmento di minima distanza uscente da $A$ colpisce $B$ (segmento $AB$) e quello di minima distanza da $C$ colpisce $D$ (segmento $CD$).
Supponiamo inoltre che $ bar(AB) Costruiamo la circonferenza di raggio $ bar(CD $ centrata in $D$ (che chiameremo circonferenza rossa) e la retta passante per $AB$ (che chiameremo retta blu).
Siccome $E$ poggia sul segmento $CD$ esso è interno alla circonferenza rossa e, siccome $E$ appartiene alla retta blu, possiamo affermare che la retta blu interseca la circonferenza rossa in 2 punti che chiameremo $ G $ ed $ F $ .



Allora per il Lemma 1 abbiamo che $A,B$ sono esterni alla circonferenza rossa e siccome $E$ è interno ad $AB$ e $E$ è interno alla circonferenza rossa possiamo affermare che $GF$ è interno ad $AB$, quindi
$ bar(AB)>bar(GF $ ciò implica che $ bar(GB) $5/6pi>hat(GDC)>pi$ e quindi è ottuso.

Ma se $ hat(GDC) $ è ottuso allora anche $hat(ADB)$ lo è, ma siccome l'angolo maggiore si oppone al lato maggiore abbiamo che $ bar(AD)
Conclusione punto 2

Abbiamo dimostrato che due segmenti di minima distanza tra punti del piano non possono mai intersecarsi, quindi la figura non contiene segmenti che si intersecano.

[axpgn]

Alcune considerazioni ...

"jas123":

Lemma 1
Immagino, quando costruisco un segmento, di associare ad esso un disco con centro sul punto di partenza e raggio pari alla distanza di quest'ultimo dal punto di arrivo, allora affermo che nessuno degli $ n $ punti sul piano è contenuto in questo disco, perché se così non fosse il segmento costruito non sarebbe quello di minima lunghezza possibile.

Beh, non proprio, almeno il punto di arrivo fa parte del disco e non è la stessa cosa ovvero un punto può appartenere teoricamente a due dischi perché può essere il centro di un disco e sul bordo di un altro.

"jas123":
Lemma 2
Affermo che partendo da un punto e procedendo a costruire un percorso si disegneranno segmenti sempre più brevi.
Dimostrazione per assurdo:
suppongo che il segmento che parte dal k_esimo punto (in ordine di costruzione dei segmenti) ed arriva al k+1_esimo (che chiameremo k-esimo segmento) sia più lungo del k-1_esimo allora il k-1_esimo punto appartiene al k_esimo disco (perché la sua distanza dal k_esimo punto è minore del raggio del disco) il che è assurdo per il lemma 1.

Questo lemma è falso perché, a parte il concetto di "spezzata ordinata" che, a mio parere, non è esplicitato chiaramente (dai per scontato che si possa costruire una spezzata "dal più piccolo al più grande" ma sarebbe da dimostrare), a priori il $k+1$-esimo punto potrebbe sicuramente essere quello più lontano da tutti gli altri ed essere collegato al $k$-esimo (o ultimo punto della tua spezzata).

Quello che voglio dire è che un punto può essere collegato oltre che al suo più vicino anche ad un altro punto perché è il più vicino dell'altro.

Ne consegue che la dimostrazione che fai è inficiata da quanto detto (anche la seconda se pur parzialmente).

Cordialmente, Alex

[jas1231]

Sul lemma 1 hai assolutamente ragione, ho dimenticato di aggiungere "tranne punto di partenza e di arrivo", una piccola svista.
Per il lemma 2 forse sono stato frettoloso nello scrivere l'enunciato, ma penso si possa salvare:
per esempio potrei dire:
Costruisco un percorso partendo da un punto e fermandomi quando non è più possibile costruire un nuovo segmento che parte da un punto lungo il percorso (qui il "che parte" significa che il segmento che si costruisce deve essere quello di minima distanza da quello di partenza), allora ho costruito segmenti sempre più piccoli.

Cambiando, però, l'enunciato andrebbe fatta qualche giustificazione in più per la dimostrazione del punto 1 (ma mi sembra fattibile).

Farò le opportune correzioni...

[axpgn]

@jas123

Riguardo al lemma 2 così com'è non credo si possa aggiustare più di tanto; al di là del fatto che non è chiaro (nel senso che non definisci esattamente come costruirlo questo percorso) nel momento in cui dici "mi fermo perché non posso più andare avanti", di fatto stai assumendo come ipotesi che non esistono percorsi chiusi ma questa è la tesi da dimostrare.
Per esempio, prendi i punti (sulla retta reale) $0, 5, 9, 12, 14, 15, 100$; ora il "tuo" percorso sarebbe quello a decrescere da $0$ a $15$ e lì finisce ma purtroppo, anche se tu non lo vuoi e lo escludi a priori, il segmento da $15$ a $100$ c'è, eccome ed è pienamente compatibile con le "regole del gioco"

Cordialmente, Alex

[jas1231]

@Alex

Sisi infatti hai ragione, con il solo lemma 2 non si può fare molto, il "mi fermo" è per prendere un tipo particolare di percorso, ma non sto dicendo che tutti i percorsi siano così. La mia idea era quella di introdurre un terzo lemma che dice che un percorso qualsiasi è sempre unione di due percorsi descritti nel lemma 2 che si uniscono in un punto, ad esempio nel caso che hai portato tu sarebbe così:




dove sia il percorso blu che quello rosso, presi singolarmente, sono compatibili con il lemma 2.

[axpgn]

Dunque ... la prima versione del Lemma 2 cioè questa

"jas123":
Lemma 2
Affermo che partendo da un punto e procedendo a costruire un percorso si disegneranno segmenti sempre più brevi.

è falsa e l'abbiamo dimostrato, però almeno è chiara (e quindi è relativamente facile dimostrarne la veridicità o falsità)
La seconda versione cioè questa

"jas123":
per esempio potrei dire:
Costruisco un percorso partendo da un punto e fermandomi quando non è più possibile costruire un nuovo segmento che parte da un punto lungo il percorso ...

invece chiara non lo è per niente: che vuol dire "partendo da un punto (quale? generico? specifico?) e fermandomi quando non è più possibile costruire un nuovo segmento (cosa significa costruire "un nuovo segmento"? abbiamo visto che può essercene uno sia più corto che più lungo quindi quando?)" ?

Io lascerei perdere i lemmi e cercherei una soluzione più diretta, riorganizzando le idee sulle quali stavi lavorando ...

Cordialmente, Ale

[jas1231]

Se hai voglia di dargli un'occhiata dimmi se questa volta ti convince:

Traccia

"axpgn":Disponiamo $ n $ punti sul piano e colleghiamo ognuno di essi al più vicino con un segmento.
Assumiamo che le distanze siano tutte differenti cosicché non ci siano dubbi su quale sia il punto più vicino a ciascuno di essi.

Dimostrare che la figura risultante non contiene poligoni chiusi né segmenti che si intersechino.

Svolgimento
Iniziamo distinguendo 2 tipi differenti di segmento associato ad un punto $ P $:
Dato un punto $ P $ sul piano chiamiamo segmento del tipo $ a $ (che è unico) il segmento che congiunge $ P $ al punto generico $ Q $ ad esso il più vicino possibile.
Tutti i segmenti che hanno $P $ come estremo e non sono del tipo $ a $ sono chiamati segmenti del tipo $ b $. (nota se un segmento $PQ$ è di tipo $ b$ associato a $P$, allora sarà di tipo $a$ associato a $Q$)
Chiamo "percorso" la spezzata composta da un numero qualsiasi di segmenti che congiungono un punto al più vicino.

Lemma 1
Immagino, quando costruisco un segmento, di associare ad esso un disco con centro sul punto di partenza e raggio pari alla distanza di quest'ultimo dal punto di arrivo, allora affermo che nessuno degli $ n $ punti sul piano, tranne i due estremi del segmento, è contenuto in questo disco, perché se così non fosse il segmento costruito non sarebbe quello di minima lunghezza possibile.

Lemma 2
Affermo che, partendo da un punto e costruendo il segmento di tipo $ a $ associato ad esso, poi quello associato al punto di arrivo del primo segmento e così via, si disegneranno segmenti sempre più brevi. (Il percorso così generato verrà chiamato percorso di tipo $a$)
Dimostrazione per assurdo:
suppongo che il segmento che parte dal k_esimo punto (in ordine di costruzione dei segmenti) ed arriva al k+1_esimo (che chiameremo k-esimo segmento) sia più lungo del k-1_esimo segmento, allora il k-1_esimo punto appartiene al k_esimo disco (perché la sua distanza dal k_esimo punto è minore del raggio del disco) il che è assurdo per il lemma 1.




Lemma 2 esteso
Affermo che, partendo da un punto e costruendo un segmento di tipo $ b $ associato ad esso, poi quello associato al punto di arrivo del primo segmento e così via, si disegneranno segmenti sempre più lunghi.
(il percorso così generato verrà chiamato percorso di tipo $b$)
Dimostrazione per assurdo:
suppongo che il segmento che parte dal k_esimo punto (in ordine di costruzione dei segmenti) ed arriva al k-1_esimo (che chiameremo k-esimo segmento) sia più lungo del k+1_esimo segmento (che parte dal k+1_esimo punto ed arriva al k_esimo segmento), allora il k+1_esimo punto appartiene al k_esimo disco (perché la sua distanza dal k_esimo punto è minore del raggio del disco) il che è assurdo per il lemma 1.





Nota: un percorso di tipo $a$ è anche un percorso di tipo $b$, dipende soltanto dal verso di percorrenza.
Lemma 3
Affermo che dopo un segmento del tipo $ b$ associato ad un punto $ k_1$, con estremi $ k_1, k_2$ non ci potrà mai essere un segmento del tipo $ a$ associato al punto $ k_2$ diverso dal segmento $k_1k_2$.
Dimostrazione:
Se esistesse un segmento di tipo $a$ associato a $k_2$ diverso da $k_1k_2$ questo vorrebbe dire che ci sono due segmenti del tipo $a$ associati a $k_2$ il che è assurdo per definizione di segmento di tipo $a$ associato a $P$.
Corollario Lemma 3
Tutti i percorsi che non sono del tipo $a $ o del tipo $b $ (che chiameremo percorsi compositi) sono composti da due sotto-percorsi consecutivi uno del tipo $a $ e uno del tipo $b $ (dove questi sotto-percorsi sono i più grandi possibili).
Punto 1

Tesi: la figura risultante non contiene poligoni chiusi.

Dimostrazione

Affermare che la figura non contiene poligoni chiusi corrisponde ad affermare che la figura non contiene percorsi che tornano su sé stessi. (poniamo arbitrariamente che il percorso torni su sé stesso nel punto iniziale, altrimenti, se non fosse così, esisterebbe un sotto-percorso che torna su sé stesso nel punto iniziale e noi sceglieremmo quello)

Divido la dimostrazione in 3 casi:
- Se il percorso è di tipo $a$ allora il segmento del tipo $a$ associato al punto iniziale è maggiore di tutti gli altri segmenti, e quindi il segmento del tipo $a$ associato all’ultimo punto è minore di quello associato al primo punto e quindi l’ultimo punto appartiene al disco associato al primo punto. Assurdo.





- Se il percorso è del tipo $b$ il ragionamento è analogo al caso precedente
- Se il percorso è composito allora il percorso $b$, che compone il percorso composito, è contemporaneamente preceduto e succeduto dal percorso $a$, associato al percorso composito, ma ciò contravviene al lemma 3 perché vuol dire che c’è un punto a cui sono associati 2 segmenti del tipo $a$





Conclusione punto 1

Abbiamo dimostrato che nessun percorso può tornare su sé stesso, quindi la figura non può contenere poligoni chiusi.

Punto 2

Tesi: la figura risultante non contiene segmenti che si intersechino.

Dimostrazione

Supponiamo di avere 4 punti distinti $ A, B, C, D $, sul piano, per cui il segmento di minima distanza uscente da $A$ colpisce $B$ (segmento $AB$) e quello di minima distanza da $C$ colpisce $D$ (segmento $CD$).
Supponiamo inoltre che $ bar (AB) Costruiamo la circonferenza di raggio $ bar (CD $ centrata in $D$ (che chiameremo circonferenza rossa) e la retta passante per $AB$ (che chiameremo retta blu).
Siccome $E$ poggia sul segmento $CD$ esso è interno alla circonferenza rossa e, siccome $E$ appartiene alla retta blu, possiamo affermare che la retta blu interseca la circonferenza rossa in 2 punti che chiameremo $ G $ ed $ F $.






Allora per il Lemma 1 abbiamo che $A, B$ sono esterni alla circonferenza rossa e siccome $E$ è interno ad $AB$ e $E$ è interno alla circonferenza rossa possiamo affermare che $GF$ è interno ad $AB$, quindi
$ bar(AB)>bar(GF $ ciò implica che $ bar(GB) $5/6pi>hat(GDC)>pi$ e quindi è ottuso.

Ma se $ hat(GDC) $ è ottuso allora anche $hat(ADB)$ lo è, ma siccome l'angolo maggiore si oppone al lato maggiore abbiamo che $ bar(AD)
Conclusione punto 2

Abbiamo dimostrato che due segmenti di minima distanza tra punti del piano non possono mai intersecarsi, quindi la figura non contiene segmenti che si intersecano.

[axpgn]

Sinceramente la trovo eccessiva e ridondante, e diventa difficile poi (almeno per me) capire se effettivamente hai dimostrato qualcosa oppure no ...
I lemmi li trovo sostanzialmente inutili (è proprio necessario affermare che non esistono punti più vicini ad un punto di quello ad esso più vicino? o che in una spezzata possono esserci percorsi "crescenti" e percorsi "decrescenti?); a mio parere l'unica cosa veramente importante è dimostrare che non esistono due percorsi "decrescenti" dallo stesso punto però nel lemma 3 sembra che affermi il contrario (questo è ciò che ho capito).

Ecco la mia soluzione ...

Supponiamo esista un poligono $ABC...MNA$ e supponiamo che sia $NA Ciò implica che $AB Assurdo.
E lo stesso ragionamento vale se si suppone $NA>AB$

Supponiamo che esistano due segmenti $AB$ e $CD$ intersecantisi in $E$.
Supponiamo inoltre che $A$ e $B$ siano connessi perché $B$ è il punto più vicino ad $A$ e che $C$ e $D$ siano connessi perché $D$ è il punto più vicino a $C$.
Quindi $AB
[[size=85]Dimostrazione:
Nel triangolo $AED$ abbiamo $AE+ED>AD$ e nel triangolo $BEC$ abbiamo $BE+EC>BC$
Sommiamo membro a membro e otteniamo $AE+ED+BE+EC>AD+BC$ ma dato che $AE+BE=AB$ e $DE+CE=CD$ abbiamo $AB+CD>AD+BC$[/size]]

Cordialmente, Alex