kevinpirola
04-04-2012, 16:31
Ecco il testo del quesisto (tratto da un gioco per android):
I francobolli vanno considerati come bianchi da entrambi i lati. Due francobolli possono essere ripiegati in un solo modo, tre francobolli in due modi, quattro francobolli in cinque modi. In quanti modi diversi può essere ripiegata una striscia di 7 francobolli?
Non riesco a giungere ad un risultato accettabile.
Premessa. Ho ipotizzato che una piega oraria venga contata con 0 e una antioraria con 1.
Ogni combinazione di pieghe può essere interpretata con una sequenza binaria.
Esempio per 3 francobolli:
00 (due pieghe orarie) perciò la forma dei fb è una specie di spirale.
01 (una piega oraria e una anti) la forma dei fb piegati è una specie di z.
Basandosi su questa affermazione si potrebbe ipotizzare che le combinazioni 11 (che è la NOT di 00) e la 10 (che è la NOT di 01) possano essere eliminate.
Potrebbe anche sembrare che la 01 e la 10 che sono semplicemente anche inverse in ordine siano equivalenti.
Altro inghippo è il tipo di piega, che può essere interna (cioè senza 'scavallare' nessun altra piega) oppure esterna ('scavallando' una o più pieghe). Ad ogni combinazione binara perciò esistono più rappresentazioni figurate delle piegature.
Esempio 1.0.0 se li disegno su un foglio eseguirò:
una riga verticale dall'alto verso il basso, una piega antioraria (quindi una riga verso l'alto) una piega oraria (una riga verso il basso) e un'ulteriore piega oraria potrà andare ad infilarsi sia tra le ultime due pieghe, sia scavallando la piega in modo che l'ultimo francobollo ricopra il primo.
E' però facilmente dimostrabile che 100 e 001 (cioè le pieghe di 4 francobolli) sono ancora equivalenti; ognuno genera due figure che sono equivalenti (speculari) alle due generate dall'altra combinazione.
Non è invece vero che 010000 e 000010 (cioè le pieghe di 7 francobolli) sono equivalenti, nel primo caso infatti le figure generate sono 5 e nel secondo sono 4. Le quattro del secondo sono tutte congruenti a 4 del primo, che però ne aggiunge una.
Perciò non è facilmente eliminabile il caso la sequenza sia il "reverse", perchè non posso eliminarla in tronco, non essendo perfettamente equivalenti, ma non posso tenerla perchè ogni figura deve essere contata solo una volta.
L'idea che inizialmente mi è venuta è questa:
partendo da una piega (0 oppure 1) se la successiva è opposta (1 oppure 0) allora non sarà mai possibile avere situazioni "doppie" in cui la piega può essere disegnata. Il disegno sarà sempre uno zig-zag.
Il problema sussiste con due pieghe dello stesso tipo in sequenza. La seconda piega dello stesso tipo può essere "infilata" in ognuna delle "conche" nello zig-zag generate dalle precedenti pieghe di quel tipo.
Nel caso di due pieghe successive allora andrò a contare quante ne ho già effettutate dello stesso tipo, quello sarà il numero di disegni che potrò creare con quella piega. Partendo da ogni disegno poi ricomincerò il tipo di valutazione. Se dovessi però avere un altra piega dello stesso tipo la situazione si complicherebbe (risulta difficile dimostrarlo a parole sul forum, mi affido alla vostra immaginazione).
Ad oggi non sono riuscito a scrivere un algoritmo decente che mi dia la soluzione corretta.
Voi avete qualche idea?
I francobolli vanno considerati come bianchi da entrambi i lati. Due francobolli possono essere ripiegati in un solo modo, tre francobolli in due modi, quattro francobolli in cinque modi. In quanti modi diversi può essere ripiegata una striscia di 7 francobolli?
Non riesco a giungere ad un risultato accettabile.
Premessa. Ho ipotizzato che una piega oraria venga contata con 0 e una antioraria con 1.
Ogni combinazione di pieghe può essere interpretata con una sequenza binaria.
Esempio per 3 francobolli:
00 (due pieghe orarie) perciò la forma dei fb è una specie di spirale.
01 (una piega oraria e una anti) la forma dei fb piegati è una specie di z.
Basandosi su questa affermazione si potrebbe ipotizzare che le combinazioni 11 (che è la NOT di 00) e la 10 (che è la NOT di 01) possano essere eliminate.
Potrebbe anche sembrare che la 01 e la 10 che sono semplicemente anche inverse in ordine siano equivalenti.
Altro inghippo è il tipo di piega, che può essere interna (cioè senza 'scavallare' nessun altra piega) oppure esterna ('scavallando' una o più pieghe). Ad ogni combinazione binara perciò esistono più rappresentazioni figurate delle piegature.
Esempio 1.0.0 se li disegno su un foglio eseguirò:
una riga verticale dall'alto verso il basso, una piega antioraria (quindi una riga verso l'alto) una piega oraria (una riga verso il basso) e un'ulteriore piega oraria potrà andare ad infilarsi sia tra le ultime due pieghe, sia scavallando la piega in modo che l'ultimo francobollo ricopra il primo.
E' però facilmente dimostrabile che 100 e 001 (cioè le pieghe di 4 francobolli) sono ancora equivalenti; ognuno genera due figure che sono equivalenti (speculari) alle due generate dall'altra combinazione.
Non è invece vero che 010000 e 000010 (cioè le pieghe di 7 francobolli) sono equivalenti, nel primo caso infatti le figure generate sono 5 e nel secondo sono 4. Le quattro del secondo sono tutte congruenti a 4 del primo, che però ne aggiunge una.
Perciò non è facilmente eliminabile il caso la sequenza sia il "reverse", perchè non posso eliminarla in tronco, non essendo perfettamente equivalenti, ma non posso tenerla perchè ogni figura deve essere contata solo una volta.
L'idea che inizialmente mi è venuta è questa:
partendo da una piega (0 oppure 1) se la successiva è opposta (1 oppure 0) allora non sarà mai possibile avere situazioni "doppie" in cui la piega può essere disegnata. Il disegno sarà sempre uno zig-zag.
Il problema sussiste con due pieghe dello stesso tipo in sequenza. La seconda piega dello stesso tipo può essere "infilata" in ognuna delle "conche" nello zig-zag generate dalle precedenti pieghe di quel tipo.
Nel caso di due pieghe successive allora andrò a contare quante ne ho già effettutate dello stesso tipo, quello sarà il numero di disegni che potrò creare con quella piega. Partendo da ogni disegno poi ricomincerò il tipo di valutazione. Se dovessi però avere un altra piega dello stesso tipo la situazione si complicherebbe (risulta difficile dimostrarlo a parole sul forum, mi affido alla vostra immaginazione).
Ad oggi non sono riuscito a scrivere un algoritmo decente che mi dia la soluzione corretta.
Voi avete qualche idea?