Problem of the Month (July 2020)

Ten years ago, I published a set of Replacement Puzzles in GAMES magazine. This got me thinking, what is the longest possible length M of such puzzles with a unique solution, and how does it depend on S (the number of different symbols allowed), L (the maximum length of strings) and R (the number of transformation rules)?

Graph theorists use the word girth to represent the length of the shortest cycle in a directed graph. Given S, L, and R, what is the largest girth G that is possible?

ANSWERS

Clearly if S=1, then M=L–1. (for example, the goal ♥→♥♥♥♥ with the rule ♥→♥♥)

Similarly, if R=1, then M=L–1. (for example, the goal ♠♦♦♦→♠♠♠♠ with the rule ♠♦→♠♠)

If L=1, then M=min{S–1,R–1}. (for example, the goal ♠→♥ with the rules ♠→♣, ♣→♦, and ♦→♥)

M is clearly non-decreasing in S, L, and R. Because of the number of states, M ≤ S+S²+...+S^L–1= (S^L+1–2S+1)/(S–1). This upper bound can always be achieved with R=M, by having every rule move to or from a state with length L.

Here are the longest known puzzles for other cases. Only those for S=2 L=2 have been proved optimal.

Longest Unique Puzzles for S=2

L \ R	2	3	4	5	∞
2	M=3 Goal: ♠♠→♥ Rule #1: ♠→♥ Rule #2: ♥♠→♠ Solution: ♠♠→♥♠→♠→♥	M=5 Goal: ♥→♥♠ Rule #1: ♥→♠ Rule #2: ♠→♠♥ Rule #3: ♠♠→♥♥ Solution: ♥→♠→♠♥→♠♠→♥♥→♥♠	M=5	M=5	M=5
3	M=5 Goal: ♠→♠♠♥ Rule #1: ♠→♥♥ Rule #2: ♥♥→♠♥ Solution: ♠→♥♥→♠♥→ ♥♥♥→♠♥♥→♠♠♥	M=9 Goal: ♥♥♥→♠♠♠ Rule #1: ♥♥→♠♠ Rule #2: ♥♠→♥ Rule #3: ♠→♠♥ Solution: ♥♥♥→♥♠♠→♥♠→♥♠♥→ ♥♥→♠♠→♠♥♠→♠♥→♠♥♥→♠♠♠	M=11 Goal: ♥→♠♥♠ Rule #1: ♥→♥♠ Rule #2: ♠♠→♥♥ Rule #3: ♥♥→♠♠ Rule #4: ♠♥→♠ Solution: ♥→♥♠→♥♠♠→♥♥♥→ ♠♠♥→♠♠→♥♥→♥♥♠→ ♠♠♠→♠♥♥→♠♥→♠♥♠	M=11?	M=13
4	M=7 Goal: ♥♥→♥♥♥♠ Rule #1: ♥♥→♠♠♠ Rule #2: ♠♠→♥♠ Solution: ♥♥→♠♠♠→ ♥♠♠→♥♥♠→♠♠♠♠→ ♥♠♠♠→♥♥♠♠→♥♥♥♠	M=13 Goal: ♠♠♠→♥♥♥♠ Rule #1: ♠♠→♥♥ Rule #2: ♥→♠♥ Rule #3: ♠♠♥→♠ Solution: ♠♠♠→♠♥♥→♠♠♥♥→♠♥→ ♠♠♥→♠♠♠♥→♠♠→♥♥→♥♠♥→ ♥♠♠♥→♥♠→♠♥♠→♠♠♥♠→♥♥♥♠	M=15 Goal: ♥♥♥→♥♠♥♥ Rule #1: ♥→♠♠ Rule #2: ♥♥♠→♠♥ Rule #3: ♠→♥♥ Rule #4: ♥♠♥→♥ Solution: ♥♥♥→♥♥♠♠→♠♥♠→ ♥♥♥♠→♥♠♥→♥→♠♠→♥♥♠→ ♠♥→♠♠♠→♠♥♥♠→♠♠♥→ ♥♥♠♥→♥♥→♥♠♠→♥♠♥♥	M=17 Goal: ♥♠♠→♥♥ Rule #1: ♠♠♥♥→♠♥♠♠ Rule #2: ♥♥→♠♥♠ Rule #3: ♠→♠♥ Rule #4: ♠♥→♥♥ Rule #5: ♥♥♠→♠♥ Solution: ♥♠♠→♥♠♥♠→♥♥♥♠→ ♥♠♥→♥♥♥→♠♥♠♥→♥♥♠♥→ ♠♥♥→♠♠♥♠→♠♥♥♠→♠♠♥→ ♠♠♥♥→♠♥♠♠→♥♥♠♠→ ♠♥♠→♥♥♠→♠♥→♥♥	M=29
5	M=9 Goal: ♠♠♠♥♥→♠♠♠♠ Rule #1: ♠♥→♥ Rule #2: ♥→♠♠♠♠ Solution: ♠♠♠♥♥→ ♠♠♥♥→♠♥♥→♥♥→ ♠♠♠♠♥→♠♠♠♥→ ♠♠♥→♠♥→♥→♠♠♠♠	M=18 Goal: ♥♥♠♠♥→♠♠♥♥♥ Rule #1: ♠♠→♥ Rule #2: ♥♥→♠ Rule #3: ♥♠→♠♠♥ Solution: ♥♥♠♠♥→♥♥♥♥→♥♥♠→ ♥♠♠♥→♠♠♥♠♥→♥♥♠♥→♥♠♠♥♥→ ♥♠♠♠→♠♠♥♠♠→♥♥♠♠→♥♠♠♥♠→ ♥♥♥♠→♥♠♠→♠♠♥♠→♠♠♠♠♥→ ♠♥♠♥→♠♠♠♥♥→♥♠♥♥→♠♠♥♥♥	M=18?	M=19 Goal: ♥♥→♥♠♥♥♠ Rule #1: ♠♥♥→♥♠ Rule #2: ♠→♠♠♥ Rule #3: ♥♥→♥♥♠ Rule #4: ♥♥♥→♠♠ Rule #5: ♥♠→♥ Solution: ♥♥→♥♥♠→♥♥♠♠♥→ ♥♥♠♥→♥♥♥→♠♠→♠♠♥♠→ ♠♠♥→♠♠♥♠♥→♠♠♥♥→ ♠♥♠→♠♥♠♠♥→♠♥♠♥→ ♠♥♥→♥♠→♥♠♠♥→♥♠♥→ ♥♠♠♥♥→♥♠♥♥→♥♠♥♥♠	M=61

Longest Unique Puzzles for S=3

L \ R	2	3	4	5	∞
2	M=3?	M=5?	M=7 Goal: ♠♣→♥♠ Rule #1: ♠→♣ Rule #2: ♣♣→♠ Rule #3: ♣→♥ Rule #4: ♥→♠♠ Solution: ♠♣→♣♣→♠→ ♣→♥→♠♠→♣♠→♥♠	M=9 Goal: ♥♠→♥♣ Rule #1: ♣→♠ Rule #2: ♠→♥ Rule #3: ♥→♣♣ Rule #4: ♠♠→♣ Rule #5: ♥♥→♣♠ Solution: ♥♠→♥♥→ ♣♠→♠♠→♣→♠→ ♥→♣♣→♠♣→♥♣	M=11
3	M=5?	M=9?	M=15 Goal: ♥→♠♣♠ Rule #1: ♠♠→♥♣ Rule #2: ♣♣→♥ Rule #3: ♥♣→♣♠ Rule #4: ♥→♠♠ Solution: ♥→♠♠→♥♣→♠♠♣→ ♥♣♣→♥♥→♥♠♠→♥♥♣→ ♥♣♠→♣♠♠→♣♥♣→♣♣♠→ ♥♠→♠♠♠→♠♥♣→♠♣♠	M=18 Goal: ♥♠♥→♠♠♣ Rule #1: ♥♠→♣♠ Rule #2: ♣♥♠→♣♥♣ Rule #3: ♥→♥♣ Rule #4: ♣→♠ Rule #5: ♠♠→♥ Solution: ♥♠♥→♣♠♥→ ♠♠♥→♥♥→♥♥♣→♥♥♠→ ♥♣♠→♥♠♠→♣♠♠→♠♠♠→ ♥♠→♣♠→♠♠→♥→♥♣→ ♥♣♣→♥♠♣→♣♠♣→♠♠♣	M=38
4	M=7?	M=13?	M=17 Goal: ♣♠♥♠→♣♣♠♥ Rule #1: ♣♠♠→♣ Rule #2: ♥♠→♣♣♥ Rule #3: ♥→♠ Rule #4: ♣→♥♠ Solution: ♣♠♥♠→♣♠♠♠→♣♠→♥♠♠→ ♣♣♥♠→♣♣♠♠→♣♣→♣♥♠→♣♠♠→ ♣→♥♠→♣♣♥→♣♥♠♥→♣♠♠♥→ ♣♥→♥♠♥→♣♣♥♥→♣♣♠♥	M=23 Goal: ♥♥→♣♥♠♥ Rule #1: ♠♥→♥ Rule #2: ♥♥♣→♠♥ Rule #3: ♠→♣♣ Rule #4: ♥→♠♠ Rule #5: ♣♣→♠♥ Solution: ♥♥→♥♠♠→♥♣♣♠→♥♠♥♠→ ♥♥♠→♥♥♣♣→♠♥♣→♥♣→ ♠♠♣→♠♣♣♣→♠♣♠♥→♠♣♥→ ♣♣♣♥→♣♠♥♥→♣♥♥→♣♠♠♥→ ♣♠♥→♣♥→♣♠♠→♣♣♣♠→ ♣♠♥♠→♣♥♠→♣♥♣♣→♣♥♠♥	M=119
5	M=10 Goal: ♣→♣♠♥♥♥ Rule #1: ♣→♣♠ Rule #2: ♣♠♠→♣♥ Solution: ♣→♣♠→♣♠♠→♣♥→ ♣♠♥→♣♠♠♥→♣♥♥→♣♠♥♥→ ♣♠♠♥♥→♣♥♥♥→♣♠♥♥♥	M=18?	M=18?	M=19?	M=362

No loops are possible with R=1.

If S=1 and R≥2, then G=L (for example, with rules ♥→♥♥ and ♥♥♥→♥.

If L=1, R≥2, and S≥2, then G=min{S,R}. (for example, with rules ♠→♣, ♣→♥, and ♥→♠)

G is also non-decreasing in S, L, and R. Because of the number of states, G ≤ S+S²+...+S^L= (S^L+1–S)/(S–1). This upper bound can always be achieved with R=G, by having every rule move to or from a state with length L.

Largest Girth for S=2

L \ R	2	3	4	5
2	G=3 Rule #1: ♠→♥ Rule #2: ♥♥→♠♠ Cycle: ♠♠→♠♥→♥♥→	G=5 Rule #1: ♠→♥♥ Rule #2: ♥→♠ Rule #3: ♠♠→♥ Cycle: ♠→♥♥→♠♥→♠♠→♥→	G=5?	G=5?
3	G=4 Rule #1: ♠→♥ Rule #2: ♥♥♥→♠♠♠ Cycle: ♠♠♠→♠♠♥→♠♥♥→♥♥♥→	G=8 Rule #1: ♠→♥ Rule #2: ♥→♠♠ Rule #3: ♥♥♥→♠ Cycle: ♠→♥→♠♠→♠♥→ ♥♥→♥♠♠→♥♥♠→♥♥♥→	G=9 Rule #1: ♠♠♥→♠♠♠ Rule #2: ♠♠→♥♥ Rule #3: ♥♠→♠ Rule #4: ♥→♠♥ Cycle: ♠♥→♠♠♥→♠♠♠→♥♥♠→ ♥♠→♠♥♠→♠♠→♥♥→♥♠♥→	G=9?
4	G=5 Rule #1: ♠→♥ Rule #2: ♥♥♥♥→♠♠♠♠ Cycle: ♠♠♠♠→♠♠♠♥→ ♠♠♥♥→♠♥♥♥→♥♥♥♥→	G=11 Rule #1: ♠♠♠→♥♥ Rule #2: ♠♠→♥♥♥♥ Rule #3: ♥→♠ Cycle: ♠♠→♥♥♥♥→♠♥♥♥→ ♠♠♥♥→♠♠♠♥→♥♥♥→♠♥♥→ ♠♠♥→♠♠♠→♥♥→♠♥→	G=14 Rule #1: ♠♥♠♠→♥♠ Rule #2: ♥♠♠♥→♥♥ Rule #3: ♠→♠♥ Rule #4: ♥♥→♠ Cycle: ♠→♠♥→♠♥♥→ ♠♠→♠♥♠→♠♥♥♠→ ♠♠♠→♠♥♠♠→♥♠→♥♠♥→ ♥♠♥♥→♥♠♠→♥♠♠♥→♥♥→	G=14?
5	G=6 Rule #1: ♠→♥ Rule #2: ♥♥♥♥♥→♠♠♠♠♠ Cycle: ♠♠♠♠♠→♠♠♠♠♥→♠♠♠♥♥→ ♠♠♥♥♥→♠♥♥♥♥→♥♥♥♥♥→	G=11?	G=14?	G=14?

Largest Girth for S=3

L \ R	2	3	4	5
2	G=3?	G=5?	G=8 Rule #1: ♥→♠ Rule #2: ♠→♣ Rule #3: ♣→♥♥ Rule #4: ♣♣→♥ Cycle: ♥→♠→♣→♥♥→ ♠♥→♠♠→♣♠→♣♣→	G=8?
3	G=4?	G=8?	G=12 Rule #1: ♣→♠ Rule #2: ♠→♣♣ Rule #3: ♠♠♣→♥♣ Rule #4: ♥♠♠→♣ Cycle: ♣→♠→♣♣→ ♠♣→♠♠→♠♣♣→♠♠♣→♥♣→ ♥♠→♥♣♣→♥♠♣→♥♠♠→	G=13 Rule #1: ♣→♥ Rule #2: ♥→♣♣ Rule #3: ♥♥→♠ Rule #4: ♠♠→♣ Rule #5: ♣♣♠→♥♠♣ Cycle: ♣→♥→♣♣→♥♣→ ♥♥→♣♣♥→♥♣♥→ ♥♥♥→♠♥→♠♣♣→ ♠♥♣→♠♥♥→♠♠→
4	G=5?	G=11?	G=14?	G=14?
5	G=6?	G=11?	G=14?	G=14?

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 7/1/20.