The Lily Pad Problem

Here is an interesting question to get you thinking about some beautiful and fundamental ideas in combinatorics - an area that every aspiring mathematician should have some grounding in.

Suppose we have n lily pads.

The lily pads are labelled from 1 to n in order.

Question 1:

If there is a frog, who can jump one to the next and can only jump 1 or 2 pads at a time, then how many ways are there of the frog jumping from the 5th lily pad to the 1st?

Solution:

Well... our frog starts on number (5)

Let say it starts by jumping 2 pads, and ends up on (3). Now, there are only two ways of doing this: either the frog jumps 1 to (2) and then once again to (1), or the frog jumps 2 straight to (1). In short, there are 2 ways in this case.

If the frog jumps one pad initially, the cases are more interesting...

(5), (4), (3), (2), (1)

(5), (4), (2), (1)

(5), (4), (3), (1)

i.e. three possibilities.

Hence, the answer is 3+2=5 in total!

Question 2:

If we write f(n) to mean the number of ways the frog can jump back from the nth lily pad, then is there any essential pattern underlying the values of f(n)?

Solution:

Well... this is again an interesting question!

f(5) = 5 as calculated above. But let us start with the smaller values...

Clearly:

f(1) = 1

f(2) = 1

f(3) = 2

f(4) = 3

f(5) = 5

Hang on! You may have spotted the Fibonacci Sequence: 1, 1, 2, 3, 5, ...

Question 3:

If f(n) is just the Fibonacci Sequence, can you think of a nice argument as the why this makes sense?

Please do think about this before reading on...

Hint:

For the frog, there are many different routes it can take. Our task is to count them. Suppose we were able to ask a yes/no question which would allow us to separate the routes into two categories, and to then count these separately.

Solution:

Let us ask the question: "Does the frog jump 1 pad on the first move?" ;

If yes, then the frog now finds itself on the (n-1)th pad.

If no, then the frog jumps two. So, it lands on the (n-2)th pad.

In the first case, the number of possibilities (by definition) is f(n-1).

Similarly for the second case, the number of possibilities (by definition) is f(n-2).

Therefore, f(n) = f(n-1)+f(n-2).

This is the recurrence relation ;that defines the Fibonacci sequence. ;

A Beautiful Connection:

The connections between counting &;; recurrence relations runs deep in many problems.

Now, I recommend you try the next problem aiming to use the above technique in a novel way.

The Final Problem:

Suppose Timothy attempts 10 Exams. Each problem has a mark out of 100.

The exams are numbered, and each exam is much harder than the previous.

Because of this, Timothy never scores higher in a subsequent problem than a previous one.

An example of scores that is allowed: (95, 86, 77, 77, 50, 46, 43, 20, 19, 5).

An example of scores that is not allowed: (99, 100, 50, 40, 34, 32, 20, 18, 16, 15).

How many possible sequences of scores are possible?

If your interested in the solution to this problem, I would be happy to arrange lessons so please do get in touch.