# Winning the Lottery

Bob: I hear you won the lottery.

Alice: So I did!

Bob: What six numbers did you win it with?

Alice: Can't remember. All I recall is that they were all different, and none greater than 28.

Bob: Anything else?

Alice: Yes. I checked that no other six different numbers, none greater than 28, have the same common factor graph as mine.

(The common factor graph of a set of integers is the graph whose vertices are the integers, two of which are joined by an edge if they have a common factor greater than 1.)

What six numbers did Alice win the lottery with?

## 2 Answers

Let the Solution contain 2; then changing that to 4, 8 or 16 will not introduce new factors and hence we can replace 2 with 4, 8 or 16 get more new Solutions, which is against the Uniqueness Constraint; Hence Either all A = { 2, 4, 8, 16 } are Part of the Solution or all are not Part of the Solution.

Likewise for B = { 3, 9, 27 }
Likewise for C = { 5, 25 }
Likewise for D = { 6, 12, 24, 18 }

Consider E = { 1, 17, 19, 23 } which have no common factors with other numbers between 1 & 28. If one of these numbers is Part of the Solution, we can replace that with some other to get more Solutions; Hence Either all 1, 17, 19 & 23 are Part of the Solution or all are not Part of the Solution.

With E in the Solution, the other 2 numbers can have multiple Possibilities, which is against the Uniqueness Constraint : we can ignore E.

With A in the Solution, we can replace that with D, Example A+C is same as D+C : we can ignore A & D.

We are left with:
7 10 11 13 14 15 20 21 22 26 28

With 7&14 in the Solution, it is same as 7&28 : Ignore 7.
With only 11 or 13 and not 22 or 26, we can replace 11 or 13 with some other number from E : Ignore these.

We are left with Solution given by Athin earlier:
10 14 15 20 21 28

[[ Lot of hand-waving involved in my "Proof" !!!! ]]

Unproven Answer (I need to go out soon):

This is the graph:

And the solution is unique, which is:

$$10, 14, 15, 20, 21, 28$$