Matematyka.pl

Indeks zgodności dla szyfrogramu \(\displaystyle{ c}\) długości \(\displaystyle{ n}\), w którym litera \(\displaystyle{ A}\) występuje \(\displaystyle{ f_A}\) razy, \(\displaystyle{ Ą}\) występuje \(\displaystyle{ f_Ą}\) razy itd., jest dany wzorem
\(\displaystyle{ \frac{f_A(f_A−1)+f_Ą(f_Ą−1)+...+f_Ż(f_Ż−1)}{n(n−1)}}\)
Niech \(\displaystyle{ n}\) będzie liczbą naturalną. Wyznacz największą i najmniejszą możliwą wartość indeksu zgodności dla ciągu znaków długości \(\displaystyle{ n}\). Podaj przykład ciągu długości \(\displaystyle{ n}\), dla którego wartość indeksu zgodności jest najmniejsza/największa.

Łatwo zauważyć, że maksymalna wartość indeksu zgodności wynosi \(\displaystyle{ 1}\) - dla ciągu, w którym wszystkie litery są takie same (mamy wówczas \(\displaystyle{ \frac{n(n-1)}{n(n-1)} = 1}\)).
Analizując minimalną wartość, można zauważyć, że jeśli długość ciągu \(\displaystyle{ n\le35}\) (gdzie \(\displaystyle{ 35}\) to liczba liter w polskim alfabecie), to minimalna wartość indeksu zgodności wynosi \(\displaystyle{ 0}\) - dla ciągu, w którym każda litera występuje co najwyżej \(\displaystyle{ 1}\) raz.
Co jednak w przypadku, gdy \(\displaystyle{ n > 35}\)? Nie jest wówczas możliwe, aby każdy litera występowała maksymalnie raz. Jak można wyznaczyć minimalną wartość indeksu zgodności w takim przypadku?

Wsk. Sprawdź jak wygląda indeks dla słów
abbbbbbbcc, aabbbbbbcc
aaabbbbbcc i aaaabbbbcc.

Wsk2. Poczytaj o funkcjach wypukłych

dla abbbbbbbcc indeks wynosi \(\displaystyle{ \frac{44}{90}}\)
dla aabbbbbbcc indeks wynosi \(\displaystyle{ \frac{34}{90}}\)
dla aaabbbbbcc indeks wynosi \(\displaystyle{ \frac{28}{90}}\)
dla aaaabbbbcc indeks wynosi \(\displaystyle{ \frac{26}{90}}\)

Na podstawie tego przypuszczam, że indeks zgodności jest tym mniejszy, im rozkład liter jest bardziej równomierny. Czy takie stwierdzenie jest prawdziwe (można je udowodnić)? Pojęcie funkcji wypukłej znam, ale nie bardzo wiem, jak to ze sobą powiązać.

T tak, to dobry wniosek. Zauważ, że `x(x-1)` jest wypukla

Zgadza się. W liczniku mamy więc sumę funkcji wypukłych, która też jest funkcją wypukłą.
Nie mam jednak pomysłu, jak sformułować dowód stwierdzenia, że indeks zgodności jest najmniejszy przy najbardziej równomiernym rozkładzie liter.

Nie masz sumy funkcji wypukłych, tylko sumę wartości tej samej funkcji wypukłej w kilku różnych punktach. Nierówność Jensena da Ci ograniczenie z dołu na taką sumę. Pomyśl kiedy to minimum da sie osiągnąć.