Most of the Classics look too difficult for me to be able to solve, but this week’s looked like I could approach it. No code required, either.
Here’s the question:
Five friends … are playing the … Lottery, in which each must choose exactly five numbers from 1 to 70. After they all picked their numbers, the first friend notices that no number was selected by two or more friends. Unimpressed, the second friend observes that all 25 selected numbers are composite (i.e., not prime). Not to be outdone, the third friend points out that each selected number has at least two distinct prime factors. After some more thinking, the fourth friend excitedly remarks that the product of selected numbers on each ticket is exactly the same. …
What is the product of the selected numbers on each ticket?
There might be a neat, elegant way of solving this, but I chipped away at it bit by bit.
Initial Constraints
These are the constraints in the original question:
- Each number is used only once.
- Each number is composite.
- Each number has at least two distinct factors.
- Each set of five numbers has the same product.
So I started by looking at the numbers between 1 and 70 that satisfy constraint three. These are the only numbers that can have been chosen by the players:
Number | Powers Of: | ||||||||||
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | |
6 | 1 | 1 | |||||||||
10 | 1 | 1 | |||||||||
12 | 2 | 1 | |||||||||
14 | 1 | 1 | |||||||||
15 | 1 | 1 | |||||||||
18 | 1 | 2 | |||||||||
20 | 2 | 1 | |||||||||
21 | 1 | 1 | |||||||||
22 | 1 | 1 | |||||||||
24 | 3 | 1 | |||||||||
26 | 1 | 1 | |||||||||
28 | 2 | 1 | |||||||||
30 | 1 | 1 | 1 | ||||||||
33 | 1 | 1 | |||||||||
34 | 1 | 1 | |||||||||
35 | 1 | 1 | |||||||||
36 | 2 | 2 | |||||||||
38 | 1 | 1 | |||||||||
39 | 1 | 1 | |||||||||
40 | 3 | 1 | |||||||||
42 | 1 | 1 | 1 | ||||||||
44 | 2 | 1 | |||||||||
45 | 2 | 1 | |||||||||
46 | 1 | 1 | |||||||||
48 | 4 | 1 | |||||||||
50 | 1 | 2 | |||||||||
51 | 1 | 1 | |||||||||
52 | 2 | 1 | |||||||||
54 | 1 | 3 | |||||||||
55 | 1 | 1 | |||||||||
56 | 3 | 1 | |||||||||
57 | 1 | 1 | |||||||||
58 | 1 | 1 | |||||||||
60 | 2 | 1 | 1 | ||||||||
62 | 1 | 1 | |||||||||
63 | 2 | 1 | |||||||||
65 | 1 | 1 | |||||||||
66 | 1 | 1 | 1 | ||||||||
68 | 2 | 1 | |||||||||
69 | 1 | 1 | |||||||||
70 | 1 | 1 | 1 | ||||||||
Totals: | 46 | 26 | 13 | 8 | 5 | 4 | 3 | 2 | 2 | 1 | 1 |
We’ve removed the prime numbers, the powers of only one prime (like eight or nine), and the number one itself. So the total number of potential lottery numbers has gone from 70 to 41. What next?
The Fundamental Theorem of Arithmetic
[T]he fundamental theorem of arithmetic … states that every integer greater than 1^{} either is a prime number itself or can be represented as the product of prime numbers and that … this representation is unique, up to (except for) the order of the factors.
So says Wikipedia. It’s useful here because of constraint four, that each set of five numbers has the same product.
Combining the theorem (that each number is the product of primes in one unique way) with the constraint (that each set of numbers has the same product), we see that each set of numbers has exactly the same set of prime factors.
Knowing that, we can remove any numbers with a prime factor greater than 11. Look at the table above: there are five numbers with a factor of 11, but the larger prime factors appear in four or fewer possible lottery numbers. If they can’t appear at least five times, then they can’t appear at all: we can’t have three sets that have a factor of 13, and two that don’t – there’s no way to satisfy constraint four in a case like that.
That lets us take reduce the number of possible lottery numbers quite a bit more:
Number | Powers Of: | ||||
2 | 3 | 5 | 7 | 11 | |
6 | 1 | 1 | |||
10 | 1 | 1 | |||
12 | 2 | 1 | |||
14 | 1 | 1 | |||
15 | 1 | 1 | |||
18 | 1 | 2 | |||
20 | 2 | 1 | |||
21 | 1 | 1 | |||
22 | 1 | 1 | |||
24 | 3 | 1 | |||
28 | 2 | 1 | |||
30 | 1 | 1 | 1 | ||
33 | 1 | 1 | |||
35 | 1 | 1 | |||
36 | 2 | 2 | |||
40 | 3 | 1 | |||
42 | 1 | 1 | 1 | ||
44 | 2 | 1 | |||
45 | 2 | 1 | |||
48 | 4 | 1 | |||
50 | 1 | 2 | |||
54 | 1 | 3 | |||
55 | 1 | 1 | |||
56 | 3 | 1 | |||
60 | 2 | 1 | 1 | ||
63 | 2 | 1 | |||
66 | 1 | 1 | 1 | ||
70 | 1 | 1 | 1 | ||
Totals: | 36 | 22 | 12 | 8 | 5 |
After removing the larger prime factors, there are now only 28 possible lottery numbers left. Since we need to find 25 lottery numbers, and removing any more prime factors would remove at least five more lottery numbers, we also know that all five of the prime factors we have must appear.
Multiples of Five
To remove the last three possible lottery numbers, we just need to remember the Fundamental Theorem of Arithmetic and constraint four. Since each set of lottery numbers must have an identical set of prime factors, the total number of appearances of any prime factor, summed over all the lottery numbers chosen, must be a multiple of five.
Look at the Totals row at the bottom of the table above. 11 already appears as a factor five times, in five separate lottery numbers, so we can’t touch those. Seven appears as a factor eight times, in eight numbers. That needs to be reduced to five times, so we need to remove three numbers with factors of seven. Here are the candidates, along with the number of times each prime factor appears over all 28 candidate lottery numbers:
Number | Powers Of: | ||||
2 | 3 | 5 | 7 | 11 | |
14 | 1 | 1 | |||
21 | 1 | 1 | |||
28 | 2 | 1 | |||
35 | 1 | 1 | |||
42 | 1 | 1 | 1 | ||
56 | 3 | 1 | |||
63 | 2 | 1 | |||
70 | 1 | 1 | 1 | ||
Total over all remaining lottery numbers: | 36 | 22 | 12 | 8 | 5 |
We know we’re going to remove three lottery numbers which are multiples of seven. The total appearances of two, three, and five also need to be multiples of five.
Clearly we’ll remove 35 and 70, so that five appears as a factor ten times. Once 35 and 70 are gone, there are only 26 candidate lottery numbers left. We still need to remove one more multiple of seven, and these are our choices:
Number | Powers Of: | ||||
2 | 3 | 5 | 7 | 11 | |
14 | 1 | 1 | |||
21 | 1 | 1 | |||
28 | 2 | 1 | |||
42 | 1 | 1 | 1 | ||
56 | 3 | 1 | |||
63 | 2 | 1 | |||
Total over all remaining lottery numbers: | 35 | 22 | 10 | 6 | 5 |
We can easily see that removing 63 will turn all of the totals to multiples of five, but no other choice will.
If we take the remaining powers, and divide their appearances by five we’ll see how many are in each individual set of lottery numbers. Even though we don’t know which of the 25 possible lottery numbers are in each set, we can still calculate their product:
2^{7} × 3^{4} × 5^{2} × 7 × 11 = 19 958 400
As for the extra credit question, I don’t think I know where to start!