Last byte
## String Me Along

Consider the following solitaire or multiperson game that will be called "String Me Along." You are given a collection of *k* distinct letters, for example, A, B, C, and a number *j.* A well-formed string has no repeats of any substrings of length *j.* Such repeats would be called *j-repeats.*

For example, A B C A C C A B has a two-repeat of A B, but

A B C A C C B A has no two-repeat.

If the string is free of *j*-repetitions, but adding any letter from the collection would cause a *j*-repetition, the string is said to be *j-complete.*

For example, let's say that *j* = 2 and the collection is A, B, C. Here is a two-complete string.

A A B B C C B A C A

It is not possible to extend this further because A has already been followed by A, B, and C.

**Warm-Up:** The two-complete string above for A, B, and C was of length 10. Is it possible to get a shorter two-complete string for A, B, and C?

**Solution to Warm-Up:** Here is one example: A B B A C C A A.

**Question:** What is the length of the shortest two-complete string on A, B, C?

**Solution:** The shortest length is six. Here is an example: A A B A C A. As in the example, it is not possible to extend this further because A has already been followed by A, B, and C. Further, any two-complete string in which it is impossible to follow A must both end with an A and must include A B, A C, as well as A A so cannot be shorter than 6.

**End of Solution to Warm-Up.**

A larger *j* gives more possibilities, so the shortest possible string could get longer. But how much longer?

**Challenge:** Find a three-complete string on A, B, C of length 11 or less.

**Figure. A two-complete string is one in which no two-letter subsequence is present more than once, but appending any letter would violate that condition. Would adding the A make this string two-complete?**

**Solution:** Here is one of length 11.

A B C A B B A B A A B

The reason this is complete is that A B has already been followed by C, B, and A. Note that you might think, based on the same reasoning, that

A B C A B B A B A B

is three-complete, but it is not because B A B appears twice so it has a three-repetition already.

This last challenge suggests a game in which players alternate adding letters to the string without causing *j*-repetitions. If some player cannot do so, then that player loses.

**Challenge:** Suppose that in some game, the string so far is

A B C A A C

It is the Player 1's move now. Can either player force the other to cause a two-repetition?

**Solution:** Player 1 should not append A next because C A is already present. Player 1 could append B or C, but appending B would be foolish because then Player 2 could put in A next and then Player 1 would not be able to continue. So, Player 1 puts in C, yielding

A B C A A C C

This forces Player 2 to append B allowing Player 1 to append A, yielding

A B C A A C C B A

Player 2 cannot extend this further, so Player 1 wins.

You are ready for the upstarts.

**Upstart 1:** Is there a three-complete string on A, B, and C of length 10 or less?

**Upstart 2:** Given *k* letters and some *j*, what is the longest *j-complete* string one can get and what is the shortest?

**Upstart 3:** Is there a forced winning strategy for either player for *j* = 2 for *k* >= 2 letters?

**Upstart 4:** Is there a forced winning strategy for general *j* and *k*?

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html

The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.

No entries found