Here’s a warm up joke:
Three logicians walk into a bar. The bar tender asks “Do all of you want a drink?”
The first logician says, “I don’t know.”
The second logician says, “I don’t know.”
The third logician says, “Yes!”
The following question went viral on Facebook. It had a sensationalising title: “Primary 5 [11 year old] mathematics question”, which later turned out to be incorrect as it was actually a Secondary 3 [15 year old] maths olympiad question.
I didn’t give much though to this question when I first saw it because I have seen such questions before so it wasn’t something new. But someone shared this with me in a private chat and so I thought might as well write a short blog post about how I solved it.
Continue reading So, about this viral maths birthday problem …
[This was found in my stack of loose notes from May 2013]
Consider the following problems
- Number of plane binary trees with n end points
- Number valid k-ary parenthesis for a string of n characters?
- Sequence of X and Y such that no initial segment of the sequence has more X than Y.
- Number of path P in the (x,y) plane from (0,0) to (n-1,0) using steps (1,k), where k+1 in S or k = -1, with a total of m-1 steps of the form (1,-1) such that P never passes below the x-axis.
- Number of dissections of a convex (m+1)-gon C into n-m regions, each a k-gon, by drawing diagonals that don’t intersect in their interiors
All these problems can be solved by the sequence known as the Catalan number. The first few numbers in the sequence are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
It can be computed using this formula:
Or by the recurrence relation
1/998999 = 1.001002003005008013021034055089 144 233 377 610 ... × 10^-6
I came across this on twitter and I thought it was interesting. The number 1/998999 contains instances of the Fibonacci numbers.
This works by considering the generating function for the series which has the following closed form:
If we let k = 1000, we get the series appearing in blocks of threes in the decimal representation. If we want higher precision, we can just let k be some higher value.
To extend this idea, my friend and I tried to find the fraction that generates a similar series: Lucas series. It is basically Fibonacci series with the first two terms being 2 and 1 instead of 0 and 1.
The generating function is
using x = 1000 like before, we get the fraction
1999000/998999 = 2.001003004007011018029047076 123 199 322 ...
We can also use this method to generate other interesting sequences as well.