Thread: July 2020 View Single Post 2020-08-28, 14:28 #6 0scar   Jan 2020 31 Posts Spin-off solution The target sequence G(n) = F(n)*F(n+1) satisfies an order-3 homogeneous linear recurrence: G(n) = 2*G(n-1) + 2*G(n-2) - G(n-3), so we need a homogeneous linear system of order at least three to generate it, which means a dictionary of at least three letters. Three letters actually suffice; I found three such solutions. Dictionary 1: {"A": "BC", "B": "AAB", "C": "ABC"}. Dictionary 2: {"A": "AB", "B": "AAAC", "C": "AAC"}. Dictionary 3: {"A": "AB", "B": "AABC", "C": "B"}. In each case, the game starts with letter "A"; letter "C" is always the rarest one, at least for index n>2. Dieter proved a nice closed-form representation for letter-counting functions. Dictionary 1: A(n) = F(n+1)*F(n-2); B(n) = F(n)*F(n-1); C(n) = F(n-1)^2. Dictionary 2: A(n) = F(n)^2; B(n) = F(n-1)^2; C(n) = F(n-1)*F(n-2). Dictionary 3: A(n) = F(n)*F(n-1) + F(n-2)^2; B(n) = F(n)*F(n-1); C(n) = F(n-1)*F(n-2). Dictionary 1 seems the most promising one, as letter "C" occurs slightly more often (by a factor F(n-1)/F(n-2), which converges to the golden ratio phi=1.618...). We can change the three spellings in 2*3*6 = 36 ways. We can replace letters "A","B","C" with letters "I","B","M" in 6 ways. Among the 216 possible variations, I chose the following one: {"M": "IB", "I": "MIM", "B": "IBM"} The game starts with letter "M"; letter "B" is the rarest one for n>2, so the upper bound IBM(n) <= B(n) is sharp. This solution almost reaches such bound: IBM(n) = B(n) if n is odd, IBM(n) = B(n)-1 if n is even. Proof. In each string of the sequence, we can only find the two-letter substrings "BM", "IB", "IM", and "MI". The sequence starts with a one-letter string, so the claim is trivially true for n=1. The given list contains all the two-letter substrings of the chosen spellings, so the claim is also true for n=2. Then, only substrings "BM" and "MI" can arise from a permitted concatenation of spellings: "BM": "IBMIB", "IB": "MIMIBM", "IM": "MIMIB", "MI": "IBMIM", so the claim is also true for every index n>2 by induction. In particular, letter "B" is always preceded by letter "I" and followed by letter "M", unless it occurs at the beginning or at the end of a string, so the lower bound IBM(n) >= B(n)-2 holds. For index n>1, it's easy to check that the first few string characters follow a regular pattern with period 2: IB... -> MIM... -> IB... -> MIM... and the same holds for the last few string characters: ...IB -> ...IBM -> ...IB -> ...IBM so letter "B" never occurs at the begin of a string, but it occurs at the end of even-indexed strings. For the given solution, the ratio IBM(n)/G(n) converges to the value 1/phi^3 ~ 0.236 Last fiddled with by 0scar on 2020-08-28 at 14:32  