13
$\begingroup$

An entry in Fortnightly Topic Challenge #35: Restricted Title 1. Title based on this xkcd.


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$
12
$\begingroup$

The string $abacabadabacabaeabacabadabacaba$ of length $31$ cannot be extended. To illustrate this, it is obtained recursively as follows: $a$, $aba$, $abacaba$, etc., i.e., inserting the next character between two copies of the string.

Now suppose $x_n$ is a shortest string on $n$ characters $a_1,\dots,a_n$ such that for all $i$, $x_n=u_iw_ia_iw_i$ for some strings $u_i$ and $w_i$ (in this problem, we are interested in $n=5$). Choose $u_i$ and $w_i$ such that $|w_i|$ is as small as possible. Without loss of generality, assume that $|w_1|<\dots<|w_n|$. Because $|x_n|$ is minimal, $|u_n|$ must be $0$, i.e., $x_n=w_na_nw_n$.

Suppose that $x_{n-1}$, a shortest string not extendable by $a_1,\dots,a_{n-1}$, is longer than $w_n$. Let $s=w_{n-1}a_{n-1}w_{n-1}$. Because $s$ cannot be extended, $s$ must be at least as long as $x_{n-1}$ and thus longer than $w_n$, so $s$ contains the $a_n$ at the center of $x_n$. Let $w_{n-1}=ya_nz$ such that $y$ and $z$ are strings and $x_n$ ends in $s=ya_nza_{n-1}ya_nz$ where the first $a_n$ coincides with the central $a_n$ of $x_n$ (the central $a_n$ must appear in the first half of $s$ because $|s|\le|x_n|$). Then $w_n$ is everything after this $a_n$, i.e., $za_{n-1}ya_nz$, so $x_n=w_na_nw_n=za_{n-1}ya_nza_nza_{n-1}ya_nz$, but this contains $a_nza_nz$, so you couldn't have eaten $x_n$! Our original assumption that $x_{n-1}$ is longer than $w_n$ was false, so $|x_n|=2|w_n|+1\ge2|x_{n-1}|+1$. Applying this inductively with a base case of $|x_1|=1$, we find that $|x_2|\ge3$, $|x_3|\ge7$, $|x_4|\ge15$, and $|x_5|\ge31$. Hence, the above string achieves the minimum.

$\endgroup$
  • $\begingroup$ Please let me know if anything is unclear/unjustified! $\endgroup$ – noedne May 28 '18 at 22:07
  • $\begingroup$ Remove the last char from your 31 char solution and add eb to obtain abacabadabacabaeabacabadabacabeb. Does this string violate the contraint? $\endgroup$ – Kaya May 28 '18 at 22:26
  • $\begingroup$ Ahh, the shortest "dead-end" string, I see. Ok : ) $\endgroup$ – Kaya May 28 '18 at 22:29
  • 1
    $\begingroup$ @Kaya Oh, perhaps you misinterpreted (as I did at first) as seeking for the longest possible string with no duplicate, which has an answer of infinitely long. $\endgroup$ – noedne May 28 '18 at 22:31
  • $\begingroup$ Yes, I think that + global repeats vs. adjacent repeats were both confusing me at some point. Carry on : D $\endgroup$ – Kaya May 28 '18 at 22:33

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.