## Binary strings

From the 2010 Australian Maths Challenge:

There are sixteen different ways of writing four-digit strings using 1s and 0s. Three of these strings are 1010, 0100 and 1001. These three can be found as substrings of 101001. There is a string of nineteen 1s and 0s which contains all sixteen strings of length 4 exactly once. If this string starts with 1111, what are the last four digits?

This took me a little while, playing around with the location of digits in the long number and how many four-digit strings they contributed to, before I stumbled upon a solution.

The number must begin 11110, in which the strings 1111 and 1110 both appear. Now, the string 0111 must appear somewhere. If it is followed by a 1, we have a repeat of the string 1111. If it is followed by a 0, then we have a repeat of the string 1110. It follows that the string 0111 isn’t followed by anything at all, and so must be at the end. Thus the final four digits are 0111.

A couple of things strike me when considering this problem. Firstly, there is no need to actually construct the whole nineteen digit string. Secondly, the solution is stunning in its brevity, when on first glance it was conceivable that a lot more work would be required. A brilliant problem indeed.