OliForum Matematico

forse sarebbe da combinatoria, ma non so la soluzione (non ho ancora voglia di fare i conti)

per entrare in una stanza segreta devo cliccare su tutti i 5 mattoni A B C D E in sequenza continua con ordine ben definito e una sola volta, ma la sequenza non deve essere "pulita" (prima o dopo si possono cliccare altri mattoni), basta che tale ordine venga completato ad un certo punto. Ad es. se la successione e' ABCDE e clicco AABEABCDE riesco ad entrare, mentre con ABCDAE no

Quanto e' lunga la minima sequenza di click tale per cui sono sicuro di riuscire ad entrare?

edit: specificato meglio che la sequanza deve essere senza interruzioni in mezzo

Riesumo il post

Un mio compagno di squadra pensa di aver trovato la soluzione [153] usando una formula generale creata ad hoc, ma abbiamo un pò di dubbi..
Anche perchè è molto empirica come formula

Qualcuno ci conferma il risultato?

io l'avevo lasciato morire perche' poco dopo mi ero accorto che era piu' semplice di quanto mi era sembrato (non mi ero proprio applicato a risolverlo prima di postarlo)

di base hai 24 sequenze minime forzate (smf d'ora in poi).
Si generano scegliendo una lettera fissa, diciamo A, e poi permuti le altre 4 (4!=24). Poi scrivi 2 volte queste subsequenze ad anello. Le smf si ottengono togliendo tagliando una lettera all'anello (togli una lettera e distendi l'anello)
usi queste sequenze facendo modo da sovrapporre il piu' possibile gli estremi. E si vede che la sovrapposizione massima e' $ ~n-2 $ lettere e si ottiene mettendo assieme le sequenze generate da $ ~n-1 $ lettere poste fisse e ponendo l'ultima nelle 4 posizioni possibili (ricordo che e' una struttura ad anello ergo prima e ultima posizione si equivalgono). es
ABCDEABCD AEBCDA BECDAB CEDABC (ABCDE +AEBCD+ABECD+ABCED)
i raggruppamenti di $ ~n-1 $ smf (d'ora in poi Gsmf) che si possono ottenere sono $ ~(n-2)! $: una lettera la posizioni dopo, una lettera la usi come indice (altrimenti ti ritrovi con n doppioni), ergo ti rimangono $ ~n-2 $ da sistemare

se si potesse fare una sequenza perfetta, in cui le sequenze di n lettere si ripetono tutte e solo una volta, sarebbe lunga $ ~(n-1)+n! $, quindi in questo caso 124
una sequenza ridondante e' quella con le Gsmf uno dopo l'altra, che sono $ ~(2n^2-6n+7)(n-2)! $ caratteri, quindi in questo caso 162
1-2 ripetizioni riesci a eliminarle se si fa attenzioni nelle giunzioni ergo si puo' stimare in 152-157 casi

direi che il valore ci sta'

Fino alla seguenza perfetta ci sono..
Però non ho capito come hai trovato la formula per il numero di caratteri della seguenza ridondante

ovvio che non hai capito, manco il mio prof di mate capiva come risolvevo i compiti dato che meta' dei passaggi li facevo a mente (divisioni di ruffini incluse)

la Gsmf sono formate da 1 smf + (n-2) smf tronche di (n-2) caratteri
ergo hai, dato che una smf ha 2n-1 caratteri
$ ~(2n-1)+(n-2)(2n-1 -(n-2))=2n-1+(n-2)(n+1)=n^2+n-3 $
e come vedi c'era un errore nel conto precedente (purtroppo le due formule danno lo stesso risultato per n=5). per questo non ti tornava

quindi
una sequenza ridondante e' quella con le Gsmf uno dopo l'altra, che sono $ ~(n^2+n-3)(n-2)! $ caratteri
sempre $ ~27\cdot 3!=162 $


PS: no, non era perche' sbagliavo i conti che il mio prof non capiva

Ok perfetto grazie

PS. si forse era per quello

mi credete se vi dico che per me è 21??

(A-B-C-D-E-A-B-C-D-E-A-B-C-D-E-A-B-C-D-E-A)

mica tanto

e la sequenza ABCED, ad es, dove la metti?
hai solo coperto 5 delle 120 possibili seguenze

SkZ ha scritto:e la sequenza ABCED, ad es, dove la metti?

qui:

A-B-C-D-E-A-B-C-D-E-A-B-C-D-E-A-B-C-D-E-A

Da quanto visto sopra si intendono lettere consecutive, cioè la sequenza dovrebbe contenere A-B-C-E-D di seguito

SkZ ha scritto:basta che tale ordine venga completato ad un certo punto.

....................................................................................................................

mi sembrava ovvio che per sequenza indicassi sequenza di lettere consecutive
cmq correggo il testo