2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ How much of the answer do you understand? Maybe that could be used as the starting point. $\endgroup$
    – hexomino
    Mar 10 at 12:34
  • $\begingroup$ I've tried to give an answer which restricts to the specific case of $n=5$. Hope this makes it a bit clearer. $\endgroup$
    – hexomino
    Mar 10 at 13:37
  • $\begingroup$ These are square-free words and are called extremal if no letter can be inserted in any position or maximal if no letter can be inserted at the beginning or end. $\endgroup$
    – RobPratt
    Mar 10 at 14:42
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think I understood the answer now. Thanks. But how does one realise that this is how to approach the question ? is it through mathematical induction ? Or does it have it's origin in cryptography or something ? I ask because this method seems very non-intuitive . $\endgroup$ Mar 10 at 14:57
  • 5
    $\begingroup$ @HemantAgarwal In my opinion, the intuition derives from trying smaller examples first. For example, the problem is a lot easier if we are limited to using just a,b. Then, when we add c in the mix, we can actually analyse this fairly rigorously. After that, you may start to see a pattern emerge and then you can try to prove it. Obviously, this comes more immediately to some people than others. You may also want to ask noedne about any intuition they had. $\endgroup$
    – hexomino
    Mar 10 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.