Arrange candies without repeating pattern

Question

The following puzzle had been posted before but I couldn't understand the only answer that was given there, which was by @neodne . So, I created this post asking someone to explain neodne's answer to me. But if you have a method of solving this question that is different to neodne's answer, especially if it is simpler and more intuitive, then also, please do post your answer below.

Link to the original post: Candy Button Paper

And this is the question that was posted in the link above:

Your biggest dream has come true: you have an infinite supply of your favorite five-flavor candy button paper. Unfortunately, you are a very picky eater. In fact, you are so picky that it is physically impossible for you to eat the same flavor pattern twice in a row. For example, if we label the flavors a-e, and you eat aebceb, then it is impossible for you to eat flavor b (can't repeat b) or c (can't repeat ebc) next. But you can eat a, d, or e next.

Question: Is it always possible to eat another candy, regardless of the pattern you've previously eaten? If so, prove it. If not, what is the minimal number of candies you can eat before it is impossible to eat any more, and prove that it is the minimal number.

Answer 1

The answer of noedne generalises the problem for any number of characters but let us instead restrict to the specific problem where we just use $a,b,c,d,e$ (five different characters).

Now, suppose we have a string of characters, $S$, which cannot be extended. This means that adding any of $a,b,c,d,e$ results in a repeating pattern.

Given that we cannot add $a$, this means that $S$ must take the form $S=X_aY_aaY_a$ for some string of characters $X_a$ and some string of characters $Y_a$ (note that either string may have zero characters). Similarly, we must be able to write $S=X_bY_bbY_b = X_cY_ccY_c = X_dY_ddY_d = X_eY_eeY_e$.

If this is confusing, take a look at noedne's original example $S=abacabadabacabaeabacabadabacaba$. We have,
$S=(abacabadabacabaeabacabadabacab)()a()$ so $X_a = abacabadabacabaeabacabadabacab$ and $Y_a$ is empty.
$S = (abacabadabacabaeabacabadabac)(a)b(a)$ so $X_b = abacabadabacabaeabacabadabac$ and $Y_b = a$
$S = (abacabadabacabaeabacabad)(aba)c(aba)$ so $X_c = abacabadabacabaeabacabad$ and $Y_c = aba$.
$S = (abacabadabacabae)(abacaba)d(abacaba)$ so $X_d = abacabadabacabae$ and $Y_d = abacaba$.
$S = ()(abacabadabacaba)e(abacabadabacaba)$ so $X_e$ is empty and $Y_e = abacabadabacaba$

Now suppose we want to make $S$ as short as we possibly can so that it can be represented as $$S=X_aY_aaY_a = X_bY_bbY_b = X_cY_ccY_c = X_dY_ddY_d = X_eY_eeY_e$$ Notice that none of the lengths of the $Y$s can be equal so we can assume $|Y_a| < |Y_b| < |Y_c| < |Y_d|<|Y_e|$ (if this isn't true we can just swap the letters until it is).
For $S$ to be as short as possible it must be the case that $X_e$ is empty (otherwise we just have unnecessary letters at the beginning) so $S = Y_eeY_e$.

Now suppose that the length of $Y_ddY_d$ is greater than the length of $Y_e$, that is, $|Y_ddY_d| > |Y_e|$.
Then $Y_d$ contains $e$ somewhere in it.
This means we can write $Y_d$ as $ZeW$ for some strings $Z$ and $W$ and $Y_ddY_d = ZeWdZeW$.
Furthermore the first $e$ here coincides with the $e$ in $Y_eeY_e$ so we can write $Y_e = WdZeW$ and, thus, $Y_eeY_e = WdZeWeWdZeW$. However, this contains $eWeW$ so it is not possible to have reached this point by eating the candy-button paper following the rules - this is a contradiction.
Hence, $|Y_ddY_d| \leq |Y_e|$.

We can use the same argument to show that $|Y_ccY_c| \leq |Y_d|$, $|Y_bbY_b| \leq |Y_c|$ and $|Y_aaY_a| \leq |Y_b|$.
Given that $Y_aaY_a$ contains at least one character, it follows that $|Y_b| \geq 1$.
In turn, this means that $|Y_c| \geq 3$, $|Y_d| \geq 7$ and $|Y_e| \geq 15$ and finally that $|S| = |Y_eeY_e| \geq 31$

So $31$ characters is the shortest $S$ can possibly be.