# National Graph Lottery

In UK's National Lottery players choose 6 different whole numbers in the range 1 to 59, and win a large prize if all six match with the day's draw.

Each choice of six numbers by a player gives rise to a graph on six vertices (or nodes) if we assume the numbers are vertices, two of which are joined by an edge if they have a common divisor greater than 1 (i.e. they are not relatively prime).

If a prize were also awarded to anyone who guesses the corresponding graph of the winning six numbers, which of the 156 graphs on six vertices should one bet for?

If instead of 59, the upper limit for the range of numbers to be chosen is different (say it is 45 as in Colombia´s lottery, or 49 as it was in the UK a few years back), does the most likely graph differ?

• This looks more like a combinatorics problem than a puzzle, and a computer program should solve it fast. – Nick S Aug 30 '19 at 4:57
• I agree with @NickS here; unless the no-computers tag is used, this could prove simple for a computer to solve for us. – Perpetual J Aug 30 '19 at 13:59
• If mechanically grinding out an answer were the objective, it would be off topic. I assume there is some relevant "aha" moment or similar that makes this a puzzle and not a problem, as the OP's extensive posting history suggests knowing the difference, but—of course—if it turns out to just be grinding through a solution then it will disappointingly need to be closed. Let's proceed for now on the assumption that it is a puzzle, until proven otherwise. – Rubio Sep 2 '19 at 4:56
• Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. – Rubio Sep 20 '19 at 5:22

I can't prove this rigorously, but my intuition suggests that the graph that you should bet on should look something like this:

The reason is as follows:

Notice that this problem can be decomposed into different subgraphs based on the number of elements with a certain prime factor. For $$p=2$$, each number has a $$\frac{1}{2}$$ chance of being even (give or take) so the most common result will be getting three even numbers. This results in the green triangle. For $$p=3$$, each number has a $$\frac{1}{3}$$ chance of being divisible by 3 so the most common result, resulting in another pair of numbers being connected. For any larger p, however, you have on expectation $$\frac{6}{p} < 1.5$$ numbers that are divisible by $$p$$, so the peak should be $$1$$ or less, which results in no numbers being picked. So it's only a question of how many of the 2 divisible by 3 numbers are even. We can justify this being one even, one odd split because we pick the numbers without replacement - there are 9 possibilities of this compared to 3 of both even, and 3 of both odd.
This all relies on the (wrong) assumption that these are all independent events, but since our pool of numbers is always quite large, this shouldn't affect the numbers too significantly.

I just did some number-crunching (couldn't resist) and found that

phenomist is correct!

In particular, for 59 numbers, the graph
applies to 4,954,498 combinations ($$\approx$$ 11% of all combinations).

Second place is this graph

which applies to 3,976,165 combinations ($$\approx$$ 8.82%)

And third is the following graph

which applies to 3,724,399 combinations ($$\approx$$ 8.27%)
These top three are unchanged whether we apply to 45 numbers or 49 numbers, unsurprisingly.

• How did you crunch the numbers? Did you write an algorithm? Just curious. :) – Miles Davis Sep 10 '19 at 10:41
• @MilesDavis Yes, I wrote an algorithm. For each choice of 6 numbers I computed the 6 vertex degrees, sorted them and then counted the number of times the list appears. This approach is fraught with danger as two graphs with the same list are not necessarily isomorphic. However, in the case of the top three, there is just one graph for each list. For example, the lists for the top three are [0,0,1,2,2,3], [0,0,0,2,2,2] and [0,0,3,3,3,3] – hexomino Sep 10 '19 at 10:51