Cash Problems

1. Let L be the set of nonrepetitive words over the alphabet {1, 2, 3}. Give an exact enumeration of L With respect to length. For the solution to this problem I offer US$100. Both Brandenburg and Brinkhuis have shown that the number of non-repetitive words of length n over a 3 letter alphabet grows exponentially with n. A related result is that of Cassaigne who has given a satisfying enumeration of overlap-free words over a 2 letter alphabet.
2. Is there an algorithm which decides, given a pattern p and a natural number n, whether p is avoidable on n letters? If so, give such an algorithm. I offer US$100 for the solution to this problem. This problem has been open since 1979 when it was posed in the paper of Bean, Ehrenfeucht and McNulty.
3. Is there an algorithm which decides, given a pattern p, whether p is strongly avoidable? If so, give such an algorithm. Again, US$100 to the solver of this problem.
4. Is there an algorithm which decides, given a pattern p and a natural number n, whether p is strongly avoidable on n letters? If so, give such an algorithm. I offer US$100 for the solution to this problem.
5. For US$100, decide the following conjecture: If pattern p is avoidable on alphabet S, then the set of omega-words on S avoiding p is perfect This is a favourite conjecture of mine.
6. For US$100, decide the following conjecture: If the smallest alphabet on which p is avoidable is of size n, then p is HDOL-avoidable on n letters.