Kimball Martin and David Whitehouse
In [MW], Martin and Whitehouse formulated the famous 3-letter problem which asks the following. Can you find a three-letter word (in the English language, without aid of a computer) such that any permutation of the letters also results in a word? This is the most interesting case of the similarly defined n-letter problem, at least at present, as the following results indicate.
Theorem 1 ([MW]). Suppose the n-letter problem has a solution. Then n is rational. Moreover, assuming the Axiom of Choice, n is a positive integer.
Theorem 2 ([MW2]). The 1-letter problem has a solution.
Theorem 3 ([MW]). The 2-letter problem has a solution. Examples of such solutions include "NO", "AM" and "ME".
It is evident that for n large, the n-letter problem has no solution. This can be easily seen from the fact that there are no words of length > 45. (The Germans seem to have us there!) In fact, we can do considerably better than that.
Theorem 4 ([MW]). Under the Continuum Hypothesis, the n-letter problem has no solution for n > 3.
Martin and Whitehouse then devoted considerable time to the search for a solution of the 3-letter problem. They give an argument which seems to yield that there is no word with a repeated letter or with two vowels that can solve the 3-letter problem. In fact, after much disappointed searching, they were led to the following (now widely believed)
Conjecture ([MW]). The 3-letter problem, sadly, has no solution.
Remarks:
1) If you counted exclamations, "HOO" would be a solution. "HOO" and "OOH" are verbs, while "OHO" is merely an exclamation. Exclamations obviously don't count, even if they are in the Oxford English Dictionary (OED), as I could exclaim "XBQ" and all its permutations had I the lingual dexterity.
2) If the ligature 'AE' ever turns into the two letters 'A' and 'E', then "TEA" will be a solution to the 3-letter problem with the help of the Scots (see below).
A proof at present, since the aid of a computer is not allowed, seems beyond the reach of normal human capabilities (and desire). Even with the aid of a computer, the justification of the adverb "sadly" in the conjecture seems elusive. In the present paper, we propose a more general problem for which interesting partial results seem more obtainable.
The generalized n-letter problem is the following. Consider the set W(n) of English words of length n (as recorded by the Oxford English Dictionary, 2nd or new ed., if you wish to be precise). Consider a word w of length n. There are n! ways to permute the letters of w. [If you don't know what a factorial is, go here.] Let p(w) be the number of such permutations which result in English words. Let a(w) be the number of distinct anagrams of w (including w itself). These will be different if w has repeated letters. Let P(n) be the maximum possible p(w) and A(n) be the maximum possible a(w). Can you find words w and x (without the aid of a computer) such that p(w)=P(n) and a(x)=A(n)?
It is obvious that the classical n-letter problem is solvable if and only if P(n)=n!. In this case a solution for the n-letter problem also solves the generalized n-letter problem. Hence for n=1 or 2, we have P(n)=A(n)=n!=n. It may be interesting to determine for which n the value of A(n) is different from that of P(n). Note that if there exists w in W(n) with p(w)>n!/2, then P(n)=A(n). Below we exhibit a three-letter word with p(w)=4, hence P(3)=A(3).
Before we state the known results, let us list a few other related questions of interest.
1. For which n is P(n) maximum? A(n)? I propose a betting pool.
2. Given n, what is the the best you can do for p(w) and a(w) among words w not containing an s?
3. As a sort of converse, what is the longest word w with no sub-anagrams, i.e., such that no subset (not necessarily proper) of the letters can be made to form a different word? What if you require that w has no repeated letters?
Here is a list of examples for various n which give the greatest known values for p(w) and a(w). Please contact me with any new results. Attributes to other sources will be given in brackets. I will try to keep this list as current as possible.
n=3
p(TEA)=a(TEA)=4: TEA, EAT, ATE, ETA [MW] ("TAE" is listed as a Scottish form for "TOE"; and the ligature 'AE' followed by 'T' is an obscure variant of "EAT" meaning food, is an obscure form of "AT," and also means "of or at the age of.")
If you believe in obscure variants, we also have p(LIE)=a(LIE)=5: EIL, LEI, ILE, LIE, ELI
n=4
p(MEET)=p(EPEE)=6: MEET, METE, TEEM x 2, EPEE x 3!
p(STOP)=a(STOP)=6: STOP, SPOT, TOPS, POTS, POST, OPTS
n=5
p(SPEAR)=a(SPEAR)=8: SPEAR, SPARE, PARSE, PARES, PEARS, RAPES, REAPS, REPAS
n=6
p(PEEWEE)=24: PEEWEE x 4!
n=???
p(Mississippi)=4!*4!*2
Longest known word with no sub-anagrams: SYZYGY
With no repeated letters: CRWTH (it's also the longest word I know with no vowels)
Kimball Martin
kimball.martin@ou.edu
Last Updated:
Tue Mar 8 14:57:50 EST 2005