Eppure l'ho già visto!

[Tess]

E sono sicuro che anche molti di voi l'hanno già visto.
Allora volevo spingere quelli che non l'avevano fatto o visto la soluzione a provarlo qui e ad indicare le idee e tecniche chiave per tentare di risolverlo.

Ma passiamo al problema:
Nel dizionario MA le parole hanno solo 2 lettere (indovinate un po' quali). Inoltre ogni parola ha almeno una e al più $2n+1$ lettere. Infine le parole sul dizionario MA hanno la seguente proprietà: se $a$ e $b$ stanno nel dizionario, allora la concatenazione $ab$ non sta nel dizionario.
Si chiede quante possano essere al più le parole nel dizionario MA.

[Loara]

Provo ad abbozzare una risposta.

Prima di tutto, siccome le lettere sono $2$, esistono $2^k$ parole diverse di lunghezza $k$. Sappiamo poi che $1+2+2^2+2^3+\cdots +2^{k-1}=2^k-1<2^k$, che può essere interpretato con il fatto che il numero di parole di $k$ lettere è maggiore del numero di tutte le parole formate da meno di $k$ lettere. Supponiamo ora che il dizionario sia formato da parole lunghe almeno $n+1$ lettere. Ma allora il dizionario può contenere tutte le parole con più di $n$ lettere, infatti la concatenazione di due parole forma una parola di più di $2n+1$ lettere. Dimostriamo ora che il dizionario non può contenere più parole. Supponiamo ora di aggiungere una parola $a$ con $k<n+1$ lettere. Essendo $n+1<k+(n+1)\leq 2n+1$ quindi se inseriamo $a$ la possiamo concatenare con ogni parola di $n+1$ lettere (ma anche di più lettere) ottenendo una parola nel dizionario, e quindi dovremo eliminare almeno $2^{n+1}$ parole. Questa perdita non può più essere ricolmata, in quanto il numero di parole lunghe meno di $n+1$ lettere è minore del numero di parole lunghe esattamente $n+1$. Quindi il numero di parole non può aumentare.
Alla fine il numero massimo di parole è $2^{2n+1}+2^{2n}+\cdots +2^{n+1}=2^{n+1}(2^n+2^{n-1}+\cdots +2+1)=2^{n+1}(2^{n+1}-1)$

EDIT: Ho aggiustato la soluzione, rendendola più chiara

[Tess]

Supponiamo ora di aggiungere una parola

ecco la causa della sbagliata soluzione. Così tu hai solo dimostrato che quella configurazione di parole non è migliorabile. Ma non sappiamo niente se un'altra configurazione di parole, completamente diverse, possa averne ancora di più...

Allora, visto che almeno uno ci ha provato, inizio con qualche aiutino. Intanto, se devo mostrare che non esiste una certa configurazione, quali sono gli strumenti che si usano più spesso per farlo? Magari inizio da quelli.

[Loara]

Ok, riformulo la soluzione, spero di non commettere altri errori.

Partiamo dall'assunto che il numero di tutte le parole di $k$ lettere è maggiore del numero di parole di meno di $k$ lettere (per una dimostrazione si veda il mio post precedente). Ora analizziamo due casi:

Caso 1: nel dizionario non ci sono parole con meno di $n+1$ lettere. Allora può contenere tutte le parole con più di $n$ lettere, in quanto la concatenazione di due parole porta ad una parola con più di $2n+1$ lettere. Quindi il numero massimo è $2^{n+1}(2^{n+1}-1)$ (si veda il post precedente).

Caso 2: nel dizionario c'è almeno una parola con meno di $n+1$ lettere. Chiamiamo $a$ una di queste parole, e indichiamo con $k_a$ il numero di lettere di $a$. Sappiamo che $k_a+n+1\leq 2n+1$ e $k_a+n+1>n+1$. Supponiamo ora che ci sono $m$ parole nel dizionario con $n+1$ lettere. Per il principio dei cassetti allora, tra tutte le parole possibili con $k_a+n+1$ lettere almeno $m$ NON possono comparire nel dizionario, altrimenti esiste una parola di $k_a+n+1$ lettere che è la concatenazione di una parola di $n+1$ lettere e di $a$. In questo dizionario non compaiono almeno $m$ parole lunghe $k_a+n+1$ e $2^{n+1}-m$ parole di $n+1$ lettere, ovvero non compaiono almeno $2^{n+1}$ parole, che è strettamente maggiore del numero di tutte le parole possibili con meno di $n+1$ lettere. Da ciò segue che il numero di parole in un dizionario con almeno una parola con meno di $n+1$ lettere non può essere maggiore del numero di parole di un dizionario che contiene tutte le parole con più di $n$ lettere.
Quindi la soluzione è $2^{n+1}(2^{n+1}-1)$.

[Tess]

Ah, ottimo! Buona soluzione! È addirittura più breve della mia! Ecco, questa è finalmente una dimostrazione come si deve!