I've got an alphabet consisting of four symbols: (, ), e, and 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
(and). - 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 e()t(te)((et))ee.
There must be at least 16 since there must be at least at least $15$ pairs.
To do it with $16$, the first and last character must be the same character (why?,) which is not possible (why?)