String Of Digits
Let be a string of digits (0 through 9) with the following property:
For any three distinct digits , there is an index such that . In other words, every set of three distinct digits occurs as a substring in but not necessarily in that order.
What is the length of the shortest string with this property?
Note : It is not difficult to estimate a lower bound for ; 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 more than once.
In the string
abceabdeacdebcd
each subset of the three letters
occurs at least once. The subset
occurs twice, once as
bce
near the beginning and once as
ebc
near the end.
The answer is 122.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The number of unordered subsets of three digits is ( 1 0 3 ) = 1 2 0 . In order for there to be 120 distinct substrings of length 3 in S , it should contain at least 122 characters. Thus N ≥ 1 2 2 .
This is the easy part. Much harder is to prove that a string of length 122 with these properties actually exists. Logically the most convincing proof is to give a concrete example. I found
Every set of three digits occurs exactly once as a subset of this string. (I verified using an Excel spreadsheet.) Thus N = 1 2 2 is the solution.
Bonus : How did I find this string? It consists of 10 groups of 12 digits, each based on the string
012469125893Add 7 (mod 10) to each digit in this group to find the next 12 digits; then add 4 (mod 10); and so on. Let's call this "translation". Finally, attach the first two digits to the end to complete the cycle.Finding this generating string was an interesting puzzle; I found a guiding algorithm to construe it, which I will not explain here.
Graph theory : The question whether the lower bound estimate N = ( 1 0 3 ) + 2 can actually be obtained is equivalent to finding a Hamilton path in the graph consisting of all sets of three digits, in which two sets are connected by an edge iff they have two digits in common. This graph consists of 120 vertices and 1260 edges; each vertex has order 21. My solution proves that a Hamilton cycle exists in this particular graph.
Challenge : What is the solution if the digit
0is no longer allowed? The theoretical minimum is N ≥ 8 4 + 2 , but a cyclic solution as the one given here has N = 9 0 + 2 digits; it is redundant, containing each of the sets { 1 , 4 , 7 } , { 2 , 5 , 8 } , { 3 , 6 , 9 } three times. (It is easy to see why!) My conjecture is that a solution with N = 8 4 + 2 does not exist, but I would love to proven wrong; or right!