1

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, the last four digits are? Interesting Question from the australian mathematics compeititon, not sure of an efficient approach.

Selwyn Liu
  • 45
  • 5
  • 3
    See the diagram here ... https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction ... you need to calculate the next one & then find a Hamiltonian path in that ... & note the last few characters. – Donald Splutterwit Sep 24 '20 at 23:01
  • 2
    If the string is reversed, it has the same property; if every $0$ is changed to a $0$ and every $0$ to a $1$, the string has the same property. Therefore, if the answer to the question is unique, it must be $0000$. – saulspatz Sep 24 '20 at 23:03
  • I had a strong feeling that the answer is $000$, but couldn't come up with the reasoning that @saulspatz so concisely wrote. Could be an answer, but OP hasn't written any thoughts. – Andrew Chin Sep 24 '20 at 23:07
  • 2
    @saulspatz I don't think this is correct, or at least it is not obvious...for two digit strings, for instance, the answer would be $11001$ and every digit is forced given the initial $11$. – lulu Sep 24 '20 at 23:20
  • Yeah, I am not sure – Selwyn Liu Sep 24 '20 at 23:21
  • For three digits the string $1110001011$ works, though I don't know if it is unique or not (given an initial $111$). – lulu Sep 24 '20 at 23:24
  • @lulu: but this does not have the same number of zeros and ones. Saulspatz answer is right as it specified that the string has 19 ones and 19 zeros. – G Cab Sep 24 '20 at 23:28
  • @GCab I don't see that specification (as there are $19$ digits in the string, it is not possible). – lulu Sep 24 '20 at 23:35
  • @GCab , Ah...I read the OP's claim as simply stating that there are $19$ entries in the string. That's what you'd expect ($2^n+(n-1)$ for strings of length $n$). If you go to length $38$ there is no way to avoid a great many repeats. – lulu Sep 24 '20 at 23:38
  • Ah, 19 is the length of the string ?! – G Cab Sep 24 '20 at 23:47
  • @GCab. Right. It's $1111000010011010111$ (by Debruijn methods). Indeed, the final $n$ digits will always be $01^{n-1}$ though I don't see a non-graphical way to see this. – lulu Sep 24 '20 at 23:49
  • @lulu: interesting, didn't know Debuijin method – G Cab Sep 24 '20 at 23:59

2 Answers2

2

Consider the term after the initial string 1111. The only possibilities are 1111, 1110, or nothing. But since 1111 has been used, and this is the start of the sequence, the next term must be 1110.

Consider the term after 0111. The only possibilities are 1111, 1110, or nothing. But since 1111 and 1110 have been used, thus there is no next term. This means that, if a sequence exists, then the sequence must end with 0111.

Notes:

  1. For completeness, we should show that at least one such string exists, which it does.
  2. I don't consider the above a full complete solution. I'm guessing that the referenced AMC is MCQ, so this is sufficient to select the answer.
  3. Of course, there is no preventing the possibility that another string abcd can have no term after it, hence note 1.
Calvin Lin
  • 68,864
  • Is there hint that would think about the terms assoiscated with 0111? – Selwyn Liu Sep 28 '20 at 01:39
  • @SelwynLiu Setting up of the graph correspondence is quite natural (even if you didn't know the theory behind it). From there, 1) Clearly, every node has an 2 out-edges and 2 in-edges (corresponding to adding 1/0 behind/infront). 2) We may guess that a Hamiltonian path/circuit exists (not immediately obvious for directed graphs). However, in general, there are many ways to complete a Hamiltonian path, so what could make this unique? 3) By symmetry of 0 and 1's, it's likely that if a Hamiltonian path exists, then a Hamiltonian circuit exists. (not always true) – Calvin Lin Sep 28 '20 at 17:12
  • Notice that 1111 has an edge that maps back to itself. This makes that part of the Hamiltonian circuit unique, so we must have 0111 -> 1111 -> 1110. (Similarly, in the path, we must have 1000 -> 0000 -> 0001.) 5) This suggests that 0111 must be the unique answer. Let's check the out-edges make sense.
    • – Calvin Lin Sep 28 '20 at 17:15
  • Thank you very much – Selwyn Liu Sep 30 '20 at 04:59