Gara a squadre di Roma-Parole di sole vocali

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Gara a squadre di Roma-Parole di sole vocali

Messaggio da dario2994 » 27 mar 2009, 20:55

Alur alla gara a squadre di Roma c'era un esercizio che non sono riuscito a risolvere e non ho idea di come si faccia... Vi scrivo qui il testo provate voi e spiegatemi come fare...
"Quante parole di 8 lettere si possono fare usando solo le 5 vocali in modo che siano in ordine alfabetico???"

Teoricamente doveva essere un esercizio "facile"...

Alex90
Messaggi: 260
Iscritto il: 25 mag 2007, 13:49
Località: Perugia

Messaggio da Alex90 » 27 mar 2009, 21:15

Allora, premetto che credo consideriamo il caso in cui tutte le vocali sono presenti almeno una volta, quindi dal momento che abbiamo 5 vocali da mettere in ordine alfabetico avremo uno schema del tipo:

$ \alpha a \quad \beta e \quad \gamma i \quad \delta o \quad \varepsilon u $

dove $ \alpha, \beta... $ indicano quante volte è presente quella vocale

Ora abbiamo vari casi:

1) una vocale è ripetuta 4 volte e le altre 1 da cui $ \displaystyle {5 \choose 1} $ cioè $ 5 $ casi

2) una vocale ripetuta 3 volte, una 2 e le altre 1 da cui $ \displaystyle {5 \choose 1}\cdot{4 \choose 1} $ cioè $ 20 $ casi

3) tre vocali ripetute 2 volte e 2 una volta, in questo caso si hanno $ \displaystyle {5 \choose 1}\cdot{4 \choose 1}\cdot{3 \choose 1} $ cioè 60 possibilità

La risposta credo pertanto che sia $ 5+20+60=85 $

ripeto, se è possibile che alcune vocali non siano presenti, vanno considerati altri casi...

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco » 27 mar 2009, 23:15

Anch'io premetto le stesse condizioni di alex90, cioè consideriamo il caso in cui tutte le vocali sono presenti almeno una volta.
sono d'accordo sul primo e sul secondo caso di alex90.
sul terzo però sono in disaccordo:
scegliere tre vocali ripetute 2 volte e 2 una sola volta, equivale a dire: scegliere le 2 vocali ripetute una sola volta, e cioè (5 su 2) = 10 casi possibili.
nel secondo caso si è potuto fare (5 su 1) per (4 su 1), poichè erano due cose distinte, cioè scegliere la lettera fra le 5 ripetuta 3 volte, e scegliere la lettera fra le restanti 4 ripetuta 2 volte (o il contrario), ma nel terzo caso le 3 lettere vengono ripetute tutte 2 volte; d'altronde i vari casi possibili sono:
(a=1...e=2...i=3...o=4...u=5)
11223345
11223445
11223455
11233445
11233455
11234455
12233445
12233455
12234455
12334455
e mi sembra non ce ne siano altri.
quindi la soluzione dovrebbe essere:
5+20+10=35 casi possibili

fph
Site Admin
Messaggi: 3662
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 27 mar 2009, 23:51

Se ci si mette a dividere in casi si impazzisce abbastanza in fretta (ok, magari non con 8 lettere e 5 vocali, ma con 2009 lettere e 9002 vocali sì). Pensatela così: le scelte da fare sono solo quattro: in che posizione smetto di avere a e passo alle e? In che posizione smetto di avere e e passo alle i? e così via. In quanti posti diversi potete mettere ognuna di queste "transizioni"?
E, poi, controllino "sanity check": "generando" in questo modo le parole, le state generando tutte? Le state generando tutte una volta sola? Se no, come potete correggere il conteggio?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

pak-man
Messaggi: 313
Iscritto il: 07 giu 2008, 18:19

Messaggio da pak-man » 28 mar 2009, 00:44

Se non è necessario che ogni vocale compaia almeno una volta, una stringa di $ n $ vocali in ordine alfabetico si può scrivere in $ \displaystyle{n+4\choose4} $ modi (cioè il numero di modi di piazzare 4 separatori in n+4 caselle).

Se invece devono comparire tutte, allora credo che si possa usare il principio di inclusione-esclusione per un conteggio esatto di tutte le possibilità:
$ \displaystyle{n+4\choose4}=(n+4)(n+3)(n+2)(n+1)/24 $ stringhe totali
$ \displaystyle-{5\choose4}{n+3\choose3}=-5(n+3)(n+2)(n+1)/6 $ stringhe che contengono al massimo 4 vocali
$ \displaystyle+{5\choose3}{n+2\choose2}=+10(n+2)(n+1)/2 $ stringhe che contengono al massimo 3 vocali
$ \displaystyle-{5\choose2}{n+1\choose1}=-10(n+1) $ stringhe che contengono al massimo 2 vocali
$ \displaystyle+{5\choose1}{n+0\choose0}=+5 $ stringhe che contengono 1 vocale

Totale $ \displaystyle\frac{1}{24}(n-4)(n-3)(n-2)(n-1) $

La formula funziona per n=5 :wink:, e per n=8 la soluzione coincide con quella di iademarco (35)...spero solo che sia giusta!

Alex90
Messaggi: 260
Iscritto il: 25 mag 2007, 13:49
Località: Perugia

Messaggio da Alex90 » 28 mar 2009, 13:38

ha assolutamente ragione iademarco...si vede che era quasi ora di cena mentre scrivevo il tezro punto! :lol:

fph
Site Admin
Messaggi: 3662
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 28 mar 2009, 19:10

pak-man ha scritto:Se non è necessario che ogni vocale compaia almeno una volta, una stringa di $ n $ vocali in ordine alfabetico si può scrivere in $ \displaystyle{n+4\choose4} $ modi (cioè il numero di modi di piazzare 4 separatori in n+4 caselle).

Se invece devono comparire tutte, allora credo che si possa usare il principio di inclusione-esclusione
Soluzione giusta, ma anche nel caso in cui ogni vocale compare almeno una volta, si riesce a scrivere una formula chiusa senza bisogno di sommare parecchi termini. Hint ma che ti lascia ancora l'idea "grossa" da trovare: il ragionamento che devi fare è simile a quello di "piazzare i separatori" che hai già fatto, ma come si può adattare all'altro caso?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

pak-man
Messaggi: 313
Iscritto il: 07 giu 2008, 18:19

Messaggio da pak-man » 28 mar 2009, 19:47

Effettivamente il secondo metodo è troppo contoso, forse ho capito come farlo meglio: dato che ci vuole almeno una vocale per tipo, da n lettere ne prendiamo n-5, aggiungiamo 4 spazi e piazziamo i separatori, che a questo punto possono anche essere ai lati o vicini ché tanto le lettere "escluse" compaiono già dall'esclusione fatta in precedenza.
Quindi i modi sono
$ ${n-5+4\choose4}={n-1\choose4}=\frac{1}{24}(n-1)(n-2)(n-3)(n-4) $
esattamente come nel risultato precedente, ma con meno conti di mezzo

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 28 mar 2009, 20:06

Alur... voglio solo dire che le vocali non devono affatto comparire tutte ;)
E non ho capito la soluzione di pakman...

pak-man
Messaggi: 313
Iscritto il: 07 giu 2008, 18:19

Messaggio da pak-man » 28 mar 2009, 20:47

Cercherò di essere il più chiaro possibile al primo colpo:
-devi piazzare n vocali in ordine alfabetico in una stringa di lunghezza n
-allunghi la stringa di 4 elementi (totale n+4), e oltre alle vocali ora devi inserire 4 'x'
-quanti sono i modi di mettere 4 'x' in n+4 spazi? $ {n+4\choose4} $
-ora a sinistra della prima 'x' metti tutte 'a', a sinistra della seconda tutte 'e', ..., a destra dell'ultima tutte 'u'
-se prima di una 'x' non c'è alcuno spazio (perché la 'x' è il primo carattere o perché ci sono almeno 2 'x' vicine) la vocale corrispondente non va messa (quindi non compare nella stringa)
-fatto: abbiamo contato in questo modo tutte le combinazioni di n vocali in ordine alfabetico, e sono tutti i modi di mettere 4 separatori tra le vocali, ovvero 4 separatori in n+4 spazi

P.S.: è lo stesso metodo che si usa per trovare i modi di scrivere un intero 'm' come somma di h interi non-negativi. Si prende una serie di m+h-1 elementi di cui h-1 sono segni '+', gli altri sono unità: ogni gruppo di unità compreso tra due segni '+' è uno degli h addendi

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 28 mar 2009, 21:08

Perfetto ho capito in pieno ;)
Ma a questo punto... dato che l'hai tirato in ballo ti propongo lo stesso problema detto da te... ma senza l'ordine:
"Trovare tutte le terne (x,y,z) Di numeri naturali tali che x+y+z=n con N naturale. Due terne sono considerate uguali se hanno gli stessi valori anche se in ordine diverso. Dato che una generalizzazione così è troppo difficile vi propongo una generalizzazione solo per i numeri divisibili per 3 ma non per 2... la formula è estremamente semplice in questo caso ;) In ultimo vi propongo questo quesito assumendo N=200... questo era una delle domande della gara a squadre di Roma ;)"
Divertitevi.

Avatar utente
gismondo
Messaggi: 84
Iscritto il: 05 feb 2009, 18:42
Località: Roma

Messaggio da gismondo » 29 mar 2009, 01:07

Bè quello per n=200 si può usare il binomiale:
$ {n+k-1 \choose k} $
dove k=200 n=3
Questo restituisce tutti i modi considerando l'ordine...ora togliamo le combinazioni con due numeri uguali che sono in tutto 101*3 (0,0,200-1,1,198 ecc. la moltiplicazione per 3 è il numero di posti in cui può stare in numero non uguale)

Si ottiene 19998, che dividiamo per 3! (il numero di permutazioni dei tre elementi)
Otteniamo 3333, a cui aggiungiamo di nuovo 101 per riconsiderare le combinazioni tolte precedentemente : 3434
"Per tre cose vale la pena di vivere: la matematica, la musica e l'amore"

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 29 mar 2009, 09:18

La soluzione per 200 è perfetta e anche ben più semplice della mia xD
Vorrei capire perchè sono sempre l'unico cretino che non usa i binomiali xD
Io per risolvere ho usato una sommatoria assumendo il numero minore da 0 a 66 e guardando in quanti modi si possono disporre gli altri... il risultato è lo stesso.
Se a qualcuno va fate il caso generale ;)

fph
Site Admin
Messaggi: 3662
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 29 mar 2009, 12:24

dario2994 ha scritto:"Trovare tutte le terne (x,y,z) Di numeri naturali tali che x+y+z=n con N naturale. Due terne sono considerate uguali se hanno gli stessi valori anche se in ordine diverso. Dato che una generalizzazione così è troppo difficile
Esatto, per queste non esiste una formula chiusa. :shock:
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 29 mar 2009, 13:59

bhe dipende da cosa intendi per formula chiusa... io dividendo in solo 3 casi ho trovato le formule chiuse... e non penso di essere un eminente scienziato che ha appena fatto la scoperta del secolo ;) Quindi provaci ;)
p.s. per formula chiuse intendo una formula che fa uso solo delle operazioni algebriche più il simbolo parte intera [N] che restituisce la parte intera di un numero

Rispondi