MathDB
Problems
Contests
International Contests
Rioplatense Mathematical Olympiad, Level 3
2019 Rioplatense Mathematical Olympiad, Level 3
3
3
Part of
2019 Rioplatense Mathematical Olympiad, Level 3
Problems
(1)
Dog dictionary
Source: Rioplatense Olympiad L3 2019
12/10/2019
In the dog dictionary the words are any sequence of letters
A
A
A
and
U
U
U
for example
A
A
AA
AA
,
U
A
U
UAU
U
A
U
and
A
U
A
U
AUAU
A
U
A
U
. For each word, your "profundity" will be the quantity of subwords we can obtain by the removal of some letters. For each positive integer
n
n
n
, determine the largest "profundity" of word, in dog dictionary, can have with
n
n
n
letters. Note: The word
A
A
U
U
A
AAUUA
AA
UU
A
has "profundity"
14
14
14
because your subwords are
A
,
U
,
A
U
,
A
A
,
U
U
,
U
A
,
A
U
U
,
U
U
A
,
A
A
U
,
A
U
A
,
A
A
A
,
A
A
U
U
,
A
A
U
A
,
A
U
U
A
A, U, AU, AA, UU, UA, AUU, UUA, AAU, AUA, AAA, AAUU, AAUA, AUUA
A
,
U
,
A
U
,
AA
,
UU
,
U
A
,
A
UU
,
UU
A
,
AA
U
,
A
U
A
,
AAA
,
AA
UU
,
AA
U
A
,
A
UU
A
.
combinatorics