Esercizio ascensore biennio

Esercizi commentate dei Giochi di Archimede del 27-11-2014
mr96
Messaggi: 1489
Iscritto il: 11/02/2014, 20:37

Re: Esercizio ascensore biennio

Messaggio da mr96 »

Partendo dal 4 se ne facevano 28... In generale, in sti problemi, se non avete qualcosa di logico tentate col più basso e con quello di mezzo :lol:
xXStephXx
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Esercizio ascensore biennio

Messaggio da xXStephXx »

Metto un'immagine per mostrare sia che si può far $28$ sia che non si può far meglio.
Immagine

Ogni volta che attraverso una linea orizzontale sto uscendo da un piano ed entrato in un altro, quindi il numero di piani attraversati aumenta di $1$.
La linea più alta può essere attraversata massimo $2$ volte, perchè l'unica possibilità è visitare l'ultimo piano. La seconda linea più alta la posso attraversare massimo $4$ volte, perchè posso passarci solo quando visito gli ultimi due piani. La terza linea più alta la posso visitare massimo $6$ volte per motivi analoghi.
Da adesso in poi l'ostacolo è dovuto ai piani più bassi, visto che son di meno di quelli più alti. Quindi la linea più bassa la posso attraversare una sola volta (quando arrivo al piano terra), la seconda linea la posso visitare massimo $3$ volte (piano terra più primo piano) e analogamente la terza $5$ e la quarta $7$.
Sommando tutto viene proprio $1+2+3+4+5+6+7=28$. Spero si capisca :D


PS: non posso attraversare la linea centrale $8$ volte perchè per farlo dovrei raggiungere il piano terra e poi risalire.
marcomarco
Messaggi: 63
Iscritto il: 28/06/2014, 11:03

Re: Esercizio ascensore biennio

Messaggio da marcomarco »

era 28 ma ho messo 27 :(
partendo dal 4^ piano :
3giu , 4su , 3 giu , 4 su , 3giu , 4 su ed infine 7 giu
quindi 28
sall96
Messaggi: 156
Iscritto il: 16/05/2013, 19:12

Re: Esercizio ascensore biennio

Messaggio da sall96 »

Volendo si poteva fare anche così:
Partendo dal 4 piano si va al 3, 5, 2, 6, 1, 7 e poi al piano terra: 1+2+3+4+5+6+7= 28 :)
marcomarco
Messaggi: 63
Iscritto il: 28/06/2014, 11:03

Re: Esercizio ascensore biennio

Messaggio da marcomarco »

sall96 ha scritto:Volendo si poteva fare anche così:
Partendo dal 4 piano si va al 3, 5, 2, 6, 1, 7 e poi al piano terra: 1+2+3+4+5+6+7= 28 :)
ma cosi' esce 1+2+3+4+5+6 +1 = 22
sall96
Messaggi: 156
Iscritto il: 16/05/2013, 19:12

Re: Esercizio ascensore biennio

Messaggio da sall96 »

Dal 7° piano al piano terra sono 7 piani non 1 :?:
marcomarco
Messaggi: 63
Iscritto il: 28/06/2014, 11:03

Re: Esercizio ascensore biennio

Messaggio da marcomarco »

sall96 ha scritto:Dal 7° piano al piano terra sono 7 piani non 1 :?:
; perdona , ho considerato i piani ordinati al contrario :shock:
bern1-16-4-13
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: Esercizio ascensore biennio

Messaggio da bern1-16-4-13 »

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.
i piani li chiamiamo da 0 a 7 dal più basso (il piano terra) al più alto. schematizziamo il passaggio da un piano all'altro con una linea che li colleghi. la prima osservazione che credo si possa fare è che per ogni piano che non sia né quello dove si trova inizialmente, né il piano terra, i due piani a lui collegati devono essere o entrambi maggiori o entrambi minori di esso. infatti in un caso in cui sia arrivato al 4 partendo dal 2 e poi sia arrivato al 7 partendo dal 4, è senz'altro più conveniente un tragitto dal 2 al 7 diretto, se il fine è quello dii massimizzare lo spostamento. se abbiamo quindi dei movimenti verso l'alto e verso il basso rigorosamente alternati, poiché l'ultimo movimento sarà verso il basso per arrivare a 0, il primo sarà necessariamente anch'esso verso il basso.
chiameremo estremi alti (EA), quei piani collegati a due piani più bassi (ma 1 soltanto nel caso sia quello iniziale), mentre estremi bassi (EB) quelli collegati a due piani più alti (ma uno soltanto nel caso sia il piano 0 che lo definiamo comunque estremo basso).
prendiamo un qualsiasi percorso possibile che rispetti le due condizioni dette: 4,3,5,2,7,1,6,0.
notiamo che il primo spostamento avviene infatti verso il basso, e che si tratta di spostamenti effettivamente alterni. per calcolare la distanza percorsa in un movimento faremo la differenza maggiore-minore fra i due piani tra i quali è avvenuto. più precisamente se prendiamo un estremo bass0 come il piano 3 nell'esempio fatto, il valore del doppio spostamento 4,3,5 sarà (4-3)+(5-3) o meglio la somma dei due estremi alti a cui l'estremo basso è collegato, meno il doppio dell'estremo basso: 4+5-2*3=3.
ecco che allora possiamo raggruppare i 7 spostamenti avvenuti nel complesso, a due a due: 4,3,5-5,2,7-7,1,6 mentre lo spostamento 6,0 lo lasciamo a parte.
i primi 6 spostamenti avranno quindi distanza complessiva data dalla somma degli estremi alti, contando ovviamente due volte quelli centrali, meno il doppio degli estremi bassi:
4+2*5+2*7+6-2(1+2+3)=22.
se aggiungiamo il settimo dovremmo aggiungere una seconda volta alla somma precedente l'ultimo estremo alto: 4+2*5+2*7+2*6-2(1+2+3)=28.
per massimizzare il risultato occorre quindi che gli estremi alti siano i numeri più grandi, 4,5,6,7; e quelli che tra questi vengono raddoppiati siano 5,6,7 (già il caso che abbiamo analizzato è una soluzione)
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!
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
Ulisse
Messaggi: 2
Iscritto il: 30/11/2014, 12:46

Re: Esercizio ascensore biennio

Messaggio da Ulisse »

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 :cry:
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
Immagine
burt
Messaggi: 346
Iscritto il: 11/06/2015, 23:09

Re: Esercizio ascensore biennio

Messaggio da burt »

c e poco da discutere, visto che la soluzione che rispettava le regole dell esercizio con il numero di piani attraversati piu alti e 28 la soluzione 25 e per forza sbagliata dato che chiedeva il maggior numero di piani attraversati, detto questo anche io come un pollo l ho sbagliata
" l ingegno e la furbizia risiedono nell imparare dall esperienza" cit. Roberto colli " la creatività non è altro che l inteligenza che si diverte " albert einstain
Rispondi