You're reading: The Big Internet Math-Off, The Big Internet Math-Off 2019

The Big Internet Math-Off 2019, Group 3 – Vicky Neale vs Jim Propp

This is the third match in round 1: from Group 3, it’s Vicky Neale, vs Jim Propp. The pitches are below, and at the end of this post there’s a poll where you can vote for your favourite bit of maths.

Take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you know any more cool facts about either of the topics presented here, please write a comment below!

Vicky Neale – Patterns and structures

Vicky Neale

Vicky Neale is the Whitehead Lecturer at the Mathematical Institute and Balliol College, University of Oxford, which means her job is to be enthusiastic about mathematics with undergraduates, school students, and anyone else she can find.  She is the author of Closing the Gap: the quest to understand prime numbers. She’s @VickyMaths1729 on Twitter.

Mostly I wanted to share these pictures, and to invite you to notice and explore your own patterns and structures within them. What’s the same in every table? What are the differences between tables? But, in case you want a bit more context, here is some…

What do the pictures show?

These pictures show multiplication tables modulo 2, 3, 4, 5, 6, 7 and 8.

Here’s a description working modulo 7 as an example.

Imagine taking the number line, and coiling it round a mod 7 size cylinder, to get a helix (I always want to call it a spiral, but it’s in 3D so apparently I’m meant to call it a helix). The “mod 7 size cylinder” means that 7 ends up just above 0, and 8 just above 1, and 9 just above 2, and so on till we find 14 just above 7, 15 just above 8, and so on. And for the negatives, we find -1 below 6, -2 below 5, all the way till -7 below 0, -8 below -1, and so on.

In this world, we think of two numbers as somehow being “the same” if they are vertically above each other on the cylinder. For example, …, -14, -7, 0, 7, 14, 21, … are all “the same”. (We say that they are congruent modulo 7.) And …, -13, -6, 1, 8, 15, … are all “the same”. And …, -24, -17, -10, -3, 4, 11, 18, 25, … are all “the same”.

Working modulo 7, there are only really 7 types of number, corresponding to the seven columns of numbers round the cylinder.

The multiplication table for modulo 7 above uses 7 colours, one for each column. We pick two colours and choose a representative from each, say 5 from dull green and 2 from mid purple. Then we multiply them, to get 10, and 10 is in the same colour as 3, so is dark purple. (Thank you to the baby hedgehog highlighting this in the photo.)

Since you ask (maybe), no, the answer doesn’t depend on which representatives we pick from the two colours we’re multiplying, because multiplication modulo n is well defined. We could have chosen -2 from dull green and 16 from mid purple, and multplied them to get -32, and this would still have been dark purple.

(Why) is modular arithmetic important?

It definitely is important, for a variety of reasons.

Within maths, it’s crucial in number theory, and leads to ideas in abstract algebra such as quotienting. Working modulo a prime number can be particularly interesting, and this leads to the idea of finite fields.

Beyond maths, it’s widely used in computer science, cryptographyand information theory. The ISBN (number assigned to a book) and IBAN (bank account number) both use modular arithmetic to detect errors.

Vital statistics

Number of small squares: $2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 = 203$

Number of 0 squares: 73

  • for first rows and columns: $3 + 5 + 7 + 9 + 11 + 13 + 15 = 8^2 – 1 = 63$
  • for elsewhere: $10$

Distribution of other colours: varies between squares. For example, modulo 7, each nonzero number occurs the same number of times, but this is definitely not the case modulo 8.

Time to make a square: 10-15 minutes (I got faster with practice)

Number of yarn ends to sew in at the end: $476$

  • $2$ per crochet square: $406$
  • $2$ per vertical or horizontal crochet line: $2(1 + 2 + 3 + 4 + 5 + 6 + 7) = 7 \times 8 = 56$
  • $2$ per border: $14$

Hours spent in total: I prefer not to think about it.

What patterns and structures are there to notice?

Here are some things you might notice from the pictures. This is just the start!

  • The first row and column of each table is 0.
  • Each table has a line of symmetry along the \ diagonal. This is because multiplication is commutative(even in the world of modular arithmetic).
  • Ignoring the 0 row and column, each table has a line of symmetry along the / diagonal. This is not true in the infinite world of multiplying positive whole numbers.
  • Some tables have 0 inside the square as well as in the first row and column. For example, $2 \times 2 = 0 \pmod{4}$, $3 \times 4 = 0 \pmod{6}$, and $4 \times 6 = 0 \pmod{8}$ – note the strategically positioned hedgehogs. In fact these tables are the ones where the modulus is not pirme. This is because if $n$ is not prime then the integers modulo $n$ do not form an integral domain.
  • Some tables have a sudoku-like property: apart from the 0 row and column, each row and each column contains every colour exactly one. This is called a Latin square. These tables are the ones where the modulus is prime. This is because if $n$ is prime then the nonzero integers modulo $n$ form a group under multiplication.
  • The tables where the modulus is not prime have some rows and columns with the property that every colour occurs exactly once, and others where only some colours occur, but in repeating blocks. There’s lots to explore here…
  • The \ diagonal of each table contains the squares for that modulus. For example, the only squares modulo 8 are 0, 1 and 4. We see 1 appearing 4 times, because the square of an odd number is always one more than a multiple lf 8. So, excitingly, in the world modulo 8 the quadratic polynomial $x^2 – 1$ has 4 roots, where we might have expected at most 2 (the degree of the polynomial).

James Propp – The Muffin Curse

Jim Propp

Jim Propp is a math researcher/teacher/popularizer on the faculty of the University of Massachusetts Lowell who blogs at Mathematical Enchantments. Jim is active in the Gathering 4 Gardner Foundation, the Global Math Project, and the National Museum of Mathematics. He’s @JimPropp on Twitter.

Here’s a small puzzle that opens the door to a big problem: How can one equitably share 24 muffins among 25 people so that each piece is reasonably large?

One scheme for sharing 24 muffins among 25 people involves removing 1/25th of each muffin; if we give an almost-complete muffin to each of the first 24 people and give the slivers to the 25th person, everyone gets 24/25 of a muffin. But that’s a pretty crumby scheme for the last person! There are better schemes, and if you find one you think might be the best, email me at info@mathenchant.org. But be warned: mathematicians still lack a full general solution to what’s called the Muffin Problem, and some have found it addictive.

The Muffin Problem was invented by recreational mathematician Alan Frank in 2008. He asked: If we have $m$ muffins to be divided among $s$ students, how can we cut up the muffins and apportion the pieces so that each student gets $m/s$ of a muffin, and so that the smallest piece is as large as possible? (Making sure that even the smallest pieces are large ensures that all the pieces are large.) Let’s define $f(m,s)$ to be the largest number $f$ for which there’s a scheme in which all the pieces are of size at least $f$. (Here “$f$” is for “function”, “fraction”, and “Frank”.)

Frank was inspired by a real-world problem involving (fewer than 24) muffins and (fewer than 25) muffin-eaters. I’m illustrating his problem using the numbers 24 and 25 as an homage to the classic children’s book “The Math Curse” about the math problems that lurk everywhere around us, just waiting for someone like Frank to notice them. Author Jon Scieszka and illustrator Lane Smith raise the problem of how one should share 24 cupcakes among 25 people. Their answer (get someone to forego a cupcake, or forego it yourself) contains much worldly wisdom, but it ducks the problem of how one should share the cupcakes if one must.

I’ve challenged you to find $f(24,25)$. It’s clear that it’s at least $1/25$ because that’s the size of the smallest piece in the “crumby scheme”, and it’s also not hard to prove that $f(24,25)$ is less than $1/2$.

To show how tricky sharing muffins can be, here’s a good scheme for dividing seven muffins four ways. Split six of the seven muffins into a piece of size $7/12$ and a piece of size $5/12$ and split the seventh into two equal parts of size $1/2$ (which I’ll write as $6/12$ to give all the fractions a common denominator). Two of the students each get three pieces of size $7/12$ while the other two students each get three pieces of size $5/12$ and one piece of size $6/12$. Here’s a depiction of the scheme in which the seven rows (not counting the bottom row) correspond to the seven muffins and the four columns (to the right of the equals-signs) correspond to the four students.

\begin{array}{cccccccc}
1 & = & \frac{7}{12} & & & + & \frac{5}{12} & & \\
1 & = & \frac{7}{12} & & & + & \frac{5}{12} & & \\
1 & = & \frac{7}{12} & & & + & \frac{5}{12} & & \\
1 & = & & & \frac{7}{12} & & & + & \frac{5}{12} \\
1 & = & & & \frac{7}{12} & & & + & \frac{5}{12} \\
1 & = & & & \frac{7}{12} & & & + & \frac{5}{12} \\
1 & = & & & & & \frac{6}{12} & + & \frac{6}{12} \\
\hline
7 & = & \frac{21}{12} & + & \frac{21}{12} & + & \frac{21}{12} & + & \frac{21}{12}
\end{array}

The smallest piece in this scheme is $5/12$ of a muffin, so $f(7,4)$ is at least $5/12$. In fact, you can’t do better than this, so $f(7,4)$ is exactly $5/12$.

Computer scientist and mathematician William Gasarch enlisted a team of undergraduates to help him study the muffin function $f(m,s)$, and their results fill a 200-page manuscript that still doesn’t fully resolve the problem. It appears that $f(m,s)$ depends only on $m/s$ (that is, it seems that $f(m,s) = f(m’,s’)$ whenever $m/s = m’/s’$), but nobody’s proved it. To my mind this is a shocking state of ignorance.

Of the many things we do know, my favorite is the “muffin duality law” first noticed by Erich Friedman:

\[ f(s,m) = (s/m) f(m,s), \]

or in its most symmetrical form,

\[ m f(s,m) = s f(m,s). \]

Duality tells us that there’s a relationship between the problem of dividing 24 muffins among 25 students and the seemingly unrelated problem of dividing 25 muffins among 24 students. This symmetry between muffins and students seems strange, since students are eager to eat muffins while muffins are neither eager to eat students nor eager to be eaten by them (despite what The Muffin Song tells us). Yet the formula is true and easy to prove.

To see via an example why the duality relation holds, notice that if we take the table (given above) depicting our sharing-scheme for the 7-muffin, 4-student problem, in which rows sum to $1$ and columns sum to $7/4$, and we flip it diagonally so that rows become columns and columns become rows, we get a table in which rows sum to $7/4$ and columns sum to $1$; if we then multiply every number in sight by $4/7$, we get a table in which rows sum to $1$ and columns sum to $4/7$. That is, we get a sharing-scheme for the 4-muffin, 7-student problem! What’s more, the size of the smallest piece in the new sharing-scheme is exactly $4/7$ times the size of the smallest piece in the old sharing-scheme. And this relationship is a two-way street: each scheme for the 7-muffin, 4-student problem gives a scheme for the 4-muffin, 7-student problem and vice versa.

\begin{array}{cccccccccccccc}
1 & = & \frac{7}{21} & + & \frac{7}{21} & + & \frac{7}{21} & & & & & & & & \\
1 & = & & & & & & & \frac{7}{21} & + & \frac{7}{21} & + & \frac{7}{21} & & \\
1 & = & \frac{5}{21} & + & \frac{5}{21} & + & \frac{5}{21} & & & & & & & + & \frac{6}{21} \\
1 & = & & & & & & & \frac{5}{21} & + & \frac{5}{21} & + & \frac{5}{21} & + & \frac{6}{21} \\
\hline
4 & = & \frac{12}{21} & + & \frac{12}{21} & + & \frac{12}{21} & + & \frac{12}{21} & + & \frac{12}{21} & + & \frac{12}{21} & + & \frac{12}{21}
\end{array}

On July 10 I’ll post the solution to the $f(24,25)$ problem, acknowledging all solvers. I’ll give special bragging rights to anyone who meets the challenge without having read the article of Gasarch and his collaborators. (You’re on the honor system here!) Later in 2019 I’ll post a longer Mathematical Enchantments essay about the Muffin Problem.

To learn more about the Muffin Problem, watch Gasarch’s 2018 Gathering 4 Gardner video.

To learn even more, look at the (somewhat outdated) preprint by Gasarch and his students. They’ve all caught the Muffin Curse; maybe you will too!

Thanks to Alan Frank, William Gasarch, Sandi Gubin and Evan Romer.


So, which bit of maths tickles your fancy the most? Vote now!

Match 3: Group 3 - Vicky Neale vs Jim Propp

  • Vicky Neale with crafty patterns (57%, 126 Votes)
  • Jim Propp with muffins (43%, 95 Votes)

Total Voters: 221

Vote

Loading ... Loading ...

The poll closes at 9am BST on the 4th. Whoever wins the most votes will win the match, and once the group stages are over, the number of wins will determine who goes through to the semi-final.

Come back tomorrow for our fourth match of the group stages, with Colin Beveridge against Kyle Evans. Or check out the announcement post for your follow-along wall chart!

3 Responses to “The Big Internet Math-Off 2019, Group 3 – Vicky Neale vs Jim Propp”

  1. Avatar Jacob

    I’m really enjoying the matches so far. I wonder, if you do a future edition, if you’d consider hiding the authors until the voting is all finished? I think it’d be fun to read them anonymously and discover the authors only at the end.

    Reply
  2. Avatar Andrew Stacey

    Very much intrigued by the muffins – though “muffin” in the US is more like a cupcake in the UK so perhaps a mistranslation let you down here …

    To make sense of the duality, I imagine there being two groups of people: muffin bringers and muffin eaters (or scoffers to keep the initial letter as an s). The entries in the matrix then say what proportion $Y$ gets of $X$’s muffin. But we can also consider the question of what proportion $X$ contributes to what $Y$ gets. If we then introduce alternative units, the duality becomes (I think) obvious. With $m$ muffin bringers and $s$ muffin scoffers (as in the post), the natural portion unit is $\frac{1}{s}$ of a muffin. $1$ portion is then $\frac{1}{s}$ of what each bringer brings and $\frac{1}{m}$ of what each scoffer scoffs. In units of portions, if $X$ contributes $k$ portions to what $Y$ eats, then obviously $Y$ gets $k$ portions from $X$’s muffin. Now if each scoffer also brought a muffin to share with the original bringers, we could use exactly the same apportioning of portions to divide up each $Y$’s muffin to share out amongst the $X$’s. That is to say, if $X$ contributes $k$ portions of their muffin to $X$, then $X$ likewise contributes $k$ portions of their muffin to $Y$ — only the portion sizes are different so each actually ends up with a different overall amount.

    (I hope that’s clear! I suspect not …)

    So given your $f(s,m)$, I’d like to define $g(s,m) = m f(s,m)$. Then we immediately have symmetry: $g(s,m) = g(m,s)$. The conjecture about “lowest terms” would imply that $g(k s, k m) = k m f(k s, k m) = k m f(s, m) = k g(s,m)$ which is scale-invariance. There’s also a reverse triangle-like law in that if we have a scheme for sharing $a$ muffins amongst $s$ sharers, and $b$ muffins amongst $s$ sharers, then we can obtain a scheme for $a + b$ muffins by applying the scheme for $a$ to the first $a$ and for $b$ to the last $b$. Thus

    \[
    g(s, a + b) \ge \min\{ g(s,a), g(s,b)\}
    \]

    So it’s beginning to look a bit like a weird muffin-metric.

    At this point I want to go and stare at the oven in the hope that some muffins will magically appear and I can do some practical experiments.

    Reply

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Google+