Newsgroup: it.hobby.enigmi
Titolo: [POLIFORME] - Pentamini Probabilistici

Ciao a tutti,
 
colpevole del lunghissimo silenzio sul gruppo provo a farmi perdonare con un problema sui Pentamini che nel passato tante soddisfazioni hanno portato ai partecipanti a questo gruppo.
 
 
Cominciamo con un monomino (insomma, un quadrato) ed aggiungiamo un secondo quadrato su uno a caso dei 4 lati disponibili. In questo caso avremo ovviamente sempre un domino. Adesso aggiungiamo un terzo quadrato su uno a caso dei 6 lati possibili per ottenere un tri-mino.
 
Aggiungiamo un 4° quadrato e poi un 5° quadrato sempre a caso su uno dei possibili lati della figura ottenuta nello step precedente. Abbiamo adesso ottenuto un pentamino: qual è il pentamino più probabile che potremmo ottenere con un simile procedimento? ed il meno probabile?
 
Un saluto
GaS

 potremmo ottenere con un simile procedimento? ed il meno probabile?
 
Senti, ma in che ambiente siamo? Mi spiego.
Questo:
* * *
*
 
e' indistinguibile o no da quest'altro:
* * *
    *
 
Cioe', ed e' la stessa cosa, siamo sul piano o sono cubetti fisici da
attaccare, che posso girare da tutte le parti come mi pare?
 
Cumunque sia, e' solo un po' laborioso, non difficile - mi sembra, o no?
 
-- 
Tanti saluti
 

     *
 
Penso che dovrebbero essere considerati differenti, i 4-mini se non
ricordo male sono gli elementi di Tetris, dunque siamo sul piano.
 
Le probabilita' sembra, come ho gia' detto ieri, semplice anche se
lungo, con piu' tempo si trovano tutti i 5-mini, per i 4-mini mi
risulta:
 
# # # #  a = 1/12
 
 
# # #    b = 2/12
#
 
 
# # #    c = 2/12
    #
 
 
# # #    d = 3/12
  #
 
 
# #      e = 2/12
# #
 
 
# #      f = 1/12
  # #
 
 
  # #    g = 1/12
# #
 
 
-- 
Tanti saluti
 

 che potremmo ottenere con un simile procedimento? ed il meno probabile?
 
A me viene questa tabella, da cui si vede che il P vince largamente:
 
          2        4        3       2       1        (su 12)
          ##      #         #       ##
          ##      ###      ###     ##      ####
 
 ##
 ###      8        2        4       4                     44
 
 #
 ####              1                        4              8
 
 # #
 ###               1                                       4
 
 #
 ###               1                                       4
   #
 #                 
####               1        2               4             14
 
##
 ###               1                2                      8
 
 #
###                         1                              3
 #
 
#####                                       2              2
 
#
#                  1                                       4
###                                                       
 
#
###                1        1                              7
#
 
  #
###                1        2       2                     14
 #
 
#
##                                  2                     14
 ##
-------------------------------------------------------------
         8        10       10      10       10           116
 
M.
 
-- 
Per rispondermi via e-mail togli l'ovvio.

 # #
 
E' piu' veloce del previsto e l'ho provato a fare, ho visto ora che
Maurizio considera: b=c; f=g. Ecco come viene a me:
 
TIPO       PADRI        PROBABILITA' in centoventesimi
 
m m m m m  2a            2
 
m m m m    2a+b          4
m
 
m m m m    2a+b+d        7
  m
 
m m m m    2a+c+d        7
    m
 
m m m m    2a+c          4
      m
 
m m m      2b+2d+5e+4g  24
m m
 
m m m      b+c           4
m   m
 
m m m      2c+2d+5e+4f  24
  m m
 
m
m m m      b+c+d         7
m
 
    m
m m m      b+d+2f        7
  m
 
    m
m m m      b             2
m
 
m
m m m      c+d+2g        7
  m
 
  m
m m m      d             3
  m
 
m
m m m      c             2
    m
 
m m m      b+c           4
m
m
 
m m m      c+2f          4
    m m
 
  m m m    b+2g          4
m m
 
m
m m        2f+2g         4
  m m
 
Dunque sono in 3 i meno probabili e 2 invece i piu', con probabilita'
rispettuvamente di 1,(6)% e 20%.
 
 
-- 
Tanti saluti
 

 
"GaS" ha scritto

A me viene così:
 
      P 25,10%
      F 15,58%
      Y 14,15%
      N 8,73%
      T 7,39%
      L 7,30%
      W 4,76%
      U 3,97%
      V 3,97%
      Z 3,97%
      X 3,42%
      I 1,67%
 
      Totale 100,00%
 
 
Ciao
Gianni 
 


I tuoi risultati sono uguali ai miei, tranne che per i due pentamini che
hanno la probabilità maggiore (e che di solito vengono considerati lo
stesso pentamino, indicato in modo abbreviato con P). 
 
A me sembra che il tetramino quadrato (il tuo caso "e") abbia solo 8
lati di contorno, e non 10 come gli altri. Quindi non capisco perché nel
tuo calcolo per i due pentamini P tu consideri 5e + 5e, mentre il
risultato corretto dovrebbe essere 4e + 4e, ovvero tutti gli 8 lati del
tetramino quadrato danno quel pentamino quando gli si appiccica un
quadretto nuovo.
 
Con questa correzione i casi totali sono 116 (anziché 120) e la
probabilità del pentamino P sarebbe dunque 44/116 = 37,93%. Quello che
mi preoccupa è che il risultato è completamente diverso da quello di
Gianni...


       Totale 100,00%
 
E mi sa che hai visto giusto tu, perche' con le probbilita' io son
partito dai 3-mini, invece forse bisogna partire dal singolo quadrato, o
meglio, dal'unico 2-mino esistente. Comunque la correzione e' immediata,
poi magari la guardo.
 
-- 
Tanti saluti
 

 Gianni...
 
Bisogna provare a innestare la probabilita' 2-mini -> 3-mini, come ho
appena scritto a Guido, oppure se ci legge ce lo dice.
 
-- 
Tanti saluti
 

 meglio, dal'unico 2-mino esistente.
 
Non ho fatto i conti, ma ho il sospetto che la differenza sia dovuta a
come si contano i casi in cui due lati diversi portano alla stesso
polimino.  Per esempio aggiungere un quadratino nel "buco" del trimino
L per ottenere un tetramino Q conta una volta sola (con prob. 1/7) o una
per ognuno dei due lati che si affacciano al "buco" (prob. 2/8)?
 
ciao,
Mauro

 invece c'e' un solo 2-mino) come penso abbia fatto Gianni (vedi fine).
 
Ma no, vedo ora che l'avevamo considerata, quindi semplicemente il fatto
e' che troviamo risultati diversi.
 
In rete ho visto anche la storia dei nomi e la storia che non li si
ritiene differenti (wikipedia), per cui ho aggiornato i conti sommando
i casi uguali. Ecco i miei risultati.
 
TIPO      /120 NOME  PROBABILITA'
 
m m m m m   2    I:  1,(6)%     <== Min assoluto
 
m m m m     8    L:  6,(6)%
m
 
m m m m    14    Y: 11,(6)%
  m
 
m m m      48    P: 40,(0)%     <== Max assoluto
m m
 
m m m       4    U:  3,(3)%
m   m
 
m m m       8    N:  6,(6)%
    m m
 
m
m m m       7    T:  5,9(3)%
m
 
    m
m m m      14    F: 11,(6)%
  m
 
    m
m m m       4    Z:  3,(3)%
m
 
  m
m m m       3    X:  2,5(0)%
  m
 
m
m           4    V:  3,(3)%
m m m
 
m
m m         4    W:  3,(3)%
  m m
         -------    -------
          120      100,(0)%
 
 
Commentino mio: E, come sempre, il max e' in corrispondenza della piu'
bilanciata e il min della piu' sbilanciata.
 
 
P.S. (in particolare per Maurizio). "Virgola zero periodo" non si usa
per dire che un risultato e' esatto?
 
-- 
Tanti saluti
 

 per ognuno dei due lati che si affacciano al "buco" (prob. 2/8)?
 
Su questo ci ho pensato a lungo (piu' di 3 minuti), e anzi e' proprio
per questa curiosita' che ho cominciato a risolvere il quiz di GaS.
Al riguardo ho pensato quanto segue.
 
Per le probabilita' occorre sempre precisare la procedura operativa al
riguardo del problema da risolvere. Per questo problema qui, secondo me,
puo' essere una buona idea pensare a tutti i cinque (io ne avevo 7
perche' pensavo a Tetris) 4-mini messi su un biliardo e alla
possibilita' di gettare palline che abbiano ugual probabilita' di
colpire (per la prima volta) ogni lato di ognuno dei 4-mini.
 
Di qui allora risulta che 4-L  ->  5-P vale 2, perche' lo genera l'urto
della pallina che va a Nord e di quella che va a Ovest.
 
All'inizio, prima di pensare alla necessita' d'una procedura operativa,
ero un po' perplesso, perche' dicevo: E' vero che i lati sono 2, pero'
e' anche vero che, come scelta, io non posso mai sceglierne uno senza
l'altro; e allora mi domandavo se non valesse una scelta sola.
 
-- 
Tanti saluti
 

 avere 120 a denominatore comune, cioe' 2/12 * 5/10.
 
Hai ragione, mi ero sbagliato io. 
 
Quanto al calcolo di Gianni, credo che abbia ragione Mauro: se ad
esempio faccio una simulazione Monte-Carlo, in cui i quadratini cadono
"a pioggia" su una griglia, le probabilità vengono sbagliate, perché non
tutti i quadratini hanno la stessa probabilità. Infatti la procedura di
costruzione, così come descritta da GaS, implica che l'equiprobabilità
si deve avere rispetto ai lati del polimino, perciò un quadretto che
confina con due lati dovrebbe essere contato per due.


 per dire che un risultato e' esatto?
 
Mah, forse è meglio usare le frazioni.


 confina con due lati dovrebbe essere contato per due.
 
Ho provato adesso a fare una simulazione in cui appunto dò un peso
diverso ai quadretti a seconda del numero di lati con cui confinano.
Incredibile ma vero: il risultato è esattamente quello riportato da
Gianni!!
 
Dov'è lo sbaglio?


 confina con due lati dovrebbe essere contato per due.
 
Si', anche secondo me bisogna parlare di posti possibili e non di lati.
La cosa migliore e' descrivere, esempio:
 
A) PROBLEMA basato sui posti-griglia.
Pioggia ortogonale al piano della griglia, ad esempio 4-L -> 5
  O O O
O * * * O
O * O O
  O
(e adesso i posti sono 9 e non 10).
 
B) PROBLEMA basato sui lati.
Lancio palline che rotolano sul piano dei 4-mini verso:
  Nord     Ovest     Sud       Est
  * * *    * * *|    _ _ _    |* * *
  * - -    *|        * * *    |*
  -                  *
(con evidenti 10 lati-bersaglio).
 
-- 
Tanti saluti
 

 Mah, forse è meglio usare le frazioni.
 
Gia', infatti non l'ho mai visto neppure una volta... va be', avrei
potuto, meglio, scriverci accanto "esatta".
 
-- 
Tanti saluti
 

Addi' 17 ott 2014, Maurizio Frigeni scrive:

Be' penso necessariamente nella scelta del peso -- (C) by Lapalisse.
 
Il fatto che siamo andati in una brutta strada (con la storia dei lati)
lo capisco adesso, da 5-U verso esamini il mio criterio del lancio di
palline non puo' piu' andare: li' il quadrato interno all'U puo' essere
colpito solo frontalmente.
Sarebbe ora che GaS uscisse dall'ombra.
 
P.S. Pero', se scegli la pioggia, non devi mettere pesi! Hai provato?
 
-- 
Tanti saluti
 

 (e adesso i posti sono 9 e non 10).
 
La simulazione che avevo fatto funzionava proprio così, solo che quando
la scelta casuale capitava sul quadratino che confina con due lati io
gli assegnavo peso 2, come se lo avessi estratto due volte.
 
A naso pensavo che funzionasse, invece come dicevo dà i risultati
sbagliati.
 
Allora ho fatto poco fa un'altra simulazione Montecarlo, stavolta
tenendo una lista dei segmenti al bordo ed estraendo a caso fra questi:
il risultato è in perfetto accordo con le probablità che hai calcolato
tu.


 Sarebbe ora che GaS uscisse dall'ombra.
 
 
Eccomi, eccomi... Scsuate ma da un gruppo quasi silente non mi aspettavo tante risposte in 48h :-)
 
Prima di tutto confermo, ormai in ritardo ma meglio di niente, che considero indistiunguibili i polimini R&R, quindi abbiamo 5 tetramini e 12 pentamini, non l'ho specificato ma dopo tanti anni lo davo per scontato, sorry
 
In effetti, come spesso accade con le probabilità, dipende da come intendiamo lo "scegliere a caso":
 A - scegliamo un quadrato libero adiacente a caso?
 B - scegliamo un lato libero e ci appiccichiamo un nuovo quadrato?
 
(mantengo la classificazione data da Yoda tra A e B)
 
Con il testo avevo provato ad indirizzare la versione "B" proprio perchè più semplice (o almeno con numeri manegevoli) ma anche il caso A è di interesse ed è il primo che avevo risolto.
 
Per il caso A confermo assolutamente, se ma ce ne fosse bisogno, la soluzione di Giovanni (Ciao!)
 
Per il caso B confermo invece la soluzione di Yoda di oggi alle 15:20
 
Per riassumere:
 
	  A	  B
F	15,58%	11,67%
L	7,30%	6,67%
I	1,67%	1,67%
P	25,10%	40,00%
N	8,73%	6,67%
T	7,39%	5,83%
U	3,97%	3,33%
V	3,97%	3,33%
W	4,76%	3,33%
X	3,42%	2,50%
Y	14,15%	11,67%
Z	3,97%	3,33%
 
Interessante che ordinando per A o per B l'ordine di probabilità rimane quasi invariata a meno di "pari merito" e dell'inversione di probabilità per la L e la T:
 
A			B
1,67%	I	I	1,67%
3,42%	X	X	2,50%
3,97%	U	U	3,33%
3,97%	V	V	3,33%
3,97%	Z	Z	3,33%
4,76%	W	W	3,33%
7,30%	L	T	5,83%
7,39%	T	L	6,67%
8,73%	N	N	6,67%
14,15%	Y	Y	11,67%
15,58%	F	F	11,67%
25,10%	P	P	40,00%
 
 
Per il momento non mi sono azzardato a calcolare gli esamini ma mi piacerebbe individuare una regola almeno per qualche classe di polimini.
 
I più facili sono ovviamente gli n-mini I (cioè con tutti gli n quadrati in fila) che hanno una probabilità di 2/n! e sarà sempre il meno probabile.
 
Ho provato poi a tirare fuori la probabilità per l-nmino L (cioè tutti i quadrati in fila tranne uno ad uno delle estremità) e mi viene la seguente formula ricorsiva:
 
P(n)=1/n!+P(n-1)/N
 
Ho provato a risolverla e mi viene la seguente per n>4:
 
P(n)=(4n-12)/n!
 
qualcuno può confermare? (ovviamente funziona per n=5 :-)
 
Un saluto a tutti e ben ritrovati!
GaS
 

 M.
 
Ritengo che in quel caso si debba contare per uno. Non credo che in una 
aggiunta casuale le probabilità di aggiungere un quadratino proprio lì sia 
il doppio di qualunque altro posto.
Le probabilità sono quindi 1 su 7 per ciascuna posizione e di questo bisogna 
tener conto nei calcoli.
 
Ciao
Gianni 
 

 qualcuno può confermare? (ovviamente funziona per n=5 :-)
 
Ho scordato di dire che le probabilità le sto calcolando nel caso più manegevole e cioè nel B (anche se per l'n-mino I le probabilità non cambiano tra caso A e B).
 
Trovato l'n-mino ad L viene facile ricavare anche l'n-mino Z del tipo:
 
OO
 O
 O
 .
 .
 .
 O
 O
 OO
 
che, detto n il generico l'ordine e per n>5, ha una probabilita'
 
P(n)=(2n-8)/n!
 
ciao
GaS

 P(n)=(2n-8)/n!
 
Si', puo' dare soddisfazione trovare le formule generali, pero' ci vuole
parecchio tempo e soprattutto concentrazione.
 
-- 
Tanti saluti
 

 Allora ho fatto poco fa un'altra simulazione Montecarlo, stavolta
 
Prima o poi bisogna ch'io mi decida a guardare-imparare un programma per
simulazioni sotto Linux, le fate tutti con gran disinvoltura!
 
-- 
Tanti saluti
 

 piacerebbe individuare una >regola almeno per qualche classe di polimini.
 
Ecco i calcoli per gli esamini.
Ovviamente i calcoli sono in base all'aggiunta casuale nei posti disponibili 
(classificazione A di Yoda, l'altra mi sembra poco in sintonia con i 
problemi relativi alle poliforme)
 
 
      O O O    8,79%
      O O
      + O
 
      O O     6,37%
      O O O
      + + O
 
      O O     6,23%
      O O O
      + O
 
      O O O O   5,74%
      O O
 
      O O O O   4,20%
      + O O
 
      + O     4,08%
      + O O O
      O O
 
      + O     3,87%
      O O O O
      + O
 
      + O     3,81%
      O O O O
      O
 
      O O O    3,68%
      O O
      O
 
      + O O O   3,66%
      O O O
 
      + + O    3,66%
      + O O O
      O O
 
      O O O O   3,61%
      + O
      + O
 
      + O O O   3,33%
      O O
      + O
 
      O O O    3,19%
      O O O
 
      + + O    3,15%
      O O O O
      + O
 
      O O O    3,07%
      + O
      O O
 
      O O O O   2,87%
      O + O
 
      + + O    2,87%
      O O O O
      O
 
      O O O O O  2,63%
      + O
 
      O O     2,13%
      + O O
      O O
 
      + O O O   1,93%
      O O
      O
 
      O O O O O  1,69%
      + + O
 
      + + + O   1,67%
      + O O O
      O O
 
      + O O O   1,67%
      O O + O
 
      + O O O O  1,54%
      O O
 
      O O O    1,52%
      O
      O O
 
      + O O O   1,52%
      + O
      O O
 
      O      1,40%
      O O O O
      O
 
      O O O O   1,39%
      O
      O
 
      O O O O O  1,22%
      O
 
      + + O O   1,06%
      + O O
      O O
 
      + + O O O  0,87%
      O O O
 
      + + + O   0,66%
      O O O O
      O
 
      O O O O   0,66%
      O + + O
 
      O O O O O O 0,28%
 
 
          100,00%
 
Ciao
Gianni
 
 
 

 problemi relativi alle poliforme)
 
Non essere così drastico, suvvia... Io ho provato a vedere qual è
l'esamino che vince nel caso B di GaS, ma senza fare un calcolo
esaustivo come il tuo.
 
Siccome fra i pentamini ce ne sono tre che hanno una probabilità di
nascere decisamente superiore agli altri:
 
P: 48/120,  Y: 14/120, F: 14/120
 
sono andato a vedere quali esamini possono nascere da questi.
 
Quello che parte favorito è il tuo vincente:
 
O O O   
O O      p = 2/10*2/5 + 2/12*7/60 = 179/1800
+ O
 
che si può ottenere in 2 modi da P e in 2 modi da F (P ha 10 lati,
mentre Y e F ne hanno 12). Ma ce ne sono altri 4 che gli arrivano
vicini:
 
O O O    p = 2/10*2/5 = 144/1800
O O O
 
O O
O O O    p = 1/10*2/5 + 2/12*7/60 = 107/1800
+ + O
 
O O
O O O    p = 1/10*2/5 + 2/12*7/60 = 107/1800
+ O
 
O O O O  p = 1/10*2/5 + 2/12*7/60 = 107/1800
O O
 
O O O O  p = 1/10*2/5 + 2/12*7/60 = 107/1800
+ O O
 
Per completare il quadro, sono andato a vedere quali altri pentamini
possono produrre uno di questi sei esamini. Il primo può nascere anche
dal T, con prob. 4/12 * 7/120 = 7/360, il secondo può nascere anche
dall'U, con prob. 3/12 * 4/120 = 1/120, il terzo può nascere anche da Z
e W, con una prob. di 1/45, il quarto può nascere anche dall'X, con
prob. di 1/60, il quinto può nascere anche da L e V, con una prob.
complessiva di 1/60 (sperando di non aver sbagliato i calcoli), mentre
il sesto non può nascere da altri pentamini.
 
Sommando queste alle probabilità precedenti si trova il risultato
finale:
 
O O O   
O O      p = 179/1800 + 7/360 = 214/1800
+ O
 
O O O    p = 144/1800 + 1/120 = 159/1800
O O O
 
O O
O O O    p = 107/1800 + 1/45  = 147/1800
+ + O
 
O O
O O O    p = 107/1800 + 1/60  = 137/1800
+ O
 
O O O O  p = 107/1800 + 1/60  = 137/1800
O O
 
O O O O  p = 107/1800
+ O O
 
Secondo me questi sono gli esamini più probabili nello schema B.
Rispetto allo schema A si nota una grande rimonta del rettangolo, che
arriva secondo.


Che bel problema, GaS! Complimenti. Saluti a tutti!
Livio

 parecchio tempo e soprattutto concentrazione.
 
Si concentrazione che non ho avuto io... :-(
 
Riassumendo:
 
I(n)=2/n!
L(n)=8/n!
Z(n)=4/n!  [viene facile dalla L(n)]
 
Bello :-)
 
Ciao
GaS

           100,00%
 
 
Ciao Gianni,
sempre in forma è?
 
Calcolate tutte a mano?
Concordo sul fatto che il caso A sia "più in sintonia con i problemi relativi alle poliforme", però il caso B porta con se delle interessanti generalizzazioni difficili da avere nel caso A (tranne ovviamente che per l'I n-mino che ha sempre le stesse probabilità).
 
Un saluto
GaS

l'I n-mino che ha sempre le stesse probabilit�).
 
La difficolt� di generalizzazioni per tutti i problemi relativi ai 
poliqualchecosa � sempre stata quella che le caselle per le aggiunte sono in 
numero diverso tra le poliforme dello stesso ordine e che le possibili 
aggiunte tendono ad aumentare in modo quasi esponenziale all'aumentare 
dell'ordine.
Tale problema � cmq presente anche nel caso B, seppure in forma meno marcata 
(il tetra quadrato ha solo 8 possibili aggiunte).
 
Ciao
Gianni