dal sito della Rowling

Giochini matematici elementari ma non olimpici.
Rispondi
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

dal sito della Rowling

Messaggio da SkZ »

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
Ultima modifica di SkZ il 10 apr 2009, 16:35, modificato 1 volta in totale.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa »

Riesumo il post :lol:

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.. :roll:
Anche perchè è molto empirica come formula :lol:

Qualcuno ci conferma il risultato?
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

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'
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa »

Fino alla seguenza perfetta ci sono..
Però non ho capito come hai trovato la formula per il numero di caratteri della seguenza ridondante :oops:
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

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 :evil:
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Avatar utente
Cassa
Messaggi: 236
Iscritto il: 28 mar 2006, 21:48
Località: Genova

Messaggio da Cassa »

Ok perfetto grazie :D

PS. si forse era per quello :twisted:
spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Messaggio da spugna »

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)
Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco »

mica tanto :shock:
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

e la sequenza ABCED, ad es, dove la metti?
hai solo coperto 5 delle 120 possibili seguenze
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Messaggio da spugna »

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
g(n)
Messaggi: 109
Iscritto il: 14 ott 2007, 19:24
Località: Codroipo, il paese più anagrammato d'Italia

Messaggio da g(n) »

Da quanto visto sopra si intendono lettere consecutive, cioè la sequenza dovrebbe contenere A-B-C-E-D di seguito
spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Re: dal sito della Rowling

Messaggio da spugna »

SkZ ha scritto:basta che tale ordine venga completato ad un certo punto.
....................................................................................................................
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

mi sembrava ovvio che per sequenza indicassi sequenza di lettere consecutive
cmq correggo il testo
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Rispondi