Alfabet - dziwny przykład ze zbiorku Pawłowskiego

[Majeskas]

Zadanie: Alfabet pewnego języka składa się z \(\displaystyle{ n}\) liter. Każde słowo w tym języku, czyli ciąg liter (w którym litery mogą się powtarzać), zawiera nie więcej niż \(\displaystyle{ m}\) liter. Liczbę liter ciągu tworzącego słowo nazywamy jego długością. Niech \(\displaystyle{ a_k}\) oznacza liczbę wszystkich różnych słów długości \(\displaystyle{ k}\) w tym języku. Udowodnij, że \(\displaystyle{ \frac{a_1}n+\frac{a_2}{n^2}+\cdots+\frac{a_m}{n^m}\le m}\).

Rozwiązanie: Niech \(\displaystyle{ S}\) będzie zbiorem wszystkich słów w danym języku. Dla każdego słowa \(\displaystyle{ w\in S}\) długości \(\displaystyle{ k}\) (\(\displaystyle{ k=1,2,3,\ldots,m}\)) rozważmy wszystkie możliwe przedłużenia do słów długości \(\displaystyle{ m}\), których pierwsze \(\displaystyle{ k}\) liter to litery słowa \(\displaystyle{ w}\). Oczywiście powstałe w ten sposób słowa mogą nie należeć do \(\displaystyle{ S}\). Co więcej każde słowo długości \(\displaystyle{ k}\) ma dokładnie \(\displaystyle{ n^{m-k}}\) przedłużeń. Tym samym dla każdego \(\displaystyle{ k}\) zachodzi nierówność \(\displaystyle{ a_k\cdot n^{m-k}\le n^m}\), a stąd łatwo wynika teza.

Nie wiem, co tu się dzieje. Dla mnie z treści zadania wynika, że słowo ma długość \(\displaystyle{ k}\), jeśli składa się z \(\displaystyle{ k}\) liter, niezależnie, czy są różne, czy nie. W takim wypadku jest po prostu \(\displaystyle{ a_k=n^k}\). Jedyna inna interpretacja, jaka mi się nasuwa, jest taka, że słowo ma długość \(\displaystyle{ k}\), gdy występuje w nim \(\displaystyle{ k}\) różnych liter. Ale to też nie pasuje do rozwiązania. Weźmy sobie pewne słowo długości \(\displaystyle{ 1}\), np. \(\displaystyle{ A}\). Wtedy nie jest prawdą, że to słowo można przedłużyć do słowa długości \(\displaystyle{ m}\) na \(\displaystyle{ n^{m-1}}\) sposobów. Przecież mogę do tego słowa dorzucić dowolną liczbę kolejnych liter \(\displaystyle{ A}\) i to nie zmieni jego długości. A więc istnieje przeliczalnie wiele sposobów przedłużenia go do jakiegokolwiek dłuższego słowa.
Nie wiem, może coś mi się zacięło. Jakby ktoś widział, o co tu chodzi, byłbym wdzięczny.

[arek1357]

Tak w tym zadaniu na dwoje babka wróżyła!

[Premislav]

Nie zgodzę się z tym, że \(\displaystyle{ a_{k}=n^{k}}\), tylko raczej \(\displaystyle{ a_{k} \le n^{k}}\), ale to czyni zadanie równie nieciekawym. Też nie wiem, po co takie rozwiązanie (albo nie rozumiem treści).

[Majeskas]

Nie zgodzę się z tym, że \(\displaystyle{ a_{k}=n^{k}}\), tylko raczej \(\displaystyle{ a_{k} \le n^{k}}\)

Dlaczego?

[Premislav]

Bo przecież np. w polskim nie wszystko, co ułożysz z, dajmy na to, trzech liter alfabetu, jest słowem. Nie ma powodu, żeby jakkolwiek inaczej było w innym języku, w przeciwnym bowiem wypadku zbiory słów każdych dwóch języków o tym samym alfabecie byłyby równe (chyba że bierzemy jeszcze pod uwagę intonację, akcentowanie czy inne dziwy).
Jest to nawet ujęte w rozwiązaniu, mianowicie w tym zdaniu:

Oczywiście powstałe w ten sposób słowa mogą nie należeć do \(\displaystyle{ S}\)

-- 11 paź 2015, o 21:16 --

Ajajaj, późna pora i w zasadzie błąd logiczny się wkradł, no ale chyba wiadomo, o co mi chodziło.

-- 11 paź 2015, o 21:17 --

Tzn. może istnieć sobie język, który ma takie ekstremum, co jest o tyle zabawne, że wtedy wszystkie języki nad tym samym alfabetem i mające to samo ograniczenie górne na długość słowa zawierają się (w znaczeniu słownika) w tym. Ale rozważany język nie musi mieć takiej własności.

-- 11 paź 2015, o 21:34 --

Ba, nie tylko takie samo ograniczenie, mogą też mieć ostrzejsze (czyli mniejszą maksymalną długość słowa), gdyby miały taką samą, to (pomijając odcienie znaczeniowe, homonimy, akcenty itd.) słowniki byłby takie same. Naprawdę powinienem już iść spać.

[Majeskas]

OK, być może Twoja w sumie dość prosta uwaga stanowi meritum w tym zadaniu. Ja potraktowałem sprawę czysto matematycznie, tzn. generujemy ciąg liter i nazywamy to słowem, nie wgłębiając się, czy ten ciąg liter układa się w sens. (Po przerobieniu pewnej liczby zadań z kombinatoryki, gdzie na ogół przyjmuje się taką interpretację, człowiek odruchowo tak na to patrzy). Jeśli założyć, że zadanie ma jakiś kontekst realistyczny, tj. faktycznie interesują nas tylko słowa, które mają sens, to wszystko się zgadza. Tylko właśnie - jak zauważyłeś - nie potrzeba w takim razie tak rozbudowanego rozwiązania.