Thread: IBM July 2020
View Single Post
Old 2020-08-28, 14:28   #6
0scar
 
Jan 2020

101002 Posts
Default 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
0scar is online now   Reply With Quote