Tracciaaxpgn ha scritto: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.
SvolgimentoIniziamo 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 1Immagino, 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 2Affermo 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 estesoAffermo 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 3Affermo 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 3Tutti 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 1Tesi: la figura risultante non contiene poligoni chiusi.
DimostrazioneAffermare 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 1Abbiamo dimostrato che nessun percorso può tornare su sé stesso, quindi la figura non può contenere poligoni chiusi.
Punto 2Tesi: la figura risultante non contiene segmenti che si intersechino.
DimostrazioneSupponiamo 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)<bar (CD) $ e che i segmenti $ AB $ e $ CD $ si intersechino nel punto $ E $.
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)<bar(CD $ e quindi l'angolo $0<hat(GCF)< pi/3 $ e quindi
$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)<bar(AB $, il che è assurdo.
Conclusione punto 2Abbiamo dimostrato che due segmenti di minima distanza tra punti del piano non possono mai intersecarsi, quindi la figura non contiene segmenti che si intersecano.