Newsgroup: it.hobby.enigmi
Titolo: Sequenze di pentamini

[per vedere l'ascii-art, usare caratteri fissi]
   _ _   _   _     _ _   _   _ _ _
 _|  _| | | | |   |   | | | |_   _|
|_  |   | | | |   |  _| | |_  | |
  |_|   | | | |_  |_|   |_  | |_|    _ _
        | | |_ _|         |_|       |  _|
        |_|              _          | |_
 _       _         _    | |_   _ _  |_ _|
| |     | |_     _| |_  |  _| |_  |
| |_ _  |_  |_  |_   _| | |     | |_
|_ _ _|   |_ _|   |_|   |_|     |_ _|
ATTO I
Partite da un pentamino a piacere e, spostando un
solo quadrato, trasformatelo in un altro.
Ora, partendo da quest'ultimo, ripetete l'operazione.
Ripetete poi l'operazione per complessive 12 mosse
in modo da ritornare al pentamino di partenza dopo
aver formato una sola volta ciascun pentamino.
Troppo facile?
ATTO II
Se avete trovato il quesito precedente troppo facile,
vi sarete accorti che le sequenze cicliche cosiffatte
sono parecchie.
Quante?
[Tutti i metodi sono leciti]
Ciao!!!  ((^__^))'
Livio

 Quante?
Veramente tante, non so però quante. O meglio, arrivo ad un risultato che
non può essere giusto perchè mi sono incasinato troppo. Intanto lo posto,
magari qualcuno riesce a capire le mie forneticazioni e riesce a correggerle
(non sono sicuro di aver sbagliato qualche cosa, diciamo che è molto
probabile :-)
Facciamo intanto uno schemino delle trasformazioni possibili per ogni
pentamino:
F -> tutte tranne la I
L -> tutte tranne W e X
I -> L,Y
P -> tutte tranne la I
N -> tutte tranne I e X
T -> tutte tranne I e W
U -> F,L,P,N,T,V,Y,Z
V -> tutte tranne I e X
W -> F,P,N,V,Z
X -> F,P,Y,T
Y -> tutte tranne la W
Z -> tutte tranne I e X
Vediamo che l'anello *debole* è la I, un passaggio obbligato di tutte le
catene dovrà quindi essere:
...-L-I-Y-...
A questo punto dobbiamo trovare quante possibili sequenze esistono per
Y-........-L
in cui non deve essere presente la I ma tutti gli altri 11 pentamini.
Altra considerazione è che la F e la P legano con tutte (tranne la I gia
sistemata) e quindi possiamo, in un primo momento, lasciarle fuori dal
nostro conto. In un secondo momento potranno essere inserite in ciascun
punto della catene ed andremo ad aumentare le soluzioni di un fattore
10x10+10=110 (ognuna delle due due pentamini possono essere inserite in 10
posizioni diverse, quando vengono inserite nella stessa posizione hanno due
possibilità FP o PF).
A questo punto, tolta la I, la P e la F, notiamo che, per la X può essere
legata solo a Y e T e quindi la catena risulta obbligata come segue :
[1]  Y-X-T-..........-L
che da luogo al fattore moltiplicativo 110 come prima detto.
Oppure si potrebbe avere
[2]  Y-T-X-(F o P)-.........-L
che da luogo ad ad un fattore moltiplicativo 10x2=20 (inserendo quella tra F
e P che non metto dopo la X in una delle 10 possibili posizioni intermedie).
Ci rimangono ora da sistemare N,U,V,W e Z. In quanti modi si può fare? Non
lo so :-)
Vediamo di sviluppare la [1]
Delle rimanenti la U è l'unica che non può legare con la W, altrimenti tutte
legano con tutte. Sistemiamo allora la N,V,W e Z. La W non può legare con
gli estremi T e L allora dovrà occupare una posizione centrale. Si può
vedere che possono essere sistemate in 12 modi diversi, inserendo la U in
uno dei 3 spazi ad essa consoni abbiamo 12x3=26 combinazioni diverse.
Cosi abbiamo 36x110=3960 catene diverse.
 Altrimenti la W potrebbe essere legata a T o L tramite F o P. Dobbiamo
allra aggiungere un certo numero di combinazioni. Consideriamo che sia
legata attraverso la F a T (dovremo poi moltiplicare per 4, per i cambi di F
con P e L con T). Abbiamo quindi 6x3x4=72 combinazioni (6 per le N,V e Z e
x3 contando la U). Vanno moltiplicate per 10 quando si inserisce l'altra tra
F e P: 720 combinazioni.
Per la catena [1] abbiamo in totale 3960+720=4680 catene possibili.
Vediamo di sviluppare la [2]
La W non può legare con la L, allora per N,V,W e Z abbiamo 3x3x2=18
possibilità Dobbiamo poi inserire la U in uno tra 3 posti disponobili e ne
ricaviamo 54 combinazioni, moltiplichiamo per 20 (inserendo quella tra F e P
che ancora manca e scambiano F e P) e otteniamo altre 1080 combinazioni.
 Se invece W fosse legata a L tramite l'altra tra F e P, abbiamo 3x3x2=18
combinazioni che vanno moltiplicate per 2 scambiano P e F.
In totale altre 36+1080=1116 catene.
In totale ottengo 5796 catene possibili.
Sono riuscito a contare tutto o mi manca ancora qualche cosa?
Un saluto,
GaS

 possibilità FP o PF).
Qui non ti seguo piu'. Quando *inseriro'* P o F, i vincoli del
precedente e del seguente cambieranno... E' vero che ogni sequenza
che generero' sara' lecita, ma le generero' tutte?
Cmq il mio nr. finale e' diverso (potrebbe essere sbagliato il mio, neh).
Ciao!!!  ((^__^))'
Livio

 Cmq il mio nr. finale e' diverso (potrebbe essere sbagliato il mio, neh).
a me viene un rotondo 14400
Ho provato sia controllando la validità delle catene ILxxxxxxxxxY DOPO la
generazione delle permutazioni dei 9 pentamini (esclusi L,I,Y), sia potando
al volo i rami secchi e fortunatamente mi torna 14400
-- 
Ciao, Silv:o)

 a me viene un rotondo 14400
Ciao Silvio!
Anche a me viene un rotondo.
45.000 pero'.  :o(
Se il giusto e' nel mezzo, sei a cavallo.
Anch'io son partito dalla sequenza LIY fissa a cui aggiungo le
362.880 permutazioni, tagliando i rami impossibili. Essi sono
quelli che cominciano per W o finisconono per X o W oppure
contengono una coppia impossibile, nei due sensi.
Riverificheremo....
Ciao!!!  ((^__^))'
Livio

 contengono una coppia impossibile, nei due sensi.
nei due sensi?
la relazione di "trasformabilità" non è simmetrica?
Comunque avevo sbagliato un vincolo.
Ora mi viene 16.800
-- 
Ciao, Silv:o)

            16.800
Dai Livio: abbassa un pò la richiesta che magari Silvio ti viene ancora
incontro e si aggiudica il set di pentamini :o))
Scusate ma non ho saputo resistere.
GaS
P.S.: E io che volevo risolvere a mano qualcosa su cui neanche due forza
brutisti affermati [leggasi Livio e Silvio] riescono a mettersi daccordo....

 incontro e si aggiudica il set di pentamini :o))
Eh... non c'e' niente da fare. Quando si parla di calcolo combinatorio,
Silvio non lo batte nessuno. Ebbene si', verificati i conti, trovato
il bug (in una stringa chiamavo il pentamino "U" con "C" e 'sto
stupido di PC non capisce che sono lo stesso pezzo!), e' uscito
il numero magico giusto:  ***16.800***
C'aggia fa?  :o))
Ciao!!!  ((^__^))'
Livio
PS.: In quanto al set di pentamini, si qualcuno si aspetta ch'io mantenga
la promessa di uscire a settembre con una produzioncina di cosi
vari, beh... spero di non aver detto il settembre di quale anno,
perche' sono decisamente in alto mare.  :o(

 la promessa di uscire a settembre con una produzioncina 
Non so che tipo di produzione devi fare, ma attendo con fiducia,
perche' l'argomento pentamini mi attira un sacco, da tanti anni :-)
Ciao!
Carlo