Let \(S = \langle s_1, s_2, s_3, \dots \rangle\) be a string of \(N\) digits (0 through 9) with the following property:

For any three distinct digits \(a, b, c\), there is an index \(1 \leq n \leq N-2\) such that \(\{s_n, s_{n+1}, s_{n+2}\} = \{a, b, c\}\). In other words, every set of three distinct digits occurs as a substring in \(S\) but not necessarily in that order.

What is the length \(N\) of the shortest string \(S\) with this property?

*Note*: It is not difficult to estimate a lower bound for \(N\); but there is no guarantee that a string of that length actually exists...

**Examples and Assumptions**

A set of three digits may occur as a substring of \(S\) more than once.

In the string `abceabdeacdebcd`

each subset of the three letters \(\{a\dots e\}\) occurs at least once. The subset \(\{b, c, e\}\) occurs twice, once as `bce`

near the beginning and once as `ebc`

near the end.

×

Problem Loading...

Note Loading...

Set Loading...