OliForum Matematico

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...

Ce n'è anche una da due pagine fitte con una decina di binomiali a mano, garantisco io.

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.

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.

http://www.mathlinks.ro/Forum/viewtopic ... 26#p521326

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

Hint minuscolo (in tutti i sensi ) per la "riga e mezza"... triangolo di Tartaglia modulo 2

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

Ok, ok. L'ho sparata un po' grossa con la riga e mezza. Ma guardate questa:

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...

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} $