Oxford and Cambridge Maths interview question – Fibonacci?

Maths with Ronald blog

More Posts by Ronald

This is copied from my old blog (2023), for students applying to universities.

I'm doing a lot of Mathematics and Computer Science mock interview questions right now. Here's a tricky example question that leads to an interesting discussion:

A 1982 NASA illustration of a machine with two robotic arms passing parts to another machine, which is constructing a third machine.

Suppose a self-replicating machine has been invented. Every pair of self-replicating machines will produce one new self-replicating machines each day, indefinitely.

So, start on Day 1 with 2 self-replicating machines. These work together and take one day to make a new machine.

On Day 2, we have 3 self-replicating machines. The original two self-replicating machines keep working, but the third self-replicating machine has to wait for a pal.

One Day 3, we have 4 self-replicating machines. Now we have two pairs, so they work together to make two new machines.

On Day 4, we have 6 self-replicating machines. And so on.

Now for the question. Start out by showing your understanding, then face some hard questions. It's normal that you'll get hints to point you in the right direction - do use the comments if you need help:

A close-up photo of a sunflower illustrating a fibonacci spiral. Counting the number of sunflower seeds along different spiral paths will typically lead to a Fibonacci number.

a) How many self-replicating machines will we have on Day 10?

On Day 21, there will be 5395 machines. How many on Day 20?

b) Now let $S_{n}$ be the number of machines on Day n, so $S_{1}=2$.

Can you suggest an upper bound for $S_{n}$ in terms of n?

c) A recurrence relation for the Fibonacci sequence might look like:

$F_{1}=1,F_{2}=1$,

$F_{n}=F_{n-1}+F_{n-2}$ for $n>2$

Write a recurrence relation for $S_{n}$. Why is your recurrence relation correct?

Feel free to comment for some discussion.

Would you like to do some interview practice with me for Computer Science and Mathematics for Oxford, Cambridge and other university courses? Get in touch to arrange some sessions online: ronald@mathswithronald.com, WhatsApp +31682589013