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
28.09.2004 21:23
It is also Romanian TST 2003. And as I remember, this problem were discussed before on forum.
14.10.2004 20:51
This problems is still unsolved.
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.
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.
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).
19.11.2023 10:45
another solution I came across by math154 from here
I hope it is not exactly the same as above