Problema delle olimpiadi Archimede di quest'anno

[Willy67]

Carla si è dimenticata la password di accensione del suo nuovissimo computer! Si ricorda però che è una sequenza di 4 vocali, non necessariamente distinte, di cui due sono maiuscole e due sono minuscole. Quante password diverse deve provare Carla, al massimo, per accendere il computer?

Modulo = Coppia di vocali

Siccome vi devono essere una coppia di vocali maiuscole ed una di vocali minuscole si considerino moduli unici come se fossero lettere uniche tutte le coppie di lettere maiuscole e minuscole - -> (A,a)(A,e) (A,i)(A,o)(A,u)(E,a)(E,e)....(a,A)(a,E).. = 5 con a capo la lettere A maiuscola + 5 con la B+... = 5(5)maiuscole +5(5) minuscole - -> 50 moduli totali.
Si chiamino i moduli con i numeri da 1 a 50, si avranno 50(50) combinazioni di diversi moduli in quanto la password è composta da due coppie di lettere.

Si considerino ora le password formate da moduli con lettere o maiuscole o minuscole del tipo (A,E)(E,E). Si avranno 25 tipi diversi di moduli con lettere tutte maiuscole, e altri 25 minuscoli, che si andranno a combinare l'un l'altro. Quindi altri 25(25) possibilità.

In tutto si avranno quindi 50(50) +25(25)2 password possibili ossia (2x5^2)^2 +5^4 = 2^2x5^4 + 2(5^4) =(2^2+2)5^4 = 6x5^4

Ora: questa risoluzione è quella che mi è venuta in mente ieri sera quando mi hanno ridato il foglio delle olimpiadi: durante la prova non avevo la minima idea di come fare. Mi sembra una soluzione piuttosto complessa, tipica di chi di combinatoria sa quasi nulla. Quindi vorrei che mi diceste se ci sono soluzioni piu sbrigative, se si possono saltare dei passaggi, se si può formalizzare con meno complessità questo problema e risolvere in 3 minuti ( ossia la media del tempo che andava fatta per problema nella gara). Infatti per elaborarne una così ci ho messo come minimo piu di mezz'ora!!

Grazie a tutti

[Giuseppe R]

Senza tenere conto di maiuscole e minuscole le vocali possono essere sistemate in $ 5^4 $ modi (la prima ha 5 opzioni, come la 2, la 3 e la 4). In che posizione possono stare le 2 minuscole? 1-2, 1-3, 1-4, 2-3, 2-4, 3-4; quindi 6. Risultato: $ 6*5^4 $

[Willy67]

Comprendo che $ 5^4 $ sono i modi di porre le vocali senza tenere conto delle maiuscole e minuscole. Non comprendo perchè sapendo quali posizioni devono avere le maiuscole lo moltiplichi per 6

[Giuseppe R]

Comprendo che $ 5^4 $ sono i modi di porre le vocali senza tenere conto delle maiuscole e minuscole. Non comprendo perchè sapendo quali posizioni devono avere le maiuscole lo moltiplichi per 6

Esempio: la combinazione AAAA
Le minuscole possono stare:
1)1-2 posizione: aaAA
2)1-3 posizione: aAaA
3)1-4 posizione: aAAa
4)2-3 posizIone: AaaA
5)2-4 posizione: AaAa
6)3-4 posizione: AAaa
Quindi per ognuno delle $ 5^4 $ combinazioni, considerando che 2 lettere devono essere minuscole e 2 maiuscole, ce ne sono 6. Quindi $ 6*5^4 $

[gian92]

vabbè più in generale noi possiamo considerare le maiuscole come a le minuscole e come b le maiuscole

quindi per avere il numero di possbili disposizioni è sufficiente calcolare gli anagrammi di una parola di 4 lettere, a 2 a due uguali.

ovvero $ \frac{4!}{2!2!} = 6 $

in generale se hai una parola di n lettere, che ha
$ a_1,a_2,a_3...a_n $ lettere uguali (3a, 4b, etc.)
i suoi anagrammi saranno
$ A_p=\frac{n!}{a_1a_2a_3\cdot...\cdot a_n} $

[Willy67]

Gian non ho ben capito cosa vuoi dire eheh scusate se non comprendo al volo!

[gian92]

aspè vediamo se questo ti è più chiaro, non sono mai stato capace a spiegare

http://it.wikipedia.org/wiki/Calcolo_combinatorio

la parte permutazioni con ripetizioni

[Willy67]

Dunque Gian, io ho capito che le permutazioni distinte di un insieme A formato da n elementi sono esattamente n!/k1!...kr!, dove k1 è il numero di volte che si ripete l'elemento 1 nell'insieme. Nel problema si parla di maiuscole e minuscole. Ma nel mio caso non si tratta di calcolare il numero di permutazioni dell insieme {a,e,i,o,u,A,E,I,O,U} in quanto una permutazione è una sequenza ordinata dei suoi elementi nella quale ogni oggetto viene presentato una sola volta!

[gian92]

aspè, te devi trovare le possibili disposizioni delle maiuscole e delle minuscole.

senza considerare che lettera sia (se a, e, i ,o , u...) quindi sarai daccordo che avere due maiuscole e due minuscole è come avere due a e due b...e a quel punto ti fai le permutazioni di aabb

quando avrai trovato questo numero (6) lo moltiplichi per tutte le possibili vocali che ci puoi mettere ($ 5^4 $)

[Claudio.]

La suoluzione che hai dato è qualcosa di assurdo per questo esercizio
Delle maiuscole e minuscole devi contare solo le permutazioni poichè le combinazioni delle lettere le calcoli già tutti in $ 5^4 $ le permutazione delle vocali sono 4 fattoriale fratto le ripetizioni che sono 2, moltiplichi poi tutto per le combinazioni quindi:

$ \displaystyle \frac{4!}{2!2!} \cdot 5^4 = 6 \cdot 5^4 $