From the FiveThirtyEight website:
“Five friends with a lot in common are playing the Riddler 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. At this point, the fifth friend is left speechless. (You can tell why all these people are friends.)
What is the product of the selected numbers on each ticket?
Extra credit: How many different ways could the friends have selected five numbers each so that all their statements are true?"
My initial intent was to produce an example, use the product of the numbers on one of the example tickets as the answer, and call it a day. But in searching for an example using R, I realized that one can find the answer and prove that it is unique without saying what the friends’ selections might be. But in the end I will do that anyway. Plus I came up with a solution to the extra credit, albeit after the deadline.
The first step is to cut down the set of numbers that could be on the friends’ tickets. The third friend’s comment allows us to eliminate 1 and any prime power.
library(dplyr)
library(iterpc)
library(primes)
prime.list <- generate_primes(2,70)
prime.powers <- integer()
for(p in prime.list){
i <- 0
while(p^i <= 70){
prime.powers <- c(prime.powers,p^i)
i <- i+1
}
}
selections <- setdiff(1:70,prime.powers)
print(selections)## [1] 6 10 12 14 15 18 20 21 22 24 26 28 30 33 34 35 36 38 39 40 42 44 45
## [24] 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70Let \(P\) be the product of the numbers on one ticket, and let \(S\) be the product of the possible selections. Note that for any prime number \(q\), the number of times \(q\) appears in the prime factorization of \(P^5\), i.e. the product of the 25 numbers on the tickets, can’t be more than the number of times it appears in the prime factorization of \(S\) because the 25 distinct numbers on the tickets are, obviously, a subset of the possible selections. So it makes sense to find the prime factorization of \(S\).
p.exponent <- function(x,p){
tmp <- 0
while(x%%(p^tmp)==0){
tmp <- tmp + 1
}
return(tmp-1)
}
factor.mat <- matrix(0,nrow = length(selections),ncol = length(prime.list))
for(i in 1:length(selections)){
for(j in 1:length(prime.list)){
factor.mat[i,j] <- p.exponent(selections[i],prime.list[j])
}
}
factorization <- colSums(factor.mat)
names(factorization) <- prime.list
print(factorization)## 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
## 46 26 13 8 5 4 3 2 2 1 1 0 0 0 0 0 0 0 0This gives us upper bounds for the prime factorization of \(P^5\), but what we really care about is the prime factorization of \(P\), so we need to divide by 5 and round down.
bounds <- floor(factorization/5)
print(bounds)## 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
## 9 5 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0Clearly the bounds that apply to \(P\) also apply to the individual numbers that the players select, so we can further reduce the set of possible selections:
for(p in prime.list){
bound <- bounds[as.character(p)]
temp.bool <- sapply(selections,function(x) p.exponent(x,p) <= bound)
selections <- selections[temp.bool]
}
print(selections)## [1] 6 10 12 14 15 18 20 21 22 24 28 30 33 35 36 40 42 44 45 48 50 54 55
## [24] 56 60 63 66 70Now for a simple but crucial observation: exactly 8 of these 28 numbers are divisible by 7.
selections[selections%%7 == 0]## [1] 14 21 28 35 42 56 63 70This means that \(P\) must be divisible by 7, or else there would be only 20 numbers available for the tickets. Therefore the selected numbers must comprise 5 multiples of 7 and the 20 numbers that are not multiples of 7. (We can’t use more than 5 multiples of 7 because there wouldn’t be enough to put an equal numbers of them on each ticket.)
As noted earlier, the product of all the numbers on the tickets is \(P^5\), so we will will consider all possible ways of selecting 5 multiples of 7 and determine which of these will result in a set of 25 numbers whose product is a fifth power.
mult.7 <- selections[selections%%7==0]
other <- selections[selections%%7!=0]
prime.list <- c(2,3,5,7,11)
I = iterpc(length(mult.7),5)
valid <- list()
selections <- list()
temp <- getnext(I)
while(!is.null(temp)){
temp.select <- c(other,mult.7[temp])
factor.mat <- matrix(0,nrow = length(temp.select),ncol = length(prime.list))
for(i in 1:length(temp.select)){
for(j in 1:length(prime.list)){
factor.mat[i,j] <- p.exponent(temp.select[i],prime.list[j])
}
}
factorization <- colSums(factor.mat)
if(all(factorization%%5 == 0)){
valid[[length(valid)+1]] <- factorization
selections[[length(selections)+1]] <- temp.select
}
temp <- getnext(I)
}
print(length(valid))## [1] 1So there is indeed only one way of selecting 25 numbers that can be partitioned into 5 sets of 5 whose products are all equal. And we can say what that product is.
factorization <- valid[[1]]/5
names(factorization) <- prime.list
print(factorization)## 2 3 5 7 11
## 7 4 2 1 1ticket.product <- 1
for(p in prime.list){
ticket.product <- ticket.product*p^factorization[as.character(p)]
}
ticket.product <- as.integer(ticket.product)
print(ticket.product)## [1] 19958400Technically, we have answered the question, but we haven’t given an example of what the five friends’ tickets could be. For that, we turn to Python and its constraint package. But first we have to write the 25 selected numbers to a file.
writeLines(as.character(selections[[1]]),"selections.txt")Here is the Python code and the example tickets:
from constraint import *
source = open('selections.txt','r')
selections = source.readlines()
source.close()
selections = [int(s.strip()) for s in selections]
def legal_prod(a,b,c,d,e):
return a*b*c*d*e == 19958400
problem = Problem()
problem.addVariables(range(0,25), selections)
problem.addConstraint(AllDifferentConstraint(),range(0,25))
for i in range(0,5):
problem.addConstraint(legal_prod,range(5*i,5*i+5))
solution = problem.getSolution()
for i in range(0,5):
ticket = [solution[j] for j in range(5*i,5*i+5)]
ticket.sort()
print ticket## [6, 15, 56, 60, 66]
## [10, 14, 48, 54, 55]
## [12, 18, 42, 44, 50]
## [21, 22, 24, 40, 45]
## [20, 28, 30, 33, 36]At first I tried running the code above and getting all the solutions, but it seemed to be taking a very long time. So, realizing that each ticket must have one multiple of 7 and one multiple of 11, I looped through all \(5!\) ways of pairing up these numbers and solved a 15-variable constraint problem for each one. Note that my answer assumes the order of numbers on the tickets doesn’t matter, nor does the assignment of tickets to friends.
from constraint import *
from itertools import *
source = open('selections.txt','r')
selections = source.readlines()
source.close()
selections = [int(s.strip()) for s in selections]
seven_mults = [s for s in selections if s%7 == 0]
others = [s for s in selections if not(s%7 == 0 or s%11 == 0)]
def legal_prod(a,b,c,d,e):
return a*b*c*d*e == 19958400
def in_order(a,b,c):
return a < b and b < c
perms = permutations(seven_mults,5)
solution_count = 0
for p in perms:
def legal_prod_22(a,b,c):
return legal_prod(a,b,c,p[0],22)
def legal_prod_33(a,b,c):
return legal_prod(a,b,c,p[1],33)
def legal_prod_44(a,b,c):
return legal_prod(a,b,c,p[2],44)
def legal_prod_55(a,b,c):
return legal_prod(a,b,c,p[3],55)
def legal_prod_66(a,b,c):
return legal_prod(a,b,c,p[4],66)
problem = Problem()
problem.addVariables(range(0,15), others)
problem.addConstraint(AllDifferentConstraint(),range(0,15))
# Constraints for ticket that contains 22
problem.addConstraint(legal_prod_22,range(0,3))
problem.addConstraint(in_order,range(0,3))
# Constraints for ticket that contains 33
problem.addConstraint(legal_prod_33,range(3,6))
problem.addConstraint(in_order,range(3,6))
# Constraints for ticket that contains 44
problem.addConstraint(legal_prod_44,range(6,9))
problem.addConstraint(in_order,range(6,9))
# Constraints for ticket that contains 55
problem.addConstraint(legal_prod_55,range(9,12))
problem.addConstraint(in_order,range(9,12))
# Constraints for ticket that contains 66
problem.addConstraint(legal_prod_66,range(12,15))
problem.addConstraint(in_order,range(12,15))
solutions = problem.getSolutions()
solution_count += len(solutions)
print solution_count## 12781