Three recursive problems

In my experience, recursion is by far and away the most versatile tool for solving counting problems. In this post we’ll consider three nice such examples, where emphasis will be on the creative application of the recursive approach.

By ‘recursive approach’, we shall mean a collection of three things:

• a sensible parametrisation of any instance of the problem

• a sensible algorithm for deducing the answer of one instance of the problem from those of previous instances (the ordering we use here relies on the parametrisation from above)

• a sufficient collection of answers to ‘base instances’ of the problem, namely such that all others can be deduced via the algorithm from above.

Armed with these, we can (at best) find a closed-form solution of the problem, or (at worst) settle for a reliable inductive method for solving any particular (not unreasonably large) instance of the problem using a computer.

Without further ado, let’s get to the problems.

Problem 1: Digit sum invariants (from Project Euler #290)

Before we continue, it’s worth noting that going through the $10^{18}$ cases is out of the question even for a modern PC. As a rule of thumb, anything that will require more than $10^{12}$ elementary computations will take too long, and even this bound only holds for fast languages such as C++.

A more clever approach is then needed. Accordingly, the idea below is very clever indeed - one of my best.

Imagine for a minute that, given any $n$, we could find information $I(n)$ that has the following three wonderful properties:

• There are relatively few possible values that $I$ can take.
• For any $n$ and any digit $a$, writing $an$ for their concatenation, one can deduce $I(an)$ solely from $I(n)$ and $a$, without making any reference to $n$ itself.
• One can deduce whether $n$ counts towards the solution of our problem solely from $I(n)$.

If we had such a magical $I$, then we claim we'd be able to finish the problem off recursively. Indeed:

• By point 3, all we'd need to do is find the sizes of the $I$-equivalence classes which interest us.
• By point 2, we'd be able to deduce these from the sizes of the $I$-equivalence classes of the seventeen-digit integers, which can in turn be deduced from those of the sixteen-digit integers, etc.
• By point 1, all this can be done relatively quick. This is just there to ensure we don't do something silly like set $I(n)=n$.

Well, as it turns out there is such an I. See if you can spot it yourself before continuing to the solution.

It’s worth mentioning that this solution relies on the fortunate upper bound given in the problem.

Problem 2: Maximising non-attacking centaurs (from Project Euler #554)

This problem is not easy. My solution is linked below. Before continuing to it though, attempt to view the problem through the prism of the recursive approach. Give some thought to the following questions: What should the parameter(s) quantifying each instance of the problem be? How might the inductive algorithm work? What should the base case(s) be?

Having now seen a solution full of rickety casework and careful bookkeeping, one might reasonably ask why I picked this as a model problem for the recursive approach. The answer has to do precisely with the fact the solution is so fiddly, as this demonstrates the versatility of the method! To see this, note what our solution did not do. We did not pick the most natural parametrisation $n$ for our problem instance - in fact, our solution forced us to consider the more general case of a rectangular chessboard, and hence led us to the parameter $(m,n)$ instead.

We also did not find a simple recurrence relation between instances even of the more general rectangular problem; instead, each of the cases we considered for the bottom left centaur (BLC) led us to new problem instances which were fundamentally different from anything we'd seen up to that point. In fact, upon considering the casework for the new BLCs, some of these new instances actually spawned a third generation of hitherto unseen problem instances. This meant we needed to employ an even more elaborate parametrisation, although in the interest of clarity I opted for different parameter families instead.

Despite these difficulties, we also did not lose hope. This is because, in truth, I never would have even attempted working through all the cases without some assurance that, far from descending down an infinitude of increasingly intricate scenarios, there were in fact only finitely many families of problem instances to consider. Such an assurance is far easier to come by (yet hardly less interesting) than a complete solution - for it, one needs to go over their planned solution strategy very abstractly and confirm exceedingly intricate scenarios are avoided.

For instance, it became evident very early in the solution process that a natural approach would be to use casework on the BLC and make heavy use of the outward propagation principle. This leads one from square chessboard instances to two flavours of rectangular ones, and to one flavour of a split-rectangular instance. Each of these, however, only ever splits into smaller versions of instances seen before. Thus the family of problem instances indeed closes, and all that’s left to work out is the details.

Problem 3: Counting tours on a chessboard (from Project Euler #237)

Here, the potential solutions are grouped into families according to what's occurring at the right end of the board. An observant reader will note this problem has the additional benefit of only considering a chessboard of finite height (height 4), which immediately suffices to convince one that the collection of solution families for any particular $n$ is no doubt finite (and bounded above by, say, $2^4$=16.) Thus again the solver can feel secure in knowing his hard work of pursuing cases is sure to result in a solution.

Conclusion

In my opinion, the three problems above exemplify the versatility of the recursive approach.

Problem 1 has an especially pretty parametrisation, while Problems 2 and 3 choose fairly natural such but yield fascinating structures within their ‘induction step’ algorithms.

If you’re ever faced with a daunting counting problem, I recommend pursuing a recursive solution first - it’s remarkable how often this will suffice!