MathDB
Find the number of "balanced" n-strings

Source: Indian IMO Training Camp 2007-ST 2 P3

March 5, 2011
Putnamabsolute valuecombinatorics unsolvedcombinatorics

Problem Statement

Given a finite string SS of symbols XX and OO, we denote Δ(s)\Delta(s) as the number ofX′X's in SS minus the number of O′O's (For example, Δ(XOOXOOX)=−1\Delta(XOOXOOX)=-1). We call a string SS balanced if every sub-string TT of (consecutive symbols) SS has the property −1≤Δ(T)≤2.-1\leq \Delta(T)\leq 2. (Thus XOOXOOXXOOXOOX is not balanced, since it contains the sub-string OOXOOOOXOO whose Δ\Delta value is −3.-3. Find, with proof, the number of balanced strings of length nn.
Back to ProblemsView on AoPS