String Of Digits

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...