Distanza minore

[Pachisi]

Un ragazzo abita in ognuna di $n$ case che si trovano su una retta. Dove si devono incontrare gli $n$ ragazzi in modo tale che la somma delle distanze che devono camminare dalle loro case sia la minima possibile?

[kobeilprofeta]

Testo nascosto, fai click qui per vederlo

$\sum_1^{x-1} (x-j)+\sum_{x+1}^n (j-x)=(x-1)*x-frac{(x-1)*x}{2}+1/2*(n-x)*(n+x+1)-x*(n-x)=frac {x^2-x}{2}+frac {n^2+n-nx-x}{2}=frac {x^2+(-n-2)x+n^2+n}{2}$
La derivata è $(2x-n-2)/2$ Quindi la funzione ha un minimo per $x=(n+2)/2

[MathematicalMind]

Testo nascosto, fai click qui per vederlo

Se $n$ è dispari si devono incontrare a casa di quello centrale, se $n$ è pari si possono incontrare in qualunque punto tra le case dei due centrali. Infatti spostando il punto di incontro verso destra di una certa distanza $d$ abbastanza piccola da non oltrepassare case se ci sono $k$ case a sinistra e $h$ case a destra la somma delle distanze aumenta di $dk$ e diminuisce di $dh$, quindi diminuisce se e solo se $k<h$. Spostando a sinistra, analogamente, la distanza diminuisce se e solo se $k>h$. Quindi è evidente che il caso ottimale è $k=h$ (altrimenti spostando il punto di incontro di casa in casa si arriva proprio a questo caso migliorando la somma delle distanze) che è proprio il caso descritto prima.

Rilancio: le $n$ case non si trovano necessariamente su una retta, ma esistono strade che collegano tra di loro due case in modo tale che per ogni coppia di case esista uno e un solo percorso di strade che le congiunge. Dimostrare che il punto di incontro che minimizza la somma delle distanze è unico oppure è confinato in una delle strade.

[dan95]

@kobe
$x$ è reale non può stare come indice di sommatoria...ma integrale sarebbe meglio

[anto_zoolander]

Testo nascosto, fai click qui per vederlo

considero la retta affine in cui considero fissato $R(O,vec(e))$ con $||e||=1$
Siano $P_1,...,P_n$ punti di $RR$ tali che abbiano coordinate $P_(j)(x_j),forallj=1,..,n$
Senza ledere la generalità suppongo che $x_1leqx_2leq...leqx_n$ poiché a meno di una successione di scambi, rienumerando gli $x_j$ il problema si dimostra essere lo stesso.

Dunque sia $P(x)$ un punto variabile della retta e considero $forallj=1,..,n$ la distanza $vec(d_k(x))=vec(P_jP)(x-x_j)$ dunque il problema si riduce nel minimizzare $sum_(k=1)^(n)||d_k(x)||$ ovvero i vettori spostamento.

Posto $S(x)=sum_(k=1)^(n) |x-x_k|$ noto che $S:RR->RR$ è una funzione continua su tutto $RR$. Inoltre noto che posto $X-{x_1,...,x_n}$ la funzione $f:X->RR$ è anche derivabile. $S’(x)=sum_(k=1)^(n)sign(x-x_k)$

Ora se $n$ è pari abbiamo che essendo la funzioni segno variabili tra $1,-1$ allora per annullarsi devo avere la stessa quantità di $1,-1$ e questo accade se e solo se $x in(x_(n/2-1),x_(n/2+1))$ (questa proprietà la possiamo considerare dopo aver supposto i punti allineati).

Se $n$ è dispari allora non assume mai un minimo in quel dominio. Ragionando sul segno avremo sempre un $1$ o $-1$ in più rispetto all’altro, dunque almeno uno degli addendi deve essere nullo e questo è vero se e solo se $x$ è il punto ‘nel mezzo’.

Volevo formalizzarla un po’ meglio ma sto scoppiando dal sonno, quindi casomai lo edito domani.
So che usare vettori e analisi in questa sezione è un po’ esagerato, però ho visto che gli altri hanno già dato risposte e penso siano diverse.

[Pachisi]

@kobeilprofeta: Non ho capito, ma è sbagliata perché vengono due casi.
Mi trovo con i risultati degli altri.

@MathematicalMind: Per il rilancio riesco a dimostrare che il punto è unico solo quando le case sono i vertici di un poligono regolare

Testo nascosto, fai click qui per vederlo

dovrebbe essere il circocentro del poligono

Magari un hint per il caso generale?

[MathematicalMind]

Forse non ti è chiaro il testo: le case sono collegate da strade e i ragazzi si possono muovere solo sulle strade (quindi il punto di incontro sarà su una di esse, e potrebbe essere anche in una casa). Si chiede di dimostrare che quello che minimizza la somma delle distanze è unico oppure si possono scegliere equivalentemente più punti ma tutti sulla stessa strada.
Ulteriore chiarimento: non è un problema di geometria, anzi le strade non sono neanche necessariamente rettilinee: si tratta semplicemente di un grafo tra le $n$ case (in realtà un albero vista l'ipotesi secondo cui tra ogni coppia di case esiste uno e un solo cammino). E naturalmente, come in tutti i grafi, non ci sono strade che si intersecano in punti diversi dagli estremi.