*Note: This is an extended comment, not a full answer.*

I don't know about you, but I didn't start out with any good intuition about the answer to the question. I decided to do some computer experiments/visualization.

I wrote some code in Prolog which generates square-free and three-halves-free words over a given alphabet. I don't usually use Prolog for anything, but this seemed like the sort of problem that it's very well suited to. Source code and an interactive environment is available here. (Please comment if it doesn't work, the link is dead, etc.) Please experiment on your own too!

The query below generates the three-halves-free words of length 5 over the alphabet x,y. In the code I called it "sandwich-free" rather than "three-halves-free".

```
?- sandwich_free(L,[x,y],5).
L = [x, y, y, x, x] ;
L = [x, x, y, y, x] ;
L = [y, y, x, x, y] ;
L = [y, x, x, y, y] ;
false.
```

"?-" is the prompt; the next four lines are the results, and "false" indicates that there are no more answers. (The order of the results is lexicographic, if you read each result *from right to left*.)

If you ask for the sandwich-free words of length 6 over the same alphabet, you get 0 results:

```
?- sandwich_free(L,[x,y],6).
false.
```

Here's a sandwich-free word of length 500 over a 3-letter alphabet:

```
?- sandwich_free(L,[x,y,z],500).
L = [y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, z, x, x, y, y, x, z, y, x, x, y, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x]
...
```

You can ask for the sandwich-free words of any length over a given alphabet:

```
?- sandwich_free_peano(L,[x,y],N).
L = [],
N = zero ;
L = [x],
N = s(zero) ;
L = [y],
N = s(zero) ;
L = [x, x],
N = s(s(zero)) ;
L = [y, x],
N = s(s(zero)) ;
L = [x, y],
N = s(s(zero)) ;
L = [y, y],
N = s(s(zero)) ;
L = [y, x, x],
N = s(s(s(zero)))
...
```

(Technical limitations in Prolog required me to write a separate version of `sandwich_free`

using Peano numerals, when you're passing in a number not already instantiated as a constant.)

You can also use it to check whether a given list is sandwich-free:

```
?- sandwich_free_peano([x,y,z,z,y],[x,y,z],_).
true ;
false.
```

(The answer is true; false just indicates no more answers.)

Here's a plot of length vs. the number of square-free and sandwich-free words of that length over a 3-letter alphabet. The growth appears to be **exponential**:

The query which generated the data points was

```
?- numlist(0,23,L),maplist(how_many_sandwich_free_alphabet_3,L,XS).
```

The data points on the graph are:

- Square-free: 1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264,
342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418 (OEIS A006156)
- Sandwich-free: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008,
1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428,
86688, 128592 (not in the OEIS at this time)

I find this compelling evidence that there are arbitrarily long three-halves-free words, indeed exponentially many as a function of length. It also seems very likely that infinitely long three-halves-free words exist.

**Edit:**

Here's some interesting new data: Say that a sandwich-free word is "extensible" if you can add one more letter to the front of it to get another sandwich-free word. Most sandwich-free words are extensible. An example of one that is not:

```
_, y, y, x, x, y, z, z, x, x, z, y, y, x, x
```

Try to fill in the blank at the front.

More generally we can talk about "$k$-extensible" sandwich-free words, by which I mean "$k$-extensible but not $(k+1)$-extensible". Now here's a plot of how many non-extensible and 1-extensible words there are of particular lengths:

(Data: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008, 1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428, 86688, 128592, 190512, 282492, 418680, 620208, 919044, 1362456, 2012940; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 72, 72, 144, 396, 252, 396, 720, 1044, 1440, 2376, 3456, 5040, 7524, 11088, 16272, 26604, 36864; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36, 36, 72, 108, 180, 720, 540, 468)

AA, or less triviallyAABCandABCABC, counterexamples? Or am I misunderstanding something? $\endgroup$ – Peter LeFanu Lumsdaine Apr 5 '15 at 11:29Zimin word) is unavoidable, but the difference in my case is that $|A|=|B|$. $\endgroup$ – Joseph O'Rourke Apr 5 '15 at 18:19