Problem

Source: 2022 RELMO P3

Tags: combinatorics, relmo, revenge elmo



A sequence of moves is performed starting on the three letter string "$BAD.$'' A move consists of inserting an additional instance of the three letter string "$BAD$'' between any two consecutive letters of the current string, to achieve an elongated string. After $n$ moves, how many distinct possible strings of length $3n+3$ can be achieved? For example, after one move the strings "$BBADAD$'' and "$BABADD$'' are achievable. Proposed by squareman (Evan Chang), USA