5. Zadatak

Primijetimo da za svaki $k=1,2,\ldots,13$ vrijedi da je ukupan broj nizova slova $a$ i $b$ duljine $k$ jednak $2^k$ (za svaku poziciju u riječi biramo jedno od dva slova), pa je stoga ukupan broj nizova duljine između jednog i $13$ slova jednak

$$2^1+2^2+\cdots+2^{13}=2^{14}-1.$$

Pogledajmo jezik u kojem su riječi svi nizovi slova duljine $7$ ili više. Očito je uvjet iz zadatka zadovoljen: nadovezivanjem dviju takvih riječi dobivamo niz znakova dulji od $13$, pa se sigurno ne nalazi u jeziku. Ukupan broj takvih riječi je

$$2^7+2^8+\cdots+2^{13}=2^{14}-2^7.$$

Dokažimo da je to najveći broj riječi koji se može naći u jeziku. Jezik s najviše riječi u kojem se ne nalazi nijedna riječ duljine manje od $7$ je opisan gore. Promotrimo sada bilo koji jezik u kojem se nalazi barem jedna riječ duljine manje od $7$ i nazovimo ju $X$. Za proizvoljan niz $Y$ znakova duljine $7$, neka je $X+Y$ niz znakova nastao nadovezivanjem riječi $X$ i niza $Y$. Duljina tog niza je najviše $13$.

Za sve moguće nizove znakova $Y$ duljine $7$, promotrimo skupove oblika $\{Y,X+Y\}$. Kako se riječ $X$ nalazi u jeziku, barem jedan od nizova znakova $Y$ i $X+Y$ nije riječ. Kako takvih dvočlanih skupova ima $2^7$ (kao i nizova znakova od $7$ slova), barem toliko nizova znakova nije riječ. Zaključujemo da taj jezik može imati najviše $(2^{14}-1)-2^7$ riječi.

Dakle, ako se u jeziku ne nalazi nijedna riječ duljine manje od $7$, može imati najviše $2^{14}-2^7$ riječi, a ako se u jeziku nalazi barem jedna riječ duljine manje od $7$, može imati samo manje riječi. Time zaključujemo da je najveći broj riječi u jeziku $2^{14}-2^7=16256$.