At the MathsJam annual gathering, one of the many activities attendees can participate in is a competition competition – entrants each come up with a competition and submit it into a larger competition, other attendees enter each of the competitions within the competition competition, and the organisers get the chance to make long and confusing (but strictly correct) announcements that contain the word competition a lot of times.

This year, we decided, after a spectacular last-minute MathsJam bake-off entry failure on the behalf of Katie, to enter a joint competition into the competition competition. Inspired by the ‘lowest unique answer’ style of competition, which has previously featured in various MathsJam Competition Competitions (and our recent lecture on game theory) we came up with an idea – what about a competition seeking a unique entry in a non-ordered set?

Our Competition

We realised that choosing a combination of objects from a set, and picking colours for each object, would allow us to control the number of possible options and therefore constrain the number of options to make it likely we’d have at least some unique entries, but not so many options that we’d get too many. Here’s what we settled on for our competition:

It took us a while to settle on ‘choose two objects from three and colour them one of two colours’ (and even longer to settle on a choice of theming, but in the end Alice in Wonderland provided objects which could be drawn relatively easily, and with a maths connection).

Although there are 200-250 people at MathsJam, competitions are required to provide only 100 copies of the answer sheet, and we figured competitions typically get around 25 entries. That said, we set the bar reasonably low by making it an option to just scrawl a rough identifiable shape.

One thing we hoped people would enjoy trying to calculate was the number of distinct combinations possible. Since we have three objects in each of two colours, we have a pool of six different options for each of the two drawings. The available combinations include 6 cases of ‘the same object in the same colour twice’, and \( \binom{6}{2}=15 \) ways of picking two different objects, giving a total of 21 possible combinations.

This seemed like a good number – if we had fewer possible combinations, we might not have any unique entries, and with too many, we’d essentially be running a prize draw.

So how did it work out in practice?

The results

On the day, we got exactly 50 entries to our competition. We immediately discounted any invalid entries (people not understanding, or deliberately trying not to follow, the rules).

Of the remainder, 13 were ‘the same object in the same colour twice’ – this is about what we would expect (6 per 21 entries would give us 14). This might have been chosen by the entrants because in the absence of an ordering on the possibilities, it felt like something fewer people were likely to go for and therefore a good strategy.

We had seven entries which were unique, and drew a winner from these. Only 19 of the 21 possible combinations were submitted – no one chose ‘blue hat and blue cat’ or ‘red hat and red watch’.

This made us wonder how many entries we should expect before all 21 distinct combinations were chosen at least once each. So we did some more maths!

How many entries should we expect before all have been seen at least once?

(You may wish to go away and think about your own answer to this before reading on.)

The first entry is necessarily distinct from everything that has been chosen before. The second entry, if chosen independently at random, is therefore distinct with probability \( \frac{20}{21} \), because 20 of the 21 remaining options are distinct from the first. This means the expected number of entries after the first before we get the second distinct entry is \( \frac{1}{20/21} = \frac{21}{20} \).

By the same logic, after we’ve seen two distinct combinations, we expect another \( \frac{1}{19/21} = \frac{21}{19} \) entries before we see a third distinct combination. Carrying on, the expected number of entries before all options have been chosen is:

\[ \sum_{i=1}^{21} \frac{21}{21-(i-1)} = \frac{21}{21} + \frac{21}{20} + \ldots + \frac{21}{1} \approx 77\text{.} \]

It is interesting to see the values of \( \frac{21}{21-(i-1)} \) in a table. The value of 1 in the first row tells us we expect a distinct combination after 1 entry. The value of 1.05 on the following row tells us we expect a further 1.05 entries before the next distinct combination. The number of entries expected overall so that we have seen all possible combinations is the sum of the right hand column of this table, approx. 77.

We can also use this table to investigate what actually happened at MathsJam. The second-to-last row tells us that after 19 distinct combinations have been entered, we expect another 10.5 entries to get the 20th distinct combination. Then the last row tells us that after the 20th, we expect another 21 entries before getting the final distinct combination.

If we sum the table without the last two rows, we get approx. 45. This tells us that with between 45 and 55.5 entries we expect to have seen 19 distinct combinations but not yet 20, which is exactly what happened with our 50 entries at MathsJam!

This problem is known as the Coupon collector’s problem. Here is a statement of the problem from Wikipedia:

Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once?

Another way of calculating the answer is to take \( n H_n \) where \( H_n = \sum_{i=1}^n \frac{1}{i} \). Indeed, \( 21 H_{21} \approx 77 \) also.

More information

We found this section from Brilliant.org useful in writing this piece: Linearity of Expectation > Using States.

A note on the images. We got some fantastic drawings entered in the competition, and have shared some in this post, but in order to avoid publishing people’s names without permission (and since some weren’t sufficiently clearly labelled with a name), we have not attributed the images. If there is a picture you drew in this post and you would like it removed or attributed, please get in touch.