This week the #puzzle is: Can You Crack the Roman Code? #combinations #recursion (Link at the bottom.)

You are breaking into a vault that contains ancient Roman treasure. The vault is locked, and can be opened via a modern-day keypad. The keypad contains three numerical inputs, which are (of course) expressed using Roman numerals: “I,” “II,” and “III.”

It’s a good thing your accomplice was able to steal the numerical key code to the vault. Earlier in the day, they handed you this code on a scroll of paper. Once at the keypad, you remove the scroll from your pocket and unfurl it. It reads: “IIIIIIIIII.” That’s ten vertical marks, without any clear spacing between them.

With some quick mental arithmetic, you realize the combination to unlock the door could be anywhere from four digits long to 10 digits long. (Or is it IV digits to X digits?) How many distinct combinations are possible? If two combinations use the same numbers but in a different order, they are considered distinct.

And for extra credit:

Having successfully hacked your way through the first keypad, the door opens to reveal a second door with yet another keypad that has eight numerical inputs: “I,” “II,” “III,” “IV,” “V,” “VI,” “VII,” and “VIII.”

You were expecting this, which is why your accomplice had handed you a second scroll of paper. You unfurl this one as well, hoping they remembered to add spaces between the numbers.

No such luck. This paper reads: “IIIVIIIVIIIVIII.” That’s 15 characters in total. How many distinct combinations are possible for this second door?

Highlight to reveal (possibly incorrect) solution:

Tribonacci numbers Program

What do we know?

1. If the scroll had 1 * I, there would be 1 solution.
2. If it had 2, there would be 2 solutions, (I,I) and (II).
3. If it had 3, there would be 4 solutions, (I,I,I), (II,I), (I,II) and (III).
4. If it had 4, there would be 3 cases:
   • All the solutions for 3 * I with (I) added.
   • All the solutions for 2 * I with (II) added.
   • All the solutions for 1 * I with (III) added.
5. So this should be 4 + 2 + 1 = 7 solutions.
6. In general it’s the case, that the number of solutions f(n) = f(n-1) + f(n-2) + f(n-3).
7. These are actually the tribonacci numbers.
8. f(10) = a(12) = 274.

Just to make sure, I also wrote a recursive program to do the actual search through the tree of possibilities. Same answer.

And for extra credit:

Spreadsheet

Good thing I wrote that program! I can simply use it again. It says there are 4000 solutions.

Just to make sure, I also made a spreadsheet, counting in another way. Same result. I am happy.

***

Last week I actually didn’t do that well. I made a lot of assumptions, and some of them were wrong. In both puzzles my pass no. 2 didn’t correspond with the official solution. I’ve discovered, that for the fiddler this happened, because I made a mistake in my calculations. The area of my tilted 2nd pass is not 1.0472, but 0.7585. Oops.

***

Can You Crack the Roman Code?