Can You Crack the Roman Code?

A vault keypad has three buttons: “I”, “II”, and “III” (one, two, or three marks). Pressing a sequence of buttons writes their marks side by side with no separators. The display reads $\texttt{IIIIIIIIII}$ ($10$ marks), and the combination is between four and ten button-presses long. How many distinct combinations could have produced it? (Same marks in a different order count as distinct.)

The Fiddler, Zach Wissner-Gross, June 27, 2025(original post)

Solution

A combination is an ordered sequence of parts from $\{1,2,3\}$ summing to $10$: a composition of $10$ with parts of size $1$, $2$, or $3$. The length constraint is automatic, since $10$ marks need at least $\lceil10/3\rceil=4$ presses and at most $10$ (all ones). So the count is the tribonacci number $$T_n=T_{n-1}+T_{n-2}+T_{n-3},\qquad T_{10}=\boxed{274}.$$

The computation

Count compositions directly: the number of ways to reach $10$ marks is the sum of the ways to reach $10-1$, $10-2$, and $10-3$ marks (the last button pressed). Build that tally up from zero.

dp = [0]*11; dp[0] = 1
for i in range(1, 11): dp[i] = sum(dp[i-k] for k in (1, 2, 3) if i >= k)
print(dp[10])                            # 274

Extra Credit

A second keypad has eight buttons, the Roman numerals $\texttt{I}$ through $\texttt{VIII}$, and the display reads $\texttt{IIIVIIIVIIIVIII}$ ($15$ characters). How many distinct combinations are possible?

Solution

Now the tokens are the Roman strings $\{\texttt{I},\texttt{II},\texttt{III},\texttt{IV},\texttt{V},\texttt{VI},\texttt{VII},\texttt{VIII}\}$, and we count the ways to cut the $15$-character string into such tokens. A left-to-right tally (each position sums the ways from positions a matching token-length back) gives $$\boxed{4000}\ \text{combinations}.$$ (The source’s count is paywalled; this is my own enumeration.)

The computation

Tokenise the actual display string: walk left to right, and at each position add up the ways to have arrived from every earlier position whose intervening characters spell a valid Roman token.

S = "IIIVIIIVIIIVIII"; toks = ["I", "II", "III", "IV", "V", "VI", "VII", "VIII"]
ways = [1] + [0]*len(S)
for i in range(1, len(S) + 1):
    for t in toks:
        if i >= len(t) and S[i-len(t):i] == t: ways[i] += ways[i-len(t)]
print(ways[-1])                          # 4000