Communications of the ACM
Last byte
String Me Along
Credit: Getty Images
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?
Footnotes
All are invited to submit their solutions to [email protected]; 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