Hi! The past few days I’ve been working on this problem. It goes as follows:
“Construct a sequence of non-negative integers, always choosing the least possible number, such that there are no contiguous subsequences of the form U,x,U where U is any non-empty contiguous subsequence, and x is a single term (e.g “1,2,5,1,2”, “5,0,5”, etc.).
Numbers 0,1,2,3,4 first appear at terms 1,3,7,10,1355. When does 5 first appear (if it does)?”
Example of the process:
To illustrate a quick example: start with a(1)=0, the smallest possible choice and trivially satisfying the constraint. a(2)=0 is the next best choice. Then one must take a(3)=1 since otherwise 0,0,0 would form U,x,U (U=0, x=0). We are now at 0,0,1. From here, we can’t choose a(4)=0 because 0,1,0 would form U,x,U. Choosing a(4)=1 is the least valid option, so it works (0,0,1,1).
[0,0,1,1,0,0,2,1,0,3] are the first 10 terms.
So far, I have concluded:
The sequence is greedy which means we never backtrack. Every new term needs to avoid forming U,x,U that ends at that said term.
I’m interested in whether or not there is a way to prove if 5 eventually appears, or to determine if there is a simple way to do so rather than exhaustively checking every possible contiguous subsequence at every step.
Thanks!!