MathDB
Two types of words formed by the letters a,b,c

Source: Romanian TST 1998

April 23, 2011
functionsymmetrycombinatorics proposedcombinatorics

Problem Statement

A word of length nn is an ordered sequence x1x2…xnx_1x_2\ldots x_n where xix_i is a letter from the set {a,b,c}\{ a,b,c \}. Denote by AnA_n the set of words of length nn which do not contain any block xixi+1,i=1,2,…,n−1,x_ix_{i+1}, i=1,2,\ldots ,n-1, of the form aaaa or bbbb and by BnB_n the set of words of length nn in which none of the subsequences xixi+1xi+2,i=1,2,…n−2,x_ix_{i+1}x_{i+2}, i=1,2,\ldots n-2, contains all the letters a,b,ca,b,c. Prove that ∣Bn+1∣=3∣An∣|B_{n+1}|=3|A_n|.
Vasile Pop
Back to ProblemsView on AoPS