MathDB

Putnam 1996 B5

Source:

June 6, 2014

Putnamfloor functioncollege contests

Problem Statement

Given a finite binary string

S

of symbols

X,O

we define

\Delta(S)=n(X)-n(O)

where

n(X),n(O)

respectively denote number of

X

's and

O

's in a string. For example

\Delta(XOOXOOX)=3-4=-1

. We call a string

S

\emph{balanced} if every substring

T

of

S

has

-2\le \Delta(T)\le 2

. Find number of balanced strings of length

n

.

Back to Problems View on AoPS