A word is a sequence of n letters of the alphabet {a, b, c, d}. A word is said to be complicated if it contains two consecutive groups of identic letters. The words caab, baba and cababdc, for example, are complicated words, while bacba and dcbdc are not. A word that is not complicated is a simple word. Prove that the numbers of simple words with n letters is greater than $2^n$, if n is a positive integer.
Problem
Source: Brazilian preparation to IMO 2004
Tags: floor function, induction, combinatorics unsolved, combinatorics
Myth
28.09.2004 21:23
It is also Romanian TST 2003. And as I remember, this problem were discussed before on forum.
Myth
14.10.2004 20:51
This problems is still unsolved.
Valentin Vornicu
25.09.2005 01:37
Let us denote by $S(n)$ the set of simple words with $n$ letters and by $s_n$ the number of elements in $S(n)$. If we put a letter at the end of each of the simple words from $S(n)$ we obtain a set $T(n+1)$ of $t_{n+1}$ words of length $n+1$, their number being $t_{n+1}=4s_n$. Obviously $S(n+1) \subset T(n+1)$, $S(n+1)\neq T(n+1)$. Let $T_1(n+1)$ be the set of those words from $T(n+1)$ which have the last two letters the same, $T_k(n+1)$ the set of $T(n+1)$ which end in two consecutive identical groups of $k$ letters, for each $k\in\{1,2,\ldots,m\}$, where $m=\displaystyle \left\lfloor \frac { n+1 } 2 \right\rfloor$. Obviously \[ f(n+1)\geq t_{n+1}-|T_1(n+1)|-|T_2(n+1)|-\cdots - |T_m(n+1)|\] We have $t_{n+1}=4f(n)$, $|T_1(n+1)|=f(n)$, and furthermore $|T_k(n+1)|\leq f(n+1-k)$, because of the fact that the mapping of $S(n+1-k)$ into $T_k(n+1)$ given by adding to a simple word of $n+1-k$ letters its own last $k$ letters is obviously surjective. We have $f(1)=4$, $f(2)=12>4$. By induction we want to prove $f(k+1)>2f(k)$. We have \[ f(n+1)\geq 4f(n)-f(n)-\frac 12 f(n) - \frac 14 f(n)- \cdots > 2 f(n) \] from which the conclusion follows.
jerjer
26.09.2005 13:21
But still the obvious next questions are : Q1: Is 2^n a tight bound ? Q2: Is the bound dependent on the alphabet size ? A precision : when I say obvious I mean the esayness to formulate such questions not that the answers are necessarily easy. REMARK : It seems that too often that thes olympiad/IMO problems concentrated on one fact. I believe it is nice to follow up , to give perspective to the result by showing how it hinges on the hypothesis, otherwise the solution as little meaning or constitutes merrely a useful technique. See and read Polya about problem solving in general and making VARIATION on problems.
JOTAJOTARIM
07.06.2007 21:41
Valentin Vornicu wrote: \box{ We have $t_{n+1}= 4f(n)$, $|T_{1}(n+1)| = f(n)$, and furthermore $|T_{k}(n+1)| \leq f(n+1-k)$, because of the fact that the mapping of $S(n+1-k)$ into $T_{k}(n+1)$ given by adding to a simple word of $n+1-k$ letters its own last $k$ letters is obviously surjective.} The mapping of $S(n+1-k)$ into $T_{k}(n+1)$ defined latter is wrong defined. The mapping of $T_{k}(n+1)$ into $S(n+1-k)$ given by removing to a word of $T_{k}(n+1)$ its own last $k$ letters is obviously injective (and this mapping is well defined).
parmenides51
19.11.2023 10:45
another solution I came across by math154 from here
Let $f(n)$ denote the number of simple words with $n$ letters. We'll show by strong induction that $f(n+1)>2f(n)$ for all $n\ge0$. Since $f(0)=1$ and $f(1)=4$, the base case is clear.
Now consider a simple word $W$ with $n\ge1$ letters, and prepend a letter $x\in\{a,b,c,d\}$ to it. There exist strings $S,T$ (possibly empty) such that
\[x+W=x+S+x+S+T \Longleftrightarrow W=S+x+S+T\]iff $x+W$ is complicated (note that $x+S+T\in W$ and is thus simple). Hence there is a surjection from simple words with $1\le k=|x+S+T|\le n$ letters to complicated words of the form $x+W$ (i.e. prepending the first $n+1-k$ letters of $x+S+T$ to get $x+W$), so by complementary counting,
\[f(n+1) \ge 4f(n) - \sum_{k=1}^{n}f(k) > 4f(n) - \sum_{k=1}^{n}\frac{f(n)}{2^{n-k}} > 2f(n),\]as desired.
I hope it is not exactly the same as above