Punti

[gio73]

l'ho trovato su un sito americano e mi è piaciuto

A finite number of points are plotted so that the distances between any two are distinct. Each point joins the one closest to it. Find the maximum number of segments that can start from a single point.

Ho la mia idea che vorrei discutere con voi

[axpgn]

A occhio direi che a cinque segmenti ci si arriva sicuramente ma a sei mi pare di no ... questo perché le misure son tutte diverse quindi un esagono regolare non si può usare e d'altra parte se lo "stiri" un pochino, si allunga da da una parte e si accorcia dall'altra ...

Cordialmente, Alex

[Bokonon]

Ci ho pensato su 10 minuti e non riesco a confutarmi. Io dico al massimo n-1 segmenti.
Se è corretto allora spiego

[gio73]

@bokonon

e n quanto è?

io avrei fatto un disegno, allego?

[Bokonon]

@gio73

"gio73":e n quanto è?

È una domanda trabocchetto?
n è un numero di punti a piacere

[gio73]

@bokonon non è una domanda trabocchetto

"gio73":
A finite number of points are plotted so that the distances between any two are distinct. Each point joins the one closest to it. Find the maximum number of segments that can start from a single point.

Un numero finito di punti sono disposti (immaginiamo su un piano) in modo tale che la distanza tra una qualsiasi coppia sia diversa da qualsiasi altra. Ogni punto è collegato quello a lui più vicino: Trova il numero massimo di segmenti che può partire da un singolo punto.

Se il numero finito è 20 non credo che da un punto possano partire 19 segmenti perchè bisogna rispettare la condizione "ogni punto è collegato a quello a lui più vicino"

[Bokonon]

@gio73
Il disegno fa davvero schifo ma credo renda l'idea

[ghira1]

Nel disegno di Bokonon credo di vedere al massimo due segmenti da un punto.

[hydro1]

"gio73":l'ho trovato su un sito americano e mi è piaciuto

A finite number of points are plotted so that the distances between any two are distinct. Each point joins the one closest to it. Find the maximum number of segments that can start from a single point.

Ho la mia idea che vorrei discutere con voi

Scusatemi ho qualche problema di comprensione: come fa un punto ad avere più di un segmento che parte da lui? Dalla descrizione mi sembra che per ogni $P$ esiste un unico $Q$ a lui connesso: è quello a distanza minima. Cosa non sto capendo?

[axpgn]

Non è così.

Poniamo di avere tre punti $A$, $B$ e $C$.
Supponiamo che il punto più vicino ad $A$ sia $B$; avremo il segmento $AB$.
Non è detto che il punto più vicino a $B$ sia $A$, può benissimo essere $C$ quindi avremo il collegamento $BC$.
Ed ecco che da $B$ partono due segmenti non uno.

Cordialmente, Alex

P.S.: Appena posso posterò la mia (quasi) dimostrazione del perché al max i segmenti siano $5$ e non di più.

[ghira1]

"hydro":
Scusatemi ho qualche problema di comprensione: come fa un punto ad avere più di un segmento che parte da lui? Dalla descrizione mi sembra che per ogni $P$ esiste un unico $Q$ a lui connesso: è quello a distanza minima. Cosa non sto capendo?

Mettiamo 5 punti intorno ad un sesto punto centrale. Un pentagono quasi regolare. Tutti i punti esterni saranno connessi al punto centrale.

[hydro1]

"axpgn":Non è così.

Poniamo di avere tre punti $A$, $B$ e $C$.
Supponiamo che il punto più vicino ad $A$ sia $B$; avremo il segmento $AB$.
Non è detto che il punto più vicino a $B$ sia $A$, può benissimo essere $C$ quindi avremo il collegamento $BC$.
Ed ecco che da $B$ partono due segmenti non uno.

Cordialmente, Alex

P.S.: Appena posso posterò la mia (quasi) dimostrazione del perché al max i segmenti siano $5$ e non di più.

aaahh certo, hai ragione. Oggi sono rintronato.

[gabriella127]

"ghira":[quote="hydro"]
Scusatemi ho qualche problema di comprensione: come fa un punto ad avere più di un segmento che parte da lui? Dalla descrizione mi sembra che per ogni $P$ esiste un unico $Q$ a lui connesso: è quello a distanza minima. Cosa non sto capendo?

Mettiamo 5 punti intorno ad un sesto punto centrale. Un pentagono quasi regolare. Tutti i punti esterni saranno connessi al punto centrale.[/quote]

Mi sto facendo al stessa domanda di Hydro da stamattina. Infatti dal testo sembra che ogni punto deve essere conesso con un solo punto, quello più vicino. E quindi il punto al centro dell'esagono non può essere connesso a tutti gli altri.
Forse ho frainteso il testo, ma se anche hydro ha lo stesso dubbio ci deve essere qualche ambiguità.

[hydro1]

"gabriella127":[quote="ghira"][quote="hydro"]
Scusatemi ho qualche problema di comprensione: come fa un punto ad avere più di un segmento che parte da lui? Dalla descrizione mi sembra che per ogni $P$ esiste un unico $Q$ a lui connesso: è quello a distanza minima. Cosa non sto capendo?

Mettiamo 5 punti intorno ad un sesto punto centrale. Un pentagono quasi regolare. Tutti i punti esterni saranno connessi al punto centrale.[/quote]

Mi sto facendo al stessa domanda di Hydro da stamattina. Infatti dal testo sembra che ogni punto deve essere conesso con un solo punto, quello più vicino. E quindi il punto al centro dell'esagono non può essere connesso a tutti gli altri.
Forse ho frainteso il testo, ma se anche hydro ha lo stesso dubbio ci deve essere qualche ambiguità.[/quote]

No semplicemente il testo va interpretato così: "ho $P_1,\ldots,P_n$ nel piano e faccio le operazioni seguenti: prendo $P_1$ e lo collego all'unico punto a distanza minima, poi faccio lo stesso con $P_2$, eccetra fino a $P_n$".

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

La domanda può essere riformulata nel seguente modo.
Dato un grafo \( G=(V,E)\) con pesi, dove \( E \) è l'insieme di tutti i possibili archi che si possono creare con i vertici di \(V\), e dove i pesi sono tutti distinti. Qual'è il grado massimale del minimum spanning tree (MST), che è unico siccome i pesi sono tutti i distinti e \( G \) è connesso.

[axpgn]

Partiamo dal punto $A$.
Il punto più vicino ad esso è il punto $B$ e quindi li collego.
Pongo $d=AB$.
Ora, un terzo punto $C$ deve trovarsi ad una distanza $d_1=AC$ maggiore di $d$ dato che non è il più vicino ad $A$ ma minore della distanza $d_2=BC$ che lo separa da $B$ altrimenti non potrei avere il segmento $AC$.
Quindi deve trovarsi in una zona esterna ai cerchi centrati in $A$ e in $B$ con raggi, rispettivamente pari a $d$ e a $d_2$.
Ma non solo; al fine di trovarsi più vicino ad $A$ piuttosto che a $B$, deve trovarsi dalla parte di semipiano in cui si trova $A$, semipiano definito dall'asse di $AB$.
Ripetendo questa operazione per altre tre volte, giungo ad una situazione in cui tutta la superficie diventa "area proibita" per un nuovo punto.

Quindi, al max sono $5$ i segmenti che possono partire da un punto.

IMHO

Cordialmente, Alex

P.S.:

"3m0o":La domanda può essere riformulata nel seguente modo. ...

Ma che roba è?

[gio73]

A me viene diverso

6 segmenti

[Bokonon]

Ok. Io ho interpretato così il problema.
Ogni singolo punto ha una distanza diversa da tutti gli altri e si connette al punto che ha distanza minima da esso, ergo posso differenziare i segmenti per "verso".
L'idea dell'orribile immagine è che posso usare un pezzo di spirale come sostegno per collegare i punti con vettori. Posso anche decidere la progressione delle norme partendo da una norma pari 1 e progressivamente dimezzarla. Questo mi assicura ogni singolo punto avrà distanze diverse da tutti gli altri e si connetterà solo nel verso del punto più vicino.

Voi cosa avete capito?

[axpgn]

@gio73

Il punto $G$ è più vicino a $B$ che ad $A$ quindi il segmento $AG$ non esiste.

"Bokonon":Voi cosa avete capito?

Di cosa?
Della tua interpretazione o della tua soluzione? Entrambe



Cordialmente, Alex

[gio73]

@alex
Lo sarà sempre anche se assotiliamo a piacere le circonferenze concentriche?

mi do la risposta, sì
perchè se assotiliamo fino a quasi averle coincidenti arriviamo all'esagono regolare che avevi escluso all'inizio.

@bokonon la questione del verso del segmento l'ha tirata fuori anche mio figlio

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":

P.S.: [quote="3m0o"]La domanda può essere riformulata nel seguente modo. ...

Ma che roba è? [/quote]
Mi manca qualcosa per risolverlo in quel modo. Non ci riesco!

Comunque è semplicemente un grafo \(G\), con dei vertici (dei nodi, dei punti) li collegi in tutti i modi possibili (i collegamenti li chiami archi) e ad ogni arco gli associ un peso. Nel nostro caso i pesi sono le distanze. Ora un MST (minimal spanning tree) associato ad un grafo connesso \(G\) è un grafo \(T\) (un albero più precisamente) tale che gli archi di \(T\) sono un sottoinsieme degli archi di \(G\) e che connette tutti i vertici di \(G\) senza creare dei cicli in modo tale che la somma dei pesi degli archi di \(T\) sia minimale. Ora è un risultato noto (in teoria dei grafi) che se un grafo \(G\) è connesso con pesi tutti distinti esiste un unico \(MST\) di \(G\).
Il grado di un vertice di \(G\) è semplicemente il numero di archi che entra (o che parte) nel vertice.

Io volevo provare per induzione sul numero di vertici. Prendere una foglia del \(MST\) di \(G\), con \(n+1\) vertici, togliere la foglia (quindi un vertice finale e l' unico arco attaccato), dire che ottengo un \( MST\) di \(G'\), che è quello con \(n\) vertici. Ma non riesco a concludere.

Edit:
Ovvero quello che devo dimostrare è quanto segue
Dato \(G_n=(V_n,E_n)\) un grafo con \(n\) vertici collegati in tutti i modi possibili con pesi distinti. Sia \(T_n\) il MST di \(G_n \), e definiamo \( M_n := \max_{ v \in T_n } \operatorname{deg}(v) \)

Allora in \(T_n\) esisteranno due vertici \(v_1,v_2 \in V_n \) tale che \((v_1,v_2) \in E_n \) è un arco di \(T_n\) e \( \operatorname{deg}(v_1)=1 \) e \( \operatorname{deg}(v_2) \leq M_{n-1} \).

Se riesco a dimostrare quanto detto sopra. Risulta facile, infatti da \(T_n\) posso togliere \(v_1 \) e \( (v_1,v_2) \) e otteniamo \(T_{n-1}\) il MST di \( G_{n-1} \) inoltre \( \operatorname{deg}(v_2) \leq M_{n-1} - 1 \) in \(T_{n-1}\). Dunque per siccome per ipotesi d'induzione abbiamo che in \( G_{n-1} \) il grado massimale di \(T_{n-1}\) non supera \(M_{n-1} = 5 \) (?), allora il grado massimale di \(T_n\) nemmeno.