Ciao. Questo l'ho pescato da Mathlinks (incredibile: vi siete presi la briga di metterlo là e non qui... vergogna!!)
Sia S una stringa composta da 99 caratteri, di cui 66 A e 33 B. Diciamo che S è buona se, per ogni n compreso tra 1 e 99, la sottostringa composta dai primi n caratteri di S ha un numero dispari di permutazioni distinte.
Quante sono le stringhe buone? Come sono fatte?
Bel problemino, con una soluzione da una rigaemmezza...
Stringhe buone (Italian TST 2006)
Stringhe buone (Italian TST 2006)
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
ALURA
Sia $ A_n $ il numero di A presenti nella sottostringa formata dalle prime n lettere.
Sia $ B_n $ il numero di B presenti nella sottostringa formata dalle prime n lettere.
Dato n, il numero di permutazioni è: $ \frac{n!}{(A_n)!(B_n)!} $
Step 1:Considerando n= 64 ho un numero di permutazioni dispari sse $ A_{64}=64 $
Interpretazione carina:
Ho 64 perle di due colori.
Claim:” se le perle non sono tutte uguali allora le permutazioni possibili sono pari”.
Sia considerata una generica configurazione che chiamo 1.
Dispongo le perle su di una retta, numerandole da 1 a 64.
Sia considerata la potenza di due maggiore $ (2^k) $ tale che le perle compresa tra essa e la prima non siano simmetriche rispetto all’asse del settore considerato.
K esiste sempre a meno che:
La configurazione sia simmetrica rispetto all’asse di $ (1,2^t) $ per qualsiasi t<7 ovvero le prime $ 2^{t-1} $ perle siano simmetriche rispetto alle seconde $ 2^{t-1} $, ciò vuole dire in particolare che tutte le perle sono uguali (la prima è simmetrica della seconda, e quindi sono uguali, le prime due delle seconde due...).
In tutti gli altri casi opero come segue.
Alla configurazione considerata faccio corrispondere biunivocamente la seguente configurazione: divido le 64 perle in tanti settori di lunghezza $ 2^k $, traccio l’asse di ciascun settore e applico una simmetria assiale in ciascun settore.
La configurazione trovata (che chiamo 2) sarà diversa da quella considerata prima poiché per ipotesi la configurazione 1 non era simmetrica rispetto all’asse del settore $ (1,2^k) $mentre lo era rispetto all’asse di $ (1,2^{k+1}) $ (se k è diverso da 6). Inoltre anche la configurazione 2 sarà simmetrica rispetto all’asse di $ (1,2^{k+1}) $ (se k è diverso da 6) ma non rispetto a quello di $ (1,2^k) $ quindi alla configurazione 2 faccio corrispondere la configurazione 1.
Posso quindi creare delle coppie di configurazioni distinte. Le permutazioni totali risulteranno quindi essere pari a meno che le perle non siano tutte uguali (nel cui caso c'è un'unica permutazione).
Questo vuole dire che le prime 64 lettere sono tutte A. Quindi ho un numero dispari di permutazioni per tutti gli n<65 sse le prime 64 lettere sono tutte A.
Step 2: Non un numero di permutazioni dispari sia per n=64 che per n=96 se $ A_{64} = 64 ; B_{96}\not =32 $
Sia f(n) il massimo numero i tale che $ 2^i $ divida n!.
Sia g(n) il massimo numero i tale che $ 2^i $ divida n.
È ben noto che $ f(n)= \sum_{i=1}^{\infty}[\frac{n}{2^i}] $
Nelle posizioni comprese tra 65 e 96 posso avere 0, 1 o 2 A.
Le permutazioni saranno a seconda dei casi:
$ \frac{96!}{(32)!(64)!} $
$ \frac{96!}{(31)!(65)!} $
$ \frac{96!}{(30)!(66)!} $
essendo $ \frac{n!}{(A_n)!(B_n)!} $ intero vale la seguente: $ f(96) \ge f(A_{96})+f(B_{96}) $ e l’uguaglianza vale sse $ \frac{n!}{(A_n)!(B_n)!} $ è dispari.
verifico facilmente che:
$ f(65)+f(31) $ = $ f(64)+f(32)-5<f(66)+f(30) $ = $ f(32)-5+f(64)+2 $ < $ f(32)+f(64) $
dalla definizione di f (contando i fattori due di differenza).
Quindi solo se $ B_{96}= 32 $ il numero di permutazioni può essere dispari.
Sia $ A_n $ il numero di A presenti nella sottostringa formata dalle prime n lettere.
Sia $ B_n $ il numero di B presenti nella sottostringa formata dalle prime n lettere.
Dato n, il numero di permutazioni è: $ \frac{n!}{(A_n)!(B_n)!} $
Step 1:Considerando n= 64 ho un numero di permutazioni dispari sse $ A_{64}=64 $
Interpretazione carina:
Ho 64 perle di due colori.
Claim:” se le perle non sono tutte uguali allora le permutazioni possibili sono pari”.
Sia considerata una generica configurazione che chiamo 1.
Dispongo le perle su di una retta, numerandole da 1 a 64.
Sia considerata la potenza di due maggiore $ (2^k) $ tale che le perle compresa tra essa e la prima non siano simmetriche rispetto all’asse del settore considerato.
K esiste sempre a meno che:
La configurazione sia simmetrica rispetto all’asse di $ (1,2^t) $ per qualsiasi t<7 ovvero le prime $ 2^{t-1} $ perle siano simmetriche rispetto alle seconde $ 2^{t-1} $, ciò vuole dire in particolare che tutte le perle sono uguali (la prima è simmetrica della seconda, e quindi sono uguali, le prime due delle seconde due...).
In tutti gli altri casi opero come segue.
Alla configurazione considerata faccio corrispondere biunivocamente la seguente configurazione: divido le 64 perle in tanti settori di lunghezza $ 2^k $, traccio l’asse di ciascun settore e applico una simmetria assiale in ciascun settore.
La configurazione trovata (che chiamo 2) sarà diversa da quella considerata prima poiché per ipotesi la configurazione 1 non era simmetrica rispetto all’asse del settore $ (1,2^k) $mentre lo era rispetto all’asse di $ (1,2^{k+1}) $ (se k è diverso da 6). Inoltre anche la configurazione 2 sarà simmetrica rispetto all’asse di $ (1,2^{k+1}) $ (se k è diverso da 6) ma non rispetto a quello di $ (1,2^k) $ quindi alla configurazione 2 faccio corrispondere la configurazione 1.
Posso quindi creare delle coppie di configurazioni distinte. Le permutazioni totali risulteranno quindi essere pari a meno che le perle non siano tutte uguali (nel cui caso c'è un'unica permutazione).
Questo vuole dire che le prime 64 lettere sono tutte A. Quindi ho un numero dispari di permutazioni per tutti gli n<65 sse le prime 64 lettere sono tutte A.
Step 2: Non un numero di permutazioni dispari sia per n=64 che per n=96 se $ A_{64} = 64 ; B_{96}\not =32 $
Sia f(n) il massimo numero i tale che $ 2^i $ divida n!.
Sia g(n) il massimo numero i tale che $ 2^i $ divida n.
È ben noto che $ f(n)= \sum_{i=1}^{\infty}[\frac{n}{2^i}] $
Nelle posizioni comprese tra 65 e 96 posso avere 0, 1 o 2 A.
Le permutazioni saranno a seconda dei casi:
$ \frac{96!}{(32)!(64)!} $
$ \frac{96!}{(31)!(65)!} $
$ \frac{96!}{(30)!(66)!} $
essendo $ \frac{n!}{(A_n)!(B_n)!} $ intero vale la seguente: $ f(96) \ge f(A_{96})+f(B_{96}) $ e l’uguaglianza vale sse $ \frac{n!}{(A_n)!(B_n)!} $ è dispari.
verifico facilmente che:
$ f(65)+f(31) $ = $ f(64)+f(32)-5<f(66)+f(30) $ = $ f(32)-5+f(64)+2 $ < $ f(32)+f(64) $
dalla definizione di f (contando i fattori due di differenza).
Quindi solo se $ B_{96}= 32 $ il numero di permutazioni può essere dispari.
Ultima modifica di enomis_costa88 il 30 mag 2006, 16:31, modificato 1 volta in totale.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Step 3: Se $ A_{64} = 64; B_{96}=32 $ allora ho un numero dispari di permutazioni per qualsiasi n piu piccolo di novantasette.
Infatti il numero di permutazioni per 97>n>64 risulta essere:
$ p(n)= p(n-1)*\frac{n}{n-64} $
ma $ n \equiv n-64 (mod 64) $ ovvero g(n)=g(n-64) per $ n \not \equiv 0 (mod 64) $ (ovvero sempre nell’intervallo considerato) quindi
$ P(96)= \frac{96!}{(32)!(64)!} $ risulta essere dispari e ciò vale anche per qualsiasi n<97.
Step 4: conclusione.
Mi rimangono ancora due A da disporre e una B.
Considero n=98, nelle posizioni 97 e 98 posso avere un A e un B oppure due A.
Le permutazioni saranno a seconda dei casi:
$ \frac{98!}{(33)!(65)!}=p(96)*\frac{97*98}{33*65} $
$ \frac{98!}{(32)!(66)!}= p(96)*\frac{97*98}{65*66} $
noto che solo la seconda è dispari infatti è il prodotto di due quantità dispari (p(96) è dispari..).
In questo caso la lettera nella 97-esima posizione sarà una A, e verifico che anche $ p(97)= p(96)*\frac{97}{65} $ è dispari.
Nell’ultima posizione ho quindi solo un’ultima lettera da piazzare che sarà una B.
Per scaramanzia controllo che $ p(99)= p(98)*\frac{99}{33} $ sia dispari e lo è.
Quindi ho solo una configurazione possibile..
64 A seguiti da 32 B seguiti a loro volta da 2 A con una B in fondo.
Infatti il numero di permutazioni per 97>n>64 risulta essere:
$ p(n)= p(n-1)*\frac{n}{n-64} $
ma $ n \equiv n-64 (mod 64) $ ovvero g(n)=g(n-64) per $ n \not \equiv 0 (mod 64) $ (ovvero sempre nell’intervallo considerato) quindi
$ P(96)= \frac{96!}{(32)!(64)!} $ risulta essere dispari e ciò vale anche per qualsiasi n<97.
Step 4: conclusione.
Mi rimangono ancora due A da disporre e una B.
Considero n=98, nelle posizioni 97 e 98 posso avere un A e un B oppure due A.
Le permutazioni saranno a seconda dei casi:
$ \frac{98!}{(33)!(65)!}=p(96)*\frac{97*98}{33*65} $
$ \frac{98!}{(32)!(66)!}= p(96)*\frac{97*98}{65*66} $
noto che solo la seconda è dispari infatti è il prodotto di due quantità dispari (p(96) è dispari..).
In questo caso la lettera nella 97-esima posizione sarà una A, e verifico che anche $ p(97)= p(96)*\frac{97}{65} $ è dispari.
Nell’ultima posizione ho quindi solo un’ultima lettera da piazzare che sarà una B.
Per scaramanzia controllo che $ p(99)= p(98)*\frac{99}{33} $ sia dispari e lo è.
Quindi ho solo una configurazione possibile..
64 A seguiti da 32 B seguiti a loro volta da 2 A con una B in fondo.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
http://www.mathlinks.ro/Forum/viewtopic ... 26#p521326
@Marco Sarei contento se trascrivessi la soluzione di una riga .
Bel problemino, con una soluzione da una rigaemmezza...
@Marco Sarei contento se trascrivessi la soluzione di una riga .
Let's generalize a little bit...
Under which conditions, given a and b integers, there is exactly one good string with a "A"s and b "B"s? Is it possible to have a,b such that there is more than one good string
Ultima modifica di herbrand il 29 mag 2006, 22:41, modificato 1 volta in totale.
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
) per la "riga e mezza"... Ok, ok. L'ho sparata un po' grossa con la riga e mezza. Ma guardate questa:herbrand ha scritto:@Marco Sarei contento se la trascrivessi la soluzione di una riga .Let's generalize a little bit...
Under which conditions, given a and b integers, there is exactly one good string with a "A"s and b "B"s? Is it possible to have a,b such that there is more than one good string
Dimostro che se $ \binom n k $ è dispari, allora esiste un'unica stringa buona con n simboli e k A. [ovviamente se è pari, non ho stringhe buone per definizione]
Devo anche dimostrarvi che gli anagrammi sono $ \binom n k $? No, vero?
Dim.:Per induzione su n. n=0 (o 1 se vi scocciano gli anagrammi di stringhe vuote) ok.
Allora diciamo che ho $ \binom n k $ dispari. $ \binom n k $ è dispari sse esattamente uno tra $ \binom{n-1}{k-1} $ e $ \binom{n-1}k $ è dispari. Ma allora (per ipotesi induttiva su n) esiste esattamente una sottostringa buona su n-1 simboli e una sola lettera finale possibile, aggiungendo la quale la stringa resta buona e con la composizione voluta. []
Manca la parte di costruire l'unica stringa buona, ma con la formula delle parità dei binomiali, è un attimo verificare che le prime 96 lettere sono A e B, nel modo che ha detto Enomis.
Forte, vero?
A proposito la sapete tutti la formula per la parità dei binomiali, vero?
Se non la sapete:
Dimostrare che $ \binom n k $ è dispari se e solo se scrivendo in base 2 $ k $ e $ n-k $ allora la somma $ k+(n-k) $ non ha riporti.
EDIT: Dannazione alla fretta! Avevo ciccato l'enunciato. Ora va meglio...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
mattilgale
- Messaggi: 372
- Iscritto il: 01 gen 1970, 01:00
- Località: Lucca
- Contatta:
metto la mia soluzione, che però non è stata tale perché alla gara ho racimolato solo 2 punti lasciandola incompleta... 
allora
ovviamente se chiamo $ n_A $ il numero di A e $ n_B $ il numero di B ho che il numero di modi di riordinare le prime n lettere è
$ {n \choose n_A}={n \choose n_B} $
supponiamo $ {63\choose n_A} $ dispari, allora chiamo y quello tra n_A e n_B che non cambia aggiungendo la lettera dopo, cioè se aggiungo una B y=n_A e viceversa...
allora
$ {64\choose y}={63\choose y}\cdot \frac{64}{64-y} $
quindi y=0 o y=64 altrimenti si avrebbe un risultato pari...
allora ci sono 64 lettere uguali, cioè 64 A ( è facile vedere che va bene questo risultato, c'è sempre un solo modo, cioè un numero dispari di modi, di riordinare n lettere uguali)...
adesso andiamo a 96
$ {96\choose y}={95\choose y}\cdot\frac{96}{96-y} $, ponen $ {95\choose y} $ dispari, si osserva che $ {96\choose y} $ è dispari se e solo se 96-y vale 32 o 96... poiché non si possono avere 96 lettere uguali, 96-y=32 => y=64...
la stringa è fatta da 64A poi 32B...
ora
consideriamo che al 98-esimo posto si possono avere solo due casi, o 65A o 66A... poiché se ce ne fossero 65, avremmo che $ \frac{98!}{65!\cdot 33!} $ contiene più fattori 2 sopra che sotto, allora $ {98\choose 65} $ è pari, quindi abbiamo che la stringa può essere solo
64A 32B AAB
verifichiamo adesso che funzioni
già fatto per le prime 64
dimostriamo induttivamente dalla 65-esima alla 96-esima lettera...
infatti
se $ {n-1\choose 64} $ è dispari => $ {n\choose 64}={n-1\choose 64}\cdot \frac{n}{n-64} $ che è ovviamente dispari poiché nella frazione la max potenza di due che sta sopra è uguale a quella di sotto per ogni n<64...
gli ultimi tre casi sono ovvi
poiché
$ {97\choose 65}={96\choose 64}\cdot\frac{97}{65} $
$ {98\choose 66}={97\choose 65}\cdot\frac{98}{66} $
$ {99\choose 66}={98\choose 66}\cdot\frac{99}{33} $
allora
ovviamente se chiamo $ n_A $ il numero di A e $ n_B $ il numero di B ho che il numero di modi di riordinare le prime n lettere è
$ {n \choose n_A}={n \choose n_B} $
supponiamo $ {63\choose n_A} $ dispari, allora chiamo y quello tra n_A e n_B che non cambia aggiungendo la lettera dopo, cioè se aggiungo una B y=n_A e viceversa...
allora
$ {64\choose y}={63\choose y}\cdot \frac{64}{64-y} $
quindi y=0 o y=64 altrimenti si avrebbe un risultato pari...
allora ci sono 64 lettere uguali, cioè 64 A ( è facile vedere che va bene questo risultato, c'è sempre un solo modo, cioè un numero dispari di modi, di riordinare n lettere uguali)...
adesso andiamo a 96
$ {96\choose y}={95\choose y}\cdot\frac{96}{96-y} $, ponen $ {95\choose y} $ dispari, si osserva che $ {96\choose y} $ è dispari se e solo se 96-y vale 32 o 96... poiché non si possono avere 96 lettere uguali, 96-y=32 => y=64...
la stringa è fatta da 64A poi 32B...
ora
consideriamo che al 98-esimo posto si possono avere solo due casi, o 65A o 66A... poiché se ce ne fossero 65, avremmo che $ \frac{98!}{65!\cdot 33!} $ contiene più fattori 2 sopra che sotto, allora $ {98\choose 65} $ è pari, quindi abbiamo che la stringa può essere solo
64A 32B AAB
verifichiamo adesso che funzioni
già fatto per le prime 64
dimostriamo induttivamente dalla 65-esima alla 96-esima lettera...
infatti
se $ {n-1\choose 64} $ è dispari => $ {n\choose 64}={n-1\choose 64}\cdot \frac{n}{n-64} $ che è ovviamente dispari poiché nella frazione la max potenza di due che sta sopra è uguale a quella di sotto per ogni n<64...
gli ultimi tre casi sono ovvi
poiché
$ {97\choose 65}={96\choose 64}\cdot\frac{97}{65} $
$ {98\choose 66}={97\choose 65}\cdot\frac{98}{66} $
$ {99\choose 66}={98\choose 66}\cdot\frac{99}{33} $
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"
Galileo Galilei
Galileo Galilei