Numbers are not interesting. Yet, someone think that it is interesting to put a definition on everything. Today, let’s take a look at this slightly annoying Interesting Number puzzle.
Here comes the definition: numbers are considered interesting if and only if:
2013, for example, is considered interesting. Of course, when there are only four digits, there are other equally interesting numbers: 2301 and 2031.
And this raises us the question: given as the number of digits, please count the number of interesting numbers . That means when , .
Well, feel free to play around in this spoiler-free area:
Also, before you accidentally peek into the answer, please take a look at this beautiful flamingo:
Alright. Now that you’ve tried (did ya?) and appreciated the flamingo (yeah you did), you must be eager to know the answer! Well me too! This puzzle is said to be easier if you know about Dynamic Programming (aka DP). As Wikipedia said, it is both a mathematical optimization method and a computer programming method. It works by simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Our puzzle could also be solved in this way.
Now that’s a pretty good question. But first, let’s look at it from a recursive angle: