Ragazzi

[axpgn]

In ciascuna di $n$ case su una strada diritta, abitano uno o più ragazzi.
In quale punto della via si dovranno incontrare tutti i ragazzi cosicché la somma delle distanze percorse da ognuno, da casa propria al punto di incontro, sia la minima possibile?


Cordialmente, Alex

[Quinzio]

Dovrebbe essere il punto (i punti) dove ci si passa da "piu' ragazzi da una parte" a "piu' ragazzi dall'altra".
Ovvero mettiamo la strada su una asse $x$.
Il numero di ragazzi la cui casa e' situata in posizione minore di $x$ e' una funzione $f(x)$.
Il punto in cui $f(x) = r/2$ e' il punto di incontro, dove $r$ e' il numero di ragazzi.
Questo punto puo' anche essere un punto di discontinuita'.

[axpgn]

Non mi è chiaro e non c'è dimostrazione.

[Quinzio]

"axpgn":Non mi è chiaro e non c'è dimostrazione.

Bene. E' la risposta che mi aspettavo.

$r_i$ e' il numero di ragazzi che abitano nella casa $i$.
$x_i$ e' la posizione della casa $i$.

La distanza che un ragazzo compie per recarsi in $x$ e' $|x-x_i|$.

Quindi la distanza complessiva che i ragazzi fanno per recarsi in $x$ e' $\sum_{i=1}^n r_i|x-x_i|$.

Questa curva e' una spezzata composta da $n-1$ segmenti e le due semirette all'inizio e alla fine.
La curva ha minimo o in uno dei segmenti o in uno dei punti $x_i$.

Il minimo e' unico solo su un segmento o su un punto.
Questo deriva dal fatto che la curva e' convessa e la curva e' convessa perche' e' somma di curve convesse.
Per trovare il minimo troviamo la derivata uguagliata a zero, che e':
$\sum_{i=1}^n r_i \sign(x-x_i) = 0$

Siccome la derivata della funzione e' discontinua, potrebbe anche non esistere un valore per cui la derivata e' zero.
Allora usiamo uno stratagemma: troviamo l'indice minimo $p$, con $1\le p \le n$ per cui
$\sum_{i=1}^p r_i \ge 1/2 \sum_{i=1}^n r_i$


Nel caso in cui la disuguaglianza sia vera anche col segno di uguale abbiamo che il punto d'incontro desiderato e' ogni punto tra la casa $p$ e la casa $p+1$. Questo significa che la funzione distanza ha un segmento orizzontale, ovvero la derivata ha un segmento sullo zero.
Altrimenti, il punto d'incontro e' in corrispondenza della casa $p$, la funzione ha minimo su $x_p$ e la derivata scavalca lo zero.

[axpgn]

Ho capito molto meno di prima
[ot]Non ho detto che non è chiaro ma che sono io che non ho capito granché [/ot]
Comunque non hai ancora detto chiaramente dove si trova 'sto punto
Disegnino? Schemino?


Cordialmente, Alex

[Quinzio]

"axpgn":Ho capito molto meno di prima
[ot]Non ho detto che non è chiaro ma che sono io che non ho capito granché [/ot]

Capisco. Infatti volevo aggiungere che la spiegazione intuitiva e' piu' semplice di una dimostrazione formale, almeno in questo caso.

Comunque non hai ancora detto chiaramente dove si trova 'sto punto
Disegnino? Schemino?

Mo' arrivo.

[Quinzio]

Il grafico qua sotto e' per il caso in cui ci siano 4 case che sono posizionate nelle posizioni $x_i$:
1, 7, 8, 15
Rispettivamente il numero $r_i$ di ragazzi che abita nella singola casa e':
5, 3, 1, 4

Le linee tratteggiate, le "V", rappresentano la distanza che un ragazzo che abita nella casa (dove la V ha il vertice) percorre per arrivare al punto $x$. La funzione e' semplicemente $|x-x_i|$

La funzione distanza, con tratteggio solido, rappresenta
$ \sum_{i=1}^4 r_i|x-x_i| $
si vede che la funzione ha minimo in $x=7$, in corrispondenza della casa 2. Quello e' il punto di incontro.
Questo e' il metodo grafico, ovvio e intuitivo.
PS. La funzione distanza complessiva, con il tratteggio solido, non e' in scala (verticale) per motivi grafici. Ha un fattore di 1/10.

https://www.geogebra.org/calculator/abqyjar8


Vediamo la verifica formale. Abbiamo
$1/2 \sum_{i=1}^n r_i = 13/2$

Per $p=1$
$\sum_{i=1}^p r_i = 5$
Per $p=2$
$\sum_{i=1}^p r_i = 8$
Per $p=3$
$\sum_{i=1}^p r_i = 9$
Per $p=4$
$\sum_{i=1}^p r_i = 13$

Il minimo $p$ che verifica
$\sum_{i=1}^p r_i > 1/2 \sum_{i=1}^n r_i $
e' $p=2$.
La soluzione e': il punto d'incontro e' presso la casa 2, in $x = 7$.

[axpgn]

Premesso che è un bel lavoro , il metodo grafico è ovvio e intuitivo, è vero ma non è una dimostrazione.
Inoltre (e soprattutto) non ti dice immediatamente dove si trova il minimo (anche perché, tra l'altro, dipende dal numero e dalla distribuzione dei ragazzi )
E poi le case sono $n$ (quantità indefinita) quindi col grafico come fai?
Ti manca un passo ... piccolo ...

Cordialmente, Alex

EDIT: Quando ho risposto, la "verifica formale" non l'avevi ancora postata (anche se non cambia niente riguardo quello che ho detto).
Non prendere la brutta abitudine di modificare i messaggi precedenti, la confusione aumenta e spesso si perdono le cose. Thanks.

[Quinzio]

"axpgn":

Premesso che è un bel lavoro , il metodo grafico è ovvio e intuitivo, è vero ma non è una dimostrazione.
Inoltre (e soprattutto) non ti dice immediatamente dove si trova il minimo (anche perché, tra l'altro, dipende dal numero e dalla distribuzione dei ragazzi )
E poi le case sono $n$ (quantità indefinita) quindi col grafico come fai?
Ti manca un passo ... piccolo ...

Guarda, la soluzione c'e' tutta. Onestamente non capisco il senso di $n$ indefinito.

Comunque, immagina questa situazione analoga. E' il modo piu' semplice per capire la dimostrazione formale.
Hai $n$ scatole che rappresentano le $n$ case.
Dentro ogni scatola c'e' una pallina, tutte uguali, una per ogni ragazzo che abita nella casa. La pallina riporta scritto il numero della scatola.
Adesso tira fuori le palline dalle scatole e le metti tutte in fila, conservando l'ordinamento in base al numero della scatola, ovvero a sinistra si comincia da quelle con scritto 1, poi il 2, ecc.
Dividi la fila a meta'.
Osserva il numero della pallina a sinistra della meta' (o in corrispondenza della meta' se il totale delle palline e' dispari).
Quello e' il numero della casa in cui ci si deve incontrare.
Se la pallina a sinistra della meta' e quella a destra hanno due numeri diversi, ci si puo' incontrare in qualunque punto tra le due case.
E' tutto qui.
La dimostrazione formale e' solo tradurre in formule questo algoritmo.
Non c'e' una formula esplicita per trovare il numero della casa, bisogna usare un algoritmo.

Non prendere la brutta abitudine di modificare i messaggi precedenti, la confusione aumenta e spesso si perdono le cose. Thanks.

Giustissimo.

[axpgn]

"Quinzio":Non c'e' una formula esplicita per trovare il numero della casa,

Oh, sì che c'è, è semplicissima e il bello è che l'hai pure scritta
Solamente che, a mio parere, non hai chiaramente dimostrato perché è proprio quello il punto.

Ora non ho tempo per una dimostrazione "completa", sintetizzo.
Siano $r$ i ragazzi in totale e sia $x_i$ la distanza dell'abitazione del ragazzo $i$ dall'inizio della strada.
È sempre possibile ordinare i ragazzi in modo da avere $x_1<=x_2<=...<=x_(r-1)<=x_r$
Se $r$ (non $n$) è dispari allora il punto d'incontro è la casa del ragazzo di "mezzo", se $r$ è pari, il punto d'incontro è uno qualsiasi tra le case dei due ragazzi di "mezzo", case di questi due comprese.

[giammaria2]

Do una facile dimostrazione "completa" di quanto detto da axpgn nel suo ultimo post. Per comodità di lettura, ne ripeto alcune sue frasi; lo dico per evitare accuse di plagio.

Siano $r$ i ragazzi in totale e sia $x_k$ la distanza dell'abitazione del ragazzo $k$ dall'inizio della strada.
È sempre possibile ordinare i ragazzi in modo da avere $x_1<=x_2<=...<=x_(r-1)<=x_r$. Dividiamo ora i ragazzi nelle coppie $(1,r),(2,r-1)...$ (in generale $(k, r+1-k)$): ogni coppia può indifferentemente incontrarsi in qualsiasi punto fra le loro posizioni, perché la strada fatta da uno non è fatta dall'altro.
Quindi se $r$ è dispari la soluzione è la posizione del ragazzo centrale, quello con $k=(r+1)/2$. Se invece $r$ è pari, va bene qualsiasi punto fra le posizioni dei due ragazzi centrali, quelli con $k=r/2$ e $k=r/2+1$

[axpgn]