Season 11 Episode 9

Beth joins James on the livestream for some puzzles. We've had winter puzzles and summer puzzles on the Oxford Online Maths Club before, so maybe these are spring puzzles?

Watch on YouTube

Further Reading

Further puzzle remixes

What if, as well as losing the game when Frog says “higher” twice in a row, you also lose the game if Frog says “lower” twice in a row? (This doesn’t leave you with much room for guessing; Frog doesn’t like to repeat responses!)

How about, instead, you have five guesses, but the additional rule is that you lose if Frog says “higher” three times in a row (a slightly more patient frog...). What’s the largest number that you can let Frog pick, so that you’ll get a “yes”, without ever getting “higher” three times in a row?

A reformulation of this problem is “how many sequences are there of length 1 to n-1, where each term is 0 or 1, and where there are never two/three 1s in a row?”. This is a bit like MAT 2009 Q7 (see www.maths.ox.ac.uk/r/mat for past papers of the MAT, an admissions test that we used between 2007 and 2025 inclusive).

Fibonacci numbers

Marcus du Sautoy was on our social media recently, pointing out that Fibonacci wasn’t the first to be aware of the sequence 1, 1, 2, 3, 5, 8, ... .

There is theory for recurrence relations. See e.g. this free online textbook.

Someone in chat posted something close to the Binet formula; this is a formula in terms of \(n\) that calculates the \(n\)th Fibonacci number, without calculating the previous ones. Perhaps surprisingly, it involves the golden ratio \(\frac{1}{2}\left(1+\sqrt{5}\right)\).

I’m pretty sure that the formula in chat included an extra term to allow for the \(+2\) in our recurrence relation. You might like to study the theory above to see where this particular term comes from!

Another recursion problem

When we solved the harder Frog problem, we had two related sequences; \(a_n\) for how many numbers can you distinguish with \(n\) guesses if Frog isn’t annoyed, and \(b_n\) for how many numbers you can distinguish if Frog is annoyed about saying “higher” just now.

This next problem has something similar going on (but no angry frogs). See if you can find the pair of sequences.

Consider a rectangle of squares, 3 squares tall and \(n\) squares wide, where \(n\) is an even number. We would like to tile this rectangle with 2-by-1 tiles; each tile covers exactly two adjacent squares. For example, you could have a row of vertical tiles and a row of horizontal tiles underneath. Or lots and lots of horizontal tiles. How many ways are there to tile the rectangle, in terms of \(n\)?