bern1-16-4-13 ha scritto:anche a me torna 28, la cosa più immediata nel mezzo della gara è andare a tentativi, ma secondo me c'è una soluzione matematica che non prova solo che 28 è possibile, ma anche che è la soluzione migliore.
(...)
già che ci siamo possiamo dire che: comincia per forza dal quarto piano, e che le possibili "combinazioni" sono esattamente tutte le possibili permutazioni di 3,2,1 (essa compresa), moltiplicato per tutte le possibili permutazioni di 5,6,7 (essa compresa):3!^2=36
ciao a tutti!
Ciao a tutti. Mi attacco al post di bern per inserire il mio commento perchè è l'unico che ha fornito una spiegazione alla soluzione.
Premetto che mi sono cimentato nella risoluzione perchè un mio studente mi ha chiesto delucidazioni in merito. Devo dire che il quesito è, dal mio punto di vista, particolarmente impegnativo perchè la teoria che sta alle sue spalle non è così ben definita e formalizzabile. Quantomeno non da uno studente del biennio delle scuole medie superiori. Intendo dire che i ragionamenti fatti per arrivare al risultato (gli stessi fatti, in sostanza, da bern) non sono immediatamente riferibili ad un argomento specifico di un corso di matematica ma sono, piuttosto, un mix di varie nozioni di matematica. Mi è stato impossibile osservare il problema e dire: "Ah ecco, lo risolvo con le equazioni" oppure: "lo risolvo con", che so, "il teorema di Pitagora".
Condivido quindi l'idea di bern che nel mezzo della gara la cosa più immediata sia di procedere per tentativi sperando di azzeccare la sequenza corretta nel minor tempo possibile.
A posteriori e con tutto il tempo a disposizione ho però proceduto così.
Prima usato il metodo empirico. Con l'ausilio di excel e di automazione con VBA ho generato tutte le possibili strade percorse dall'ascensore, di ognuna ho misurato la lunghezza e poi ho individuato il massimo che è appunto 28.
L'uso del calcolatore mi ha inoltre consentito di effettuare la stessa esplorazione per diversi valori del numero di piani dell'hotel partendo da un hotel con un solo piano sino ad un hotel con 9 piani (più il piano terra). Oltre non sono andato perchè poi il foglio excel esplode
Così ho scoperto che detto
[tex]k[/tex] il numero di piani (oltre al PT) il percorso più lungo è sempre
[tex]\frac{k(k+1)}{2}[/tex]
Ma a questo punto, pur avendo in mano la risposta corretta e la formula per calcolarla con un generico numero
[tex]k[/tex] di piani non avevo ancora la minima idea del perchè fosse quella la formula giusta.
Di seguito propongo la mia soluzione che segue, come dicevo, gli stessi ragionamenti di bern ma è un pizzico più formalizzata.
Numeriamo i piani da 0 a 7 (dove 0 è il piano terra).
L'ascensore parte da un piano, si sposta ad un altro piano e così via sino al piano 0.
Chiamiamo
[tex]x_1[/tex] il piano di partenza,
[tex]x_2[/tex] il piano di arrivo dopo aver percorso la prima tratta e così via sino a
[tex]x_7[/tex] che sarà l'ultimo piano visitato prima della tratta finale che ci porta a
[tex]x_8=0[/tex] cioè al piano terra.
Con questa convenzione possiamo rappresentare i percorsi seguiti dall'ascensore con dei numeri.
Ad esempio 2121212 significa che il ragazzino è salito al secondo piano e si è divertito a fare sali-scendi un po' di volte prima di ritornare al piano di partenza.
Tutti i numeri vanno bene? Ovviamente no.
Intanto sono esclusi i numeri contenenti la cifra 8 e la cifra 9 perchè i piani sono solo 7.
Poi sono esclusi tutti i numeri che non contengono le cifre da 0 a 7 prese ognuna una ed una sola volta perchè la richiesta è che tutti i piani dell'hotel vengano visitati una ed una sola volta.
Infine sono esclusi tutti i numeri che non finiscono per 0 perchè la richiesta è che il tragitto si concluda al piano terra.
Pertanto gli unici percorsi che soddisfano tali condizioni sono le permutazioni dei primi interi da 1 a 7 alle quali accostiamo uno 0 finale.
In formule un cammino valido è rappresentato dal numero
[tex]x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8[/tex] in cui le cifre
[tex]x_i[/tex] devono soddisfare le condizioni:
[tex]x_8=0[/tex] e
[tex]x_i \neq x_j[/tex] [tex]\forall i \neq j[/tex].
Ora dobbiamo scrivere la formula per calcolare la distanza percorsa dall'ascensore:
[tex]D=|x_1-x_2|+|x_2-x_3|+|x_3-x_4|+|x_4-x_5|+|x_5-x_6|+|x_6-x_7|+|x_7-x_8|[/tex]
Possiamo iniziare la semplicazione di questa formula spendendo la prima condizione
[tex]x_8=0[/tex] che però non ci porta molto lontano:
[tex]D=|x_1-x_2|+|x_2-x_3|+|x_3-x_4|+|x_4-x_5|+|x_5-x_6|+|x_6-x_7|+x_7[/tex]
A questo punto, per proseguire serve qualche ragionamento.
Abbandoniamo la ricerca del percorso più lungo e chiediamoci quale sia il percorso più breve. "Il cammino più breve tra due punti è quello in linea retta". Ovvero senza cambiare mai direzione di marcia. Pertanto per realizzare il cammino più breve dobbiamo partire dal piano più alto e scendere di un piano alla volta visitandoli tutti sino al PT
senza mai invertire la marcia.
Tale cammino è rappresentato dal numero 76543210 la cui lunghezza è
[tex]D=7[/tex].
Sulla base di tale osservazione dobbiamo quindi aspettarci che il cammino più lungo sia quello col maggior numero di cambi di direzione. Ciò capita se il ragazzino cambia direzione ad ogni tratta. Poichè le tratte sono in numero di
[tex]k=7[/tex] e l'ultima tratta che raggiunge il PT deve essere necessariamente in discesa avremo la prima tratta in discesa, la seconda in salita e via così.
In formule avremo:
[tex]x_i - x_{i+1} > 0[/tex] se
[tex]i[/tex] è dispari e
[tex]x_i - x_{i+1} < 0[/tex] se
[tex]i[/tex] è pari.
Questo è un risultato importante perchè ci consente di risolvere tutti valori assoluti contenuti nella formula di calcolo della lunghezza del tragitto dell'ascensore. Tale formula, dopo le opportune riduzioni, diventa:
[tex]D=x_1+2(x_3+x_5+x_7)-2(x_2+x_4+x_6)[/tex]
Osservando ora la formula risulta chiaro che per massimizzare
[tex]D[/tex] è necessario attribuire i valori più grandi alle variabili
[tex]x_1[/tex],
[tex]x_3[/tex],
[tex]x_5[/tex] e
[tex]x_7[/tex] che compaiono con segno positivo e quindi contribuiscono ad incrementare
[tex]D[/tex] e i valori più piccoli alle variabili
[tex]x_2[/tex],
[tex]x_4[/tex] e
[tex]x_6[/tex] che compaiono con segno negativo e quindi contribuiscono a ridurre il valore finale di
[tex]D[/tex].
Pertanto riserveremo i numeri 4, 5, 6 e 7 alle variabili
[tex]x_1[/tex],
[tex]x_3[/tex],
[tex]x_5[/tex] e
[tex]x_7[/tex] e i numeri 1, 2 e 3 alle variabili
[tex]x_2[/tex],
[tex]x_4[/tex] e
[tex]x_6[/tex].
Osserviamo inoltre che, mentre
[tex]x_1[/tex] compare con coefficiente 1, le altre tre variabili con segno positivo hanno coefficiente pari a 2.
Ancora una volta per massimizzare
[tex]D[/tex] dobbiamo attribuire a
[tex]x_1[/tex] il valore più piccolo possibile. Quindi, inesorabilmente,
[tex]x_1=4[/tex].
Cioè il percorso più lungo
deve partire dal piano centrale (se k è dispari mentre se k è pari si conclude con analogo ragionamento che si deve partire da uno dei
due piani centrali).
In pratica abbiamo finito perchè
[tex]x_1=4[/tex] è ormai noto. Altrettanto note sono le somme
[tex]x_3+x_5+x_7=5+6+7=18[/tex] e
[tex]x_2+x_4+x_6=1+2+3=6[/tex] che possiamo calcolare pur non conoscendo l'assegnazione precisa di ogni singola variabile (grazie alla proprietà commutativa della somma).
Quindi
[tex]D=4+2\cdot 18 -2\cdot 6=28[/tex].
A corollario osserviamo che la libertà di assegnazione della terna di numeri
[tex]\{5, 6, 7 \}[/tex] alla terna di variabili
[tex]\{x_3, x_5, x_7\}[/tex] e la terna di numeri
[tex]\{1, 2, 3 \}[/tex] alla terna di variabili
[tex]\{x_2,x_4,x_6\}[/tex] porta a perdere univocità della soluzione. I percorsi che realizzano la massima lunghezza sono tanti quante le permutazioni di 3 oggetti in 3 posti sia per una che per l'altra terna ovvero sono in numero di
[tex]3!\cdot 3!=36[/tex].
Detta
[tex]h=\left \lfloor \frac{k-1}{2} \right \rfloor[/tex], cioè la parte intera di
[tex]\frac{k-1}{2}[/tex], nel caso generico di
[tex]k[/tex] piani, le soluzioni equivalenti sono
[tex]h!\cdot h![/tex] se
[tex]k[/tex] è dispari e
[tex]h!\cdot (h+1)![/tex] se
[tex]k[/tex] è pari.
Considerazione finale: la molteplicità delle soluzioni ci consente di scegliere la più comoda tra le soluzioni equivalenti per calcolare la lunghezza massima del percorso. E tra le soluzioni ce ne è una in particolare che può essere individuata per ogni valore di k ragionando a ritroso: si parte dal PT e si sale all'ultimo piano poi si scende al primo, si risale al penultimo, si scende sino al secondo, eccetera. Quindi, sempre ragionando a ritroso, l'ultima tratta sarà lunga k, la penultima k-1, poi k-2 e via via sino alla prima tratta che (in salita o in discesa non importa) sarà lunga 1 e il totale sarà quindi dato dalla somma dei primi k interi:
[tex]D=\frac{k(k+1)}{2}[/tex]
Rappresentazione grafica della soluzione 43526170