So, about this viral maths birthday problem …

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.

math1e

Continue reading So, about this viral maths birthday problem …

Advertisements

Interesting sequence catalan

[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:

equation

 

Or by the recurrence relationpasted_image001

 

 

 

998999 and fibonacci numbers

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.

How to tell the day of the week of any date

During my national service stint I had a friend who was very good at maths. One day, one of the sergeants wanted to test how good my friend was. He asked my friend to find out the day of the week which he will ORD (the day he ends his service) on. It took my friend approximately 10 seconds to give the answer. Not convinced, the sergeant used his phone to check and was absolutely amazed at his accuracy. Coming from a strong maths background, I of course knew how the trick was done. But to a layman, this is a very impressive trick.

Inspired by the Arthur’s Benjamin performance in this video http://www.ted.com/talks/arthur_benjamin_does_mathemagic.html and the performance of the man himself at one of the talks held at Cambridge, I decided to write this entry.

How to tell the day of the week of any date.

Most maths major would scream “modulus seven!” That is correct, it is not too difficult to figure out how it is done, but being able to perform it quickly is a skill and I’m going to talk about a way of making it easy to perform this feat.

Basic idea: (Year code + Month code + Date code) mod 7 = Day code

Year code

Year code is derived by the following formula:

(year after the base century + no. of leap years) + Century code mod 7

Century code is the sequence 5 3 1 6 5 3 1 6 … starting from 1600. (It doesn’t make sense to go before 1600 since the Gregorian calendar system was only established in 1582 and it was not adopted in England and its colonies until 1752). So year 1600 has year code 5, year 1700 has year code 3 etc. One can think about it as looking at the first 2 digit of the year and finding the remainder when divided by 4 (modulo 4), then it is easy to see remainder 0 gives year code 5, remainder 1 gives 3 etc. Another easy way to remember this is that it is the odd numbers 5, 3, 1, and the last number is just an anomaly.

Let’s now focus on the 21st century. Year 2000 has century code 5

Examples:

  • 2013: (13 + floor(13/4) + 5) = 0 mod 7
  • 1990: (90 + floor(90/4) + 6) = 6 mod 7
  • 1888: (88 + floor (88/4) + 1) = 6 mod 7

Month code

In his video, Arthur described a way to remember the month code, and I shall describe his technique.

Jan 1 Apr 0 Jul 0 Oct 1
Feb 4 May 2 Aug 3 Nov 4
Mar 4 Jun 5 Sep 6 Dec 6

Note that if one looks at the numbers down the columns, 144 = 12 square, 25 = 5 square, 36 = 6 square, 146 = 12 square + 2. While the the last number is an anomaly, it is not too difficult to remember since there is only one anomaly.

A slight complication when dealing with leap years. (A quick recap: leap years are years divisible by 4 but not divisible by 100 unless it is divisible by 400.) In a leap year, the year code of Jan and Feb is reduced by 1. (This is because of over counting in the year code as an additional 1 was added by the leap year.)

Examples:

  • June 2013: 5 + 0 = 5
  • Jan 1990: 1 + 6 = 0
  • Jan 1888: 0 + 6 = 6

Date code

This is very straight forward. It is just the remainder of the day of the month when divided by 7. (or day of the month mod 7)

Day code

This is also another straight forward calculation. Monday correspond to 1, Tuesday to 2, etc… Sunday to 0.

Putting it all together

The formula says it all.

Examples:

  • Jun 14 2013: 0 (year) + 5 (month) + 14 (day) = 5 mod 7 == Friday
  • Jan 24 1990: 6 (year) + 1 (month) + 24 (day) = 3 mod 7 == Wednesday
  • Jan 24 1888: 6 (year) + 0 (month) + 24 (day) = 2 mod 7 == Tuesday

Final remarks

Just a few tips: Asking for the year first will make things easier since that is the hardest computation you’ll need to do for this feat. Casting out seven along the way is also very useful. So when calculating the year code of 1888, we do floor(88/4) = 22. But we think of it as the number 1 instead of 22. Then when adding it to 88, just cast out seven, so 88 -> (subtract 70) -> 18 -> 4. So our year code for 1888 is just 1 + 4 + 1 (century code) = 6.

If you’re planning to do this on a specific group of people (say your friends) and you know their age range, then you can increase the speed of finding out when they are born by remembering some of the year code of those year. For example, 1992, 1993, 1994, 1995 have year code 2,3,4,5 respectively. It is easy to find out the year code this way and get the bulk of the calculation out of the way.

The numbers discussed here are chosen because I find them easy to remember. It is not too difficult to tweak the numbers to something else which may be easier for you to remember. For example, we can increase all the month code by 1 if we decrease the century code by 1.

For example

Century code 4 2 0 5

Jan 2 Apr 1 Jul 1 Oct 2
Feb 5 May 3 Aug 4 Nov 5
Mar 5 Jun 6 Sep 7 Dec 0

is also another way set of values that will work with this formula.

There is also another algorithm to determine the day of the week. It is called the doomsday method http://rudy.ca/doomsday.html. For those interested, it is useful to check it out.