Prendo spunto da un recente problema della staffetta per proporvi queste due varianti.
[tex]n[/tex] aerei sono in partenza dalla pista di decollo. Ogni aereo ha inizialmente il serbatoio pieno. Il carburante contenuto nel serbatoio di un aereo (pieno) è esattamente sufficiente a consentirgli di percorrere un fantasticometro ( ). In qualsiasi momento, durante il volo, è possibile trasferire istantaneamente una quantità di carburante a piacere da un aereo all'altro. Sapendo che gli aerei partono contemporaneamente, si muovono in linea retta e a velocità costante, e il consumo di carburante è proporzionale al tempo trascorso, qual è l'odine di grandezza del minimo [tex]n[/tex] tale che almeno un aereo riesca a percorrere [tex]10[/tex] fantasticometri? (NB: Gli aerei non devono ritornare alla base, ma possono essere tranquillamente sacrificati).
Stessi dati del precedente, ma stavolta gli aerei devono ritornare sani e salvi alla base, dove non possono rifornirsi di carburante né ripartire (che tra l'altro sarebbe inutile).
Dato un [tex]k[/tex] grande a piacere, è sempre possibile trovare un [tex]n[/tex] tale che almeno un aereo riesca a coprire almeno [tex]k[/tex] fantasticometri?
Quanti fantasticometri riesce a percorrere, al massimo, almeno uno degli [tex]n[/tex] aerei?
[Edit] Chiarimento per il punto 2): l'ultimo aereo non necessita di tornare alla base, ma può tranquillamente continuare il suo viaggio fino ad esaurimento carburante.
Ultima modifica di cip999 il 12/01/2015, 20:49, modificato 2 volte in totale.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre. Albert Einstein
Provo a dare una risposta così su due piedi, ma con non troppa sicurezza...
1. Se facciamo fermare gli aerei dopo mezzo fantasticometro, ognuno avrà il serbatoio a metà: possiamo sacrificare metà degli aerei perché quegli altri abbiano nuovamente il carburante necessario. Se facciamo questo ogni mezzo fantasticometro, ripeteremo il procedimento 18 volte, finché quando saremo a $9$ fantasticometri ci sarà un solo aereo col serbatoio pieno. Dunque, se il numero degli aerei viene dimezzato per ogni passaggio, vuol dire che se ne resta uno dopo 18 procedimenti, $n=(1*2)^17$, cioè $131072$, il cui ordine di grandezza è $5$, infatti $131072=1,31072*10^5$; da notare che viaggiando gli aerei a velocità costante, è inutile tornare alla base per poi ripartire.
Poi il secondo punto non lo so XD
C'è chi ha definito ogni persona come una guerriera della vita... ed allora ogni matematico combatte una guerra eterna contro i numeri per conquistarli: e più saremo in tanti a combattere tali battaglie, prima la vinceremo. Cit.Me
Conviene che un aereo ceda agli altri il suo carburante non appena è in condizione di farlo (perché?). Naturalmente, nel caso 2) nel serbatoio deve rimanere una quantità di carburante sufficiente per tornare a casa...
PS: Ho editato l'OP aggiungendo un chiarimento per la seconda variante.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre. Albert Einstein
Per il punto $1$
Generalizziamolo con una distanza $d$
Supponiamo che la prima volta che si ferma qualche aereo se ne fermino $m_1$, la seconda $m_2$, $\ldots $, l'ultima $m_p$
Vale $\displaystyle{\sum_{r=1}^p m_r=n-1}$
Inoltre supponiamo che i primi $m_1$ si fermino dopo un tempo $a$ (supponiamo per comodità che gli aerei percorrano un fantasticometro in un fantasticosecondo usando un fntasticolitro di carburante e che $a$ sia in fantasticosecondi)
Allora ogni aereo avrà usato $a$ carburante
A questo punto gli aerei, per massimizzare le distanze, riempiranno gli altri $n-m_1$
Quindi $(1-a)m_1=a(n-m_1)$
$a=\frac {m_1} n$
Ripetendo il ragionamento per i successivi otteniamo che quando si fermano $m_s$ aerei, ognuno dei rimanenti ottiene $\displaystyle{\frac {m_s} {n-\displaystyle{\sum_{r=0}^{s-1} m_r}}}$ carburante
Con $m_0=0$
Ma alla fine l'ultimo aereo deve ricevere $d-1$ carburante
Quindi
$\displaystyle{\sum_{s=1}^p (\frac {m_s} {n-\displaystyle{\sum_{r=0}^{s-1} m_r}})=d-1}$
Ma $\frac {m_1} n=\frac 1 n+\frac 1 n+\ldots +\frac 1 n\le \frac 1 n+\frac 1 {n-1}+\ldots +\frac 1 {n-m_1+1}$
E lo stesso vale per le altre somme con i relativi denominatori di partenza
L'uguaglianza si ha per $m_1=m_2=\ldots =m_p=1$
Se uno dei valori fosse maggiore occorrerebbero più elementi e aumenterebbe $\displaystyle{\sum_{r=1}^p m_r=n-1}$
Quindi per minimizzare $n$ rispetto a $d$, cioè in questo caso massimizzare $d$ rispetto a $n$, il primo aereo deve fornire $\frac 1 n$ carburante a ogni altro aereo dopo $\frac 1 n$ distanza, con $n$ aerei in volo, fino a giungere a $1$ solo aero che percorrerà dunque
$\displaystyle{\sum_{m=1}^n \frac 1 m}$ fantasticometri
Tornando all'esercizio particolare, poichè questa somma va come $ln(n)$ per percorrere $10$ fantasticometri servono $e^{10}$ aerei, che è dell'ordine di $10^4$
Per il punto $2$
Procediamo allo stesso modo, ma il primo che si ferma, dopo un tempo $a_1$ deve tenere carburante per tornare
Quindi $1-2a_1=a_1\cdotp (n-1)$
$a_1=\frac 1 {n+1}$
Dimostriamo per induzione che ogni aereo cederà $\frac 1 {n+1}$ a ognuno degli altri dopo un tempo $\frac 1 {n+1}$
Passo base dimostrato
Supponiamo ora che fino all'$m$-esimo sia stato ceduto $\frac 1 {n+1}$
L'$m+1$-esimo dovrà tenerne $\frac {m} {n+1}$ per coprire la distanza fatta finora
Gli resta dunque $\frac {n+1-m} {n+1}$ carburante con cui ripetere il ragionamento fatto col primo
$\frac {n+1-m} {n+1}-2a_{m+1}=a_{m+1}(n-(m+1))$
Da cui $a_{m+1}=\frac 1 {n+1}$
Dunque l'ultimo aereo guadagnerà dagli altri $n-1$ in totale $\frac {n-1} {n+1}$
Quindi percorrerà $1+\frac {n-1} {n+1}$ che tende a $2$ al crescere di $n$
Il che, se fosse giusto, risolverebbe sia la parte $a$ sia la $b$
Il punto $1$ si può anche vedere per ricorsione
Quindi, supponiamo che la distanza massima con $n$ aerei sia $d_n$
Supponiamo che il primo aereo si fermi dopo $a$ distanza
Allora dobbiamo massimizzare $d_{n+1}=a+d_n(\frac {(1-a)(n+1)} n)$
Moltiplicando $d_n$ per il carburante rimasto
Quest, svolgendo i calcoli dà che $d_{n+1}$ è massimo quando $a$ è minimo
Ma per $a<\frac 1 {n+1}$ del carburante andrebbe sprecato quindi non sarebbe una soluzione vantaggiosa
Sarebbe infatti uguale al caso con $a=\frac 1 {n+1}$ ma con meno distanza iniziale percorsa
Quindi il massimo si ha per $a=\frac 1 {n+1}$
Sostituendolo otteniamo
$d_{n+1}=d_n+\frac 1{n+1}$
Con $d_1=1$
Da cui la formula precedentemente trovata
Per il punto 1) si poteva notare che conviene che un aereo ceda tutto il suo carburante agli altri non appena è possibile farlo (senza sprechi). Quindi, detta [tex]x[/tex] la distanza ottimale da percorrere prima di sacrificare un aereo, si imposta la semplice equazione [tex]1 - x = (n - 1)x[/tex]
da cui [tex]\displaystyle x = \frac{1}{n}[/tex]
E quindi abbiamo la legge ricorsiva [tex]\displaystyle d_{n + 1} = d_n + \frac{1}{n + 1}[/tex], che ci porta a [tex]\displaystyle d_n = \sum_{i = 1}^n \frac{1}{i}[/tex].
Poi boh, è interessante notare che quella somma, come hai detto te, approssima sempre meglio [tex]\ln(n)[/tex] per [tex]n[/tex] grandi (in realtà il limite per [tex]n \rightarrow \infty[/tex] è [tex]\ln(n) + \gamma[/tex], dove [tex]\gamma[/tex] è la costante di Eulero-Mascheroni). Comunque [tex]e^{10}[/tex] è una buona approssimazione per eccesso del risultato esatto, che sicuramente rientra nello stesso ordine di grandezza, come tra l'altro ci conferma un caro amico...
Vai col prossimo!
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre. Albert Einstein
). In qualsiasi momento, durante il volo, è possibile trasferire istantaneamente una quantità di carburante a piacere da un aereo all'altro. Sapendo che gli aerei partono contemporaneamente, si muovono in linea retta e a velocità costante, e il consumo di carburante è proporzionale al tempo trascorso, qual è l'odine di grandezza del minimo [tex]n[/tex] tale che almeno un aereo riesca a percorrere [tex]10[/tex] fantasticometri? (NB: Gli aerei non devono ritornare alla base, ma possono essere tranquillamente sacrificati).
