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?