Alfabet - dziwny przykład ze zbiorku Pawłowskiego
: 11 paź 2015, o 19:58
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.
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.