Ponder This Challenge - June 2005 - Almost balanced A/B strings

Ponder This Challenge:

Puzzle for June:

This puzzle is based on a suggestion by Aditya K Prasad,
(Further attribution will be given with the solution.)

Consider a string S of N symbols, selected from the set {A,B}.
In any consecutive substring of S,
the number of A's differs from the number of B's by at most 3.
How many such strings S are there (as a function of N, in closed form)?

We are not accepting solutions for this month.

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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:
  https://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

Solvers

• Raicho Tchalkov (06.01.2005 @12:56:28 PM EDT)
• Eugene Vasilchenko (06.01.2005 @02:51:21 PM EDT)
• David Friedman (06.01.2005 @03:36:32 PM EDT)
• Vlad Gotlib (06.01.2005 @10:01:20 PM EDT)
• Huicheng Guo (06.01.2005 @11:47:38 PM EDT)
• Max Alekseyev (06.02.2005 @02:57:58 AM EDT)
• Luke Pebody (06.02.2005 @05:57:06 PM EDT)
• David McQuillan (06.02.2005 @07:51:25 AM EDT)
• Brian J. (06.02.2005 @10:00:17 AM EDT)
• Bart De Vylder (06.02.2005 @10:37:36 AM EDT)
• Matteo Slanina (06.02.2005 @03:05:55 PM EDT)
• Steven Noble (06.02.2005 @03:29:22 PM EDT)
• Tomas G. Rokicki (06.02.2005 @05:27:33 PM EDT)
• Patrick J. LoPresti (06.02.2005 @06:28:14 PM EDT)
• Jan Kuipers (06.02.2005 @09:33:03 PM EDT)
• Mark Pilloff (06.02.2005 @09:37:24 PM EDT)
• Dan Dima (06.02.2005 @07:40:20 PM EDT)
• Machine (06.03.2005 @02:07:00 AM EDT)
• Chang-SeoPark (06.03.2005 @06:11:24 AM EDT)
• Robert Benea (06.03.2005 @06:26:41 AM EDT)
• Daniel Bitin (06.03.2005 @12:50:05 PM EDT)
• Yong Liu (06.03.2005 @02:57:00 PM EDT)
• Abishek K (06.04.2005 @12:24:18 AM EDT)
• Kennedy (06.04.2005 @12:57:22 AM EDT)
• Alvaro Martinez Echevarria (06.04.2005 @10:02:12 AM EDT)
• Vladimir Sedach (06.04.2005 @11:27:31 AM EDT)
• Todd G. Will (06.04.2005 @02:11:43 PM EDT)
• Clive Tong (06.04.2005 @04:13:09 PM EDT)
• Franco Bassi (06.05.2005 @04:39:25 PM EDT)
• Vijay Tennety (06.06.2005 @04:45:53 AM EDT)
• Roberto Tauraso (06.06.2005 @06:28:05 AM EDT)
• John Hart (06.06.2005 @12:45:53 PM EDT)
• John Tromp (06.06.2005 @01:16:42 PM EDT)
• Dharmadeep Muppalla (06.07.2005 @02:22:43 AM EDT)
• Dinesh Layek (06.07.2005 @12:52:02 PM EDT)
• William C. Hasenplaugh (06.07.2005 @06:13:08 PM EDT)
• Brad Austin (06.08.2005 @01:01:58 AM EDT)
• Radu Grigore (06.08.2005 @01:41:08 AM EDT)
• Udo Klein (06.08.2005 @02:26:16 AM EDT)
• Patricio Alva (06.08.2005 @11:34:50 AM EDT)
• Guy Srinivisan (06.08.2005 @04:52:11 PM EDT)
• Andre Rzym (06.08.2005 @05:30:29 PM EDT)
• Hao Wu (06.08.2005 @09:51:23 PM EDT)
• Leonardo Liang (06.09.2005 @05:38:02 AM EDT)
• Mike Fee (06.09.2005 @07:09:25 AM EDT)
• Se Kwon Kim (06.09.2005 @10:44:35 PM EDT)
• Balakrishnan V (06.10.2005 @01:56:11 AM EDT)
• Vineet Dwivedi (06.10.2005 @02:32:00 AM EDT)
• Chuck Carroll (06.10.2005 @03:53:57 AM EDT)
• Atilla Eryilmaz and Irem Koprulu (06.10.2005 @08:53:41 PM EDT)
• John Hubenschmidt (06.10.2005 @10:48:03 AM EDT)
• Mayank Bathiya (06.10.2005 @10:48:08 AM EDT)
• Emilio Schiavi (06.10.2005 @06:55:53 PM EDT)
• Youssef Mohammed (06.13.2005 @01:53:44 AM EDT)
• Jose H. Nieto (06.13.2005 @07:55:21 AM EDT)
• Shirish Altekar (06.14.2005 @06:01:11 PM EDT)
• Daniel Chong Jyh Tar (06.15.2005 @07:31:06 AM EDT)
• Dave Biggar (06.16.2005 @09:00:04 AM EDT)
• Srikanth S.M. (06.16.2005 @09:37:46 AM EDT)
• IQSTAR (06.17.2005 @08:03:36 AM EDT)
• Divyesh Dixit (06.17.2005 @01:57:48 PM EDT)
• Peter Mattsson (06.17.2005 @06:29:07 PM EDT)
• Wolf Mosle (06.20.2005 @11:40:17 PM EDT)