# Shortest sequence containing at least one of every pair, creating “valid XML”

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:

1. The substring tt does not occur.
2. Every possible unique pair of symbols except for tt occurs at least once.
3. The string begins with ( and ends with ).
4. The string contains the same number of ( and ).
5. 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?)