June 2005
This puzzle (but not the solution) was adapted from a problem (B-5) in the 1996 Putnam exam.
For any string S, let f(k) be the number of A's among the first k symbols, minus the number of B's among the first k symbols. We know f(0)=0, |f(k)-f(k-1)|=1. The sequence f(0),f(1),...,f(n) has to be confined to one of the following intervals: either [0,3] or [-1,2] or [-2,1] or [-3,0]. This is because the confining interval must contain f(0)=0, and if the interval is of length 4 or greater, say |f(j)-f(k)|=4 with j<k, then in the substring s(j+1),...,s(k), the number of A's and the number of B's differ by 4.
But the sequence might also be confined to a smaller interval, either [0,2] or [-1,1] or [-2,0], in which case it will be counted twice, so we must subtract it. Or it might be confined to an even smaller interval: [0,1] or [-1,0], in which case it will have been counted three times and subtracted twice, so that we're okay. Letting M(i,j)=M(i,j;n) be the number of strings of length n confined to the interval [i,j], the principle of inclusion and exclusion tells us we want M(0,3)+M(-1,2)+M(-2,1)+M(-3,0)-M(0,2)-M(-1,1)-M(-2,0).
To calculate M(i,j;n) we use recurrence relations. We have the initial conditions M(0,3;0)=M(-1,2;0)=1. M(0,3;n)=M(-3,0;n) and M(-1,2;n)=M(-2,1;n), by symmetry. M(0,3;n)=M(-1,2;n-1): the first element must be "A", and the ensuing string must be one of those counted by M(-1,2;n-1). M(-1,2;n)=M(-2,1;n-1)+M(0,3;n-1): the first element can be "A", and the rest of the string would be one of those counted by M(-2,1;n-1), or the first element can be "B", and the rest of the string would be one of those counted by M(0,3;n-1). Substituting the earlier identities into the last one, we find M(-1,2;n)=M(-1,2;n-1)+M(-1,2;n-2), a relation satisfied by the Fibonacci numbers. Along with the initial conditions, we find M(0,3;n)=M(3,0;n)=F(n+1), M(-1,2;n)=M(-2,1;n)=F(n+2), where we take as the Fibonacci numbers
F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2), F(k)={ ((1+sqrt(5))/2)**k - ((1-sqrt(5))/2)**k } / sqrt(5).
M(0,2;n)=M(-1,1;n)=M(-2,0;n)=1.
M(0,2;n)=M(-2,0;n) by symmetry.
M(0,2;n)=M(-1,1;n-1) as before.
M(-1,1;n)=M(0,2;n-1)+M(-2,0;n-1) as before.
The solution is
M(0,2;n)=2**[n/2] where [x] is the greatest integer in x.
M(-1,1;n)=2**[(n+1)/2].
Putting it together, our answer is:
M(0,3)+M(-1,2)+M(-2,1)+M(-3,0)-M(0,2)-M(-1,1)-M(-2,0)
= F(n+1) + F(n+2) + F(n+2) + F(n+1) - 2**[n/2] - 2**[(n+1)/2] -2**[n/2]
= 2F(n+3) - 2**[(n+2)/2] - 2**[(n+1)/2].
Max Alekseyev pointed out that the sequence is in OEIS:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A027557
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com