Maths Olympiad Prep

Library / /232 of 241

, 2026

Combinatorics Difficulty 4.7 AIME Find the answer Canada

Denali compiles a list of all 5-letter strings that can be formed
using the letters AA, BB, CC, DD, and EE. He lists the strings in alphabetical
order starting with AAAAAAAAAA and
ending with EEEEEEEEEE. How many times
does the letter BB occur in the
2026th string of Denali’s list?

Pick one

Solution

The choice of 55 letters for
each of the 55 positions within the
string gives a total of 55=31255^5=3125
different strings in the list.

Of these strings, 15\frac15 begin
with the letter AA, 15\frac15 begin with the letter BB, and so on to EE.

That is, there are 15×55=54=625\frac15\times5^5=5^4=625 strings that
begin with each of the letters AA
through EE. Thus, the 3×625=18753\times625=1875th string is the last
string that begins with CC (this is
CEEEECEEEE), and the 4×625=25004\times625=2500th string is the last
string that begins with DD (this is
DEEEEDEEEE).

This tells us that the first letter in the 2026th string is DD.

Of the 625625 strings that begin
with DD, 15\frac15 have second letter AA, 15\frac15 have second letter BB, and so on to EE. That is, there are 15×625=125\frac15\times625=125 strings having each
of the second letters AA through
EE. Thus, the 1875+125=20001875+125=2000th string is the last string
that begins with DD and has second
letter AA (this is DAEEEDAEEE), and the 1875+2×125=21251875+2\times125=2125th string is the last
string that begins with DD and has
second letter BB (this is DBEEEDBEEE).

This tells us that the 2001st string is DBAAADBAAA, and the first two letters in the
2026th string are DBDB.

Of the 125125 strings that begin
with DBDB, 15\frac15 have third letter AA, 15\frac15 have third letter BB, and so on to EE. That is, there are 15×125=25\frac15\times125=25 strings beginning
with DBADBA. The 2001st of these is
DBAAADBAAA and the 2000+25=20252000+25=2025th is DBAEEDBAEE. Thus, the 2026th string is the
next string following DBAEEDBAEE which
is DBBAADBBAA, and so the 2026th string
in the list has 22 Bs.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.