I've got an alphabet consisting of four symbols:
t. The inspiration for them are the four basic types of XML elements: a start tag (like <foo>), an end tag (like </foo>), an empty tag (like <foo/>), and non-markup text (like FOO).
We call a string made up of these symbols valid if it meets the following conditions:
- The substring
ttdoes not occur.
- Every possible unique pair of symbols except for
ttoccurs at least once.
- The string begins with
(and ends with
- The string contains the same number of
- The cumulative count of
(is everywhere greater than the cumulative count of
), except at the beginning and the end.
The question is: What is the length of the shortest valid string?
An extensive brute-force search has yielded valid strings of length 17 (the string
(t((e())eet)()te) is one example) but none of length 16. Rules 1 and 2 mean that there cannot be any valid strings with fewer than 16 symbols. So the question can be rephrased as: Do any valid strings of length 16 exist? If yes, can you give an example? If no, can you prove it?
If rule 3 is omitted, then strings of length 16 are possible, for example