A sequence of letters is considered "valid" if it occurs as a substring of a common English word. For example, "RGRO" is valid because it occurs in the word "undeRGROund."

Find a sequence of four distinct letters such that all 23 non-identity permutations of the sequence are valid.

I did this one by hand, although the problem lends itself easily to a solution by computer search.

It was actually pretty easy to find, with a little thought put into it. I figured it probably had to be two consonants and two vowels, as groups of three consonants or vowels are rather rare in words, let alone groups that have to be found in any different order. The pair of vowels should be ones that work together nicely in either order; the same for the two consonants.

Based on that, the vowels were easy enough to narrow down: AE, AO, EI, EO, EU, IO, IU, and OU seemed to be pretty hard combinations to find in large numbers of words, leaving just AI/IA to work with.

Similary, finding two consonants that work well in either order was pretty simple. I focused on RST first, and decided that TS and SR would be hardest to find as they only appear in compound words or, in the case of TS, at the end of a word. I figured something like RT/TR or PR/RP would work best, as either form can appear in the middle or one end of the word.

I tried AIRT first, and it worked:

  AIRTIME
 WAITRESS
 PARITY
 PARTISAN
 SATIRE
  ATRIUM
  IART
 DIATRIBE
  IRATE
FLIRTATIOUS
GUITAR
 NITRATE
STRAIT
  RATION
VARIATION
MARITAL
CURTAIL
PARTIAL
 STAIR
  TARIFF
  TIARA
  TIRADE
  TRAIL
  TRIAL

Posted by DJ on 2005-01-13 00:48:47