Season 9 Episode 9

Combinatorics

Here’s a link to Dr Eve Vidalis' website with combinatorics problems https://www.evevidalis.com/teaching/partition-combinatorics-reading-group.

Eve set up the She Talks Science STEP Summer School for female and non-binary students, and it's still running at Murray Edwards at the University of Cambridge. Find out more at https://www.murrayedwards.cam.ac.uk/she-talks-science-step-summer-school.

Open days

If you’d like to visit Oxford for an open day this year, please see http://www.maths.ox.ac.uk/r/open-days.

If you’d like a virtual open day, there will be one on the Oxford Mathematics Plus YouTube channel (the same YouTube channel that has the OOMC episodes). See the link above for more information.

Pursuit on graphs 

Sometimes this is set up as cops and robbers, rather than Mario and Luigi. I'll try not to mix up the settings, because (as far as I know) Mario is not a cop and (as far as I know) Luigi is innocent.

The Wikipedia page on a "cop-win" graph has a description of the “dismantling” process that Eve described at the end of the episode. This is part of the description of precisely which graphs are a win for Mario. Some people in chat made hypotheses about this, and I encourage you to explore before looking at the answer.

If Luigi wins on a particular graph, then we might wonder what would happen if there were two Marios working together to catch Luigi. For example, on a large cycle, Luigi can escape one Mario forever, but if there were two Marios, they could run in opposite directions to trap Luigi.

Determining how many cops are needed to catch a robber is called the cop number problem. It’s not straightforward to work out the cop number, partly because, as we’ve already seen, either adding or removing edges might decrease the cop number. For fixed \(n\), the number of vertices of the graph, nobody knows which graph needs the most cops; that’s an open problem at the time of writing. Perhaps you could think about it?

Pursuit not on graphs

We can also think about pursuit with continuous movement (rather than taking turns on a graph). Here’s a Wolfram MathWorld page with a description of some of the maths. 

You might also like this video by Ayliean. She’s a Maths YouTuber with arty maths and mathsy art. She’s currently running hashtag MathArtMarch on Bluesky. You can draw this yourself, perhaps with pencil and paper, or perhaps by coding something.

Coin problem

Here's a problem that I was reminded of during the live episode. On reflection, I'm glad I didn't say anything about it live, because it's a bit off-topic.

Imagine a large rectangular table and two players, each of whom has a huge supply of equally-sized coins. They'll take it in turns to place a coin on the table without moving any of the other coins, and without this new coin touching or overlapping any of the previous coins. Find a winning strategy for the first player.