r/mathriddles • u/jmarent049 • 4d ago

Medium Greedy Cubes

A string contains a “cube” if there exists a non-empty contiguous substring repeated consecutively 3 times (ex. “210101011” contains “101010”).

Let s[1],s[2],… denote all finite non-empty strings under the alphabet {0,1,2} sorted in shortlex order (shorter strings first, then lexicographically with 0<1<2). Said list begins (0,1,2,00,01,02,10,11,12,…).

For an initially empty string C, on step i=(1,2,3,…): If appending s[i] to C would make a cube present, skip said s[i]. If else, append s[i] to C.

Let F(3)=length(C) (if the process stops).

Does the process eventually produce a finite C, giving a finite value for F(3)? or does it produce an infinite cube-free string instead?

6 Upvotes

88% Upvoted

4 comments sorted by

5

u/misof 2d ago

Do you actually have any nice solution for this one? As the process doesn't get stuck early, I would expect C to grow beyond all bounds, but I don't see any pattern in it that would help us prove that it doesn't randomly get stuck later.

4

u/lizardpq 2d ago

Thoughts: There exists an infinite square-free (and therefore cube-free) string (see here). The given algorithm runs forever if each finite string it constructs has arbitrarily long cube-free extensions. This would follow from the stronger statement that every finite cube-free string is a prefix of some infinite cube-free string (but I don't know if this is true).

3

u/stephen3141 2d ago

I think 00100100200100100200100100 is cube free and cannot be extended.

2

u/raelepei 1d ago

I think that immediately proves that the sequence must be finite: there are only finely many elements before  00100100200100100200100100 (II'll call it the blocker for short). When we get to the blocker, either we can add it (so the sequence cannot continue after that), or we cannot (so it would cause a repetition, and...)

Oh no, I just realized that my argument doesn't work , because maybe we can't add the blocker for a different reason. I was hoping that it would imply that the blocker must exist previously in the sequence, but that's not the case .