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:
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) 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 Sn be the number of machines on Day n, so S1 = 2.
Can you suggest an upper bound for Sn in terms of n?
c) A recurrence relation for the Fibonacci sequence might look like:
F1 = 1, F2 = 1,
Fn = Fn-1 + Fn-2 for n > 2
Write a recurrence relation for Sn. Why is your recurrence relation correct?
Feel free to comment for some discussion of this question below.
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
Leave a Reply