Politechnika Śląska
Skończony ciąg elementów danego zbioru \(\Sigma\) nazywamy słowem nad alfabetem \(\Sigma\) . O ile nie prowadzi to do niejednoznaczności, słowo zapisujemy jako konkatenację elementów zbioru \(\Sigma.\) Na przykład słowo \(\mathtt{(s,ł,o,w,o)}\) nad alfabetem \(\Sigma=\{\mathtt{ł},\mathtt{o},\mathtt{s},\mathtt{w}\}\) można zapisać jako \(\mathtt{słowo}.\)
Rozszerzeniem słowa \(PS\) jest słowo \(P\mathtt{x}S,\) gdzie \(\mathtt{x}\) jest literą (każde ze słów \(P,\) \(S\) może być słowem pustym). Przykładowym rozszerzeniem słowa \(\mathtt{bak}\) jest \(\mathtt{bark},\) a rozszerzeniem słowa \(\mathtt{bark}\) jest \(\mathtt{barek}.\)
Niech \(X\) będzie słowem niepustym. Słowo postaci \(\mathit{XX}\) (np. \(\mathtt{kuskus}\)) nazywamy kwadratem. Mówimy, że słowo \(\mathit{PXXS}\) zawiera kwadrat \(\mathit{XX},\) natomiast słowem bezkwadratowym jest takie, które nie zawiera żadnego kwadratu. Zatem \(\mathtt{matematyka}\) jest słowem bezkwadratowym, a \(\mathtt{filologia}\) nim nie jest (zawiera kwadrat \(\mathtt{lolo}\)).
Dany jest alfabet \(\Sigma\) (zakładamy, że jest uporządkowany, czyli litery mają – jak to w alfabecie – pewną kolejność). Rozważmy następującą procedurę nonszalancką: Zaczynamy od słowa pustego \(W_{0}=\varepsilon.\) W \(n\) -tym kroku procedury tworzymy rozszerzenie \(W_{n}\) poprzedniego słowa \(W_{n-1}\) w następujący sposób: na końcu słowa \(W_{n-1}\) wstawiamy możliwie najmniejszą literę \(\mathtt{x}\) taką, że otrzymane słowo \(W_n=W_{n-1}\mathtt{x}\) jest bezkwadratowe. Jeżeli nie jest to możliwe, to próbujemy wstawić jak najmniejszą literę tuż przed ostatnią literą naszego słowa. Jeżeli to też jest niemożliwe, to próbujemy wstawić jak najmniejszą literę przed ostatnimi dwiema literami itd. Reasumując, w każdym kroku staramy się najdalej, jak tylko można, wstawić jak najmniejszą literę, by uzyskać słowo bezkwadratowe.
Zauważmy, że nad alfabetem \(\{\mathtt{a},\mathtt{b}\}\) procedura kończy się szybko: \[\varepsilon\ \to\ \mathtt{\underline{a}}\ \to\ \mathtt{a\underline{b}}\ \to\ \mathtt{ab\underline{a}}.\] Każde rozszerzenie słowa \(\mathtt{aba}\) zawiera kwadrat, więc nie sposób otrzymać kolejnego rozszerzenia.
Co się stanie, gdy zwiększymy alfabet? Dla alfabetu ternarnego \(\{\mathtt{a},\mathtt{b},\mathtt{c}\}\) początkowych kilka słów to \[\begin{split} \varepsilon\ & \to\ \mathtt{\underline{a}}\ \to\ \mathtt{a\underline{b}}\ \to\ \mathtt{ab\underline{a}}\ \to\ \mathtt{aba\underline{c}}\ \to\ \mathtt{abac\underline{a}}% \to\ \mathtt{abaca\underline{b}}\ \to\ \mathtt{abacab\underline{a}}\ \to \\ & \to\ \mathtt{abacab\underline{c}a}\ \to\ \mathtt{abacabca\underline{c}}\ \to\ \mathtt{abacabcac\underline{b}}\ \to\ \cdots. \end{split}\]
Czy i w tym przypadku procedura dobiega końca po skończonej liczbie kroków? Nie wiadomo. Teoretycznie nie można tego wykluczyć, ponieważ wiemy, że nad alfabetem ternarnym istnieje nieskończenie wiele słów, których każde rozszerzenie zawiera kwadrat. Obecnie wiemy również, że nie ma ani jednego słowa o tej własności nad alfabetem \(17\) -elementowym (więc nad takim alfabetem procedura nonszalancka nigdy się nie zakończy).
A czy istnieją słowa, których każde rozszerzenie zawiera kwadrat w przypadku alfabetów mocy od \(4\) do \(16\) ? Jak powyżej – nie wiadomo.