Newsgroup: it.hobby.enigmi
Titolo: Caramelle

Ho 3 caramelle alla menta, 3 al limone e 3 all'arancio.
Mi chiedo in quanti modi posso mangiarmi le 9 caramelle una dopo l'altra
senza che due consecutive abbiano lo stesso gusto.
Esiste una generalizzazione per Car(g,n) ?? (Per ogni gusto g ci sono n
pezzi).
Il caso in questione e' naturalmente Car(3,3).
:)dario

Il caso in questione e' naturalmente Car(3,3).
Il metodo che ho usato per Car(3,3) e' completamente inutile per un
tentativo di genralizzazione.
Non essendo riuscito nell'approccio analitico, ecco pronta la soluzione
algoritmica. Come temevo il problema "esplode" in maniera rapidissima, per
cui ho riempito una tabellina molto lacunosa, sulla quale sto lavorando.
Eccola:
\   n=1        2      3        4     5      6       7        8
g\------------------------------------------------------------
2|    2        2      2        .
3|    6       30    174     1092  7188  48852  339720  2403588
4|   24      864  41304  2265024
5|  120    39480
6|  
720  2631600
7| 5040
.|
n|   n!
A parte i casi banali Car(g,1)=g! e Car(2,n)=2 non so proprio come fanno ad
uscire fuori questi dati.
Ciao, Silv:o)

senza che due consecutive abbiano lo stesso gusto.
Mi sono tornate in mente quelle orrende collanine fatte con anelli di
zucchero (e chissa' quali atre schifezze...) colorati, che si vendevano
(forse si trovano ancora) nelle bancarelle delle fiere.
Il problema e' simile:
In quanti modi posso costruire una collana con 3 caramelle rosse, 3 verdi e
tre blu, senza mai avere due caramelle dello stesso (dis)gusto vicine?
Chissa' che non si riesca a generalizzare a Col(g,n)
Ciao, Silv:o)

 n|   n!
Cacchio Silvio ! 
I dati sono tutti esatti. Corrispondono a quelli dati da Schwartz autore
del problema.
Io ho sputato sangue solo per trovare 174.
Rapido e preciso come sempre.
ciao :)dario

 uscire fuori questi dati.
Oddio, un idea ce l'avrei.
Qual e ' la probabilita' che, formando la sequenza di caramelle a caso, due
prefissate siano dello stesso gusto? Io direi q=(n-1)/(g*n-1), che siano
esse
consecutive o no.
Se le scelte fossero indipendenti, allora potremmo calcolare la probabilita'
che in una sequenza di g*n non ci siano mai due ripetizioni, e questa
varrebbe p=(1-q)^(g*n-1). Ma le caramelle mangiate influiscono sulle scelte
successive, per cui la formula non e' esatta.
Peccato, perche' moltiplicandola per il numero di possibili sequenze
otterrei le sequenze senza ripetizioni. Ci voglio provare lo stesso. I
possibili modi di permutare g gruppi di n simboli sono (g*n)!/(n!)^g.
Moltiplicando per p ho ottenuto risultati sorprendentemente vicini a quelli
esatti!
Per esempio,
Car(3,3)=168,18  (174)
Car(3,4)=1043,21 (1092)
Car(4,3)=40651,8 (41304)
Cosi' posso azzardare previsioni per configurazioni che sono altrimenti
intrattabili:
Car (10,10)=1,88E88
Ciao, Silv:o)

Chissa' che non si riesca a generalizzare a Col(g,n)
Una generalizzazione mi pare poco probabile, comunque per Col(3,3) ho
ottenuto questi risultati, partendo dalle 174 sequenze del problema
originale.
1) Prima di tutto ho formato le collane controllando quali delle sequenze
avessero il primo e l'ultimo gusto uguali (mica a mano, ho aggiunto un
if...)
col(3,3)=132 - Solo 42 sequenze scartate, 14 per colore iniziale. Pochine,
ma c'era da aspettarselo: le 7 caramelle centrali (3+3+1) hanno poche
possibilita' di evitare ripetizioni di gusto.
2) Poi ho pensato di scartare quelle sequenze che mostrassero lo stesso
ordine ciclico dei gusti (se non consideriamo il fermaglio, le collane sono
indistinguibili)
col(3,3)=16 - Grossa scremata, mi aspettavo qualche superstite in piu'.
3) Per ultimo ho provato a considerare uguali due collane speculari, perche'
se ne giro una non la distinguo dall'altra.
col(3,3)=8 - La meta': la simmetria non e' un opinione.
Ecco le collane rimaste:
 r v r      r v r      r v r      r v r
b     v    b     v    b     b    b     b
v     b    r     b    v     r    v     v
  b r        b v        b v        b r
 r v b      r v b      r v b      r v b
b     r    v     r    b     r    v     r
v     v    b     v    r     v    b     b
  r b        r b        v b        v r
Qualche altro valore (tra parentesi Car(g,n) del problema di Dario):
Col(4,2)= 54  ( 864)
Col(3,4)= 41  (1092)
Col(3,5)=174  (7188)
Ciao, Silv:o)

 Col(3,5)=174  (7188)
Notevole! un ottimo lavoro.
ciao :)dario

 Ciao, Silv:o)

... in totale 138 combinazioni... vi torna?
132
Ciao, Silv:o)