Irregular Webcomic! #3189

Today's strip is by Mike, creator of Spiked Math, a comic which is even geekier than... well, pretty much any comic you care to name. Including itself.

It's about mathematics, and is upated ε>0 times a month. Yes, it's that geeky. Furthermore, Mike provides the following text to illuminate and educate us all about his guest strip:

Matroids are mathematical structures that generalise the notion of linear independence in linear algebra (they are often called "independence structures"). The particular object illustrated in the fourth panel is known as the Fano matroid (or Fano plane) and is an important example in the theory of matroids. In fact, in order to characterise some classes of matroids, such as regular matroids and graphic matroids, one must exclude the Fano plane as a minor.

The Fano plane is one of my favourite mathematical objects and it can be used to solve the Transylvania Lottery problem. The Transylvanian lottery is a lottery where a player chooses any three numbers from 1 to 14, inclusive (call this set of three numbers a "ticket"). The number of possible tickets can be calculated as follows: for your first choice you can pick freely from any of the 14 numbers; for your second number you have to pick one of the 13 remaining numbers; and for your last choice you pick one of the remaining 12 numbers. However, it doesn't matter what order you pick the numbers, so we need to divide the result by the number of ways of ordering 3 numbers, which is 3×2. So the number of tickets is 14×13×12/(3×2) = 364.

After the player has purchased the tickets, three numbers are chosen randomly from 1 to 14 and the player wins if at least two of his/her numbers are among the random ones chosen. The problem is: How many tickets (of the possible 364) must the player purchase in order to guarantee at least one winning ticket?

The solution is that you can buy just 14 tickets; this turns out to be the minimum that the player must purchase to guarantee a win. Let's demonstrate using the Fano plane that with only 14 tickets you can guarantee yourself a win! If you look at the Fano plane, you should see seven lines (including the circle in the middle which counts as a "line"). Label the dots of the Fano plane as follows:

Now label a second Fano plane as follows:

A property of the Fano plane is that each pair (i,j) appears in some line (where i and j are between 1 and 7 for the first Fano plane). For example, the pair (2,6) appears in the circular line of the first Fano plane and the pair (1,6) appears on the vertical line through the middle. You can easily check that every pair from (1,2), (1,3), (1,4)... all the way to (6,7) appears on a line in the first Fano plane. Similarly, every pair from (8,9) to (13,14) appears in a line in the second Fano plane. It is this fact that will help us solve the Transylvania Lottery problem.

Now, buy the following tickets (where each ticket corresponds to a line in one of the Fano planes): {1-2-5, 1-3-6, 1-4-7, 2-3-7, 2-4-6, 3-4-5, 5-6-7, 8-9-12, 8-10-13, 8-11-14, 9-10-14, 9-11-13, 10-11-12, 12-13-14}.

It's clear that at least two of the winning numbers must either be high numbers (8-14) or two of the winning numbers must be low numbers (1-7). But looking at the purchased tickets, we have covered every possible high pair, and every possible low pair that could occur. Thus, we are guaranteed to match at least two numbers with one of our tickets and we win the lottery! If it so happens that all three random numbers are either high or all three are low, then either we have matched them perfectly, or we have three different winning tickets that each have two matching numbers.