Mr. P and Mr. S Quiz | LittleCheeseCake

Few months away from my little blog, I decide to make the “I am back post” by going through an interesting brain teaser again.

Months ago, one of my closest friends sent a little quiz in our chat group. I was immediately attracted by the quiz and started to think about it. Then I realized it is not an easy problem. I opened the terminal and wrote a few lines of Python to help me to do the calculation. Things got more interesting when I started to code. Finally I spend some time get the answer. It is so fun to work on such a beautiful math problem.

Problem

There are two different numbers in range of 2-99. One mathematician (Mr. P) knows the product of the two numbers, and the other mathematician (Mr. S) knows the sum of the two numbers, they have the following conversations:

Mr. P: I don’t know what x, y are Mr. S: I knew you don’t know! Mr. P: Now I know! Mr. S: well, I will know if you know.

So, what are the two numbers?

My mind map to solve it

We know a lot from unknown

Mr. P: I don’t know what x, y are. Mr. S: I knew you don’t know!

There are some information hidden in the first around of conversation between Mr. P and Mr. S

At least one of the numbers is not prime.

If both the numbers are prime numbers, Mr. P who knows the product can easily do the factorization and get the numbers

We can get a list of possible sums of the two numbers, which are the sums of any two numbers (5-197) exclusive of the sums of two prime numbers

That is why Mr. S could say that he “knew!” because he is sure that what he got in hand - the sum of the two numbers - is definitely not a sum of two primes.

So we can get a list of possible sums p :

#primes between 2-99
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

#find a list of sum from two primes
s =[]
for k in prime:
    for b in prime:
        if not k == b and (k+b) not in s:
            s.append(k+b)

#find the possible sums (all the possible sums of two numbers (5 - 197) exclusive of s[])
p =[]
for i in range(5,197):
    if i not in s:
        p.append(i)

print "possible list p: "
print p
print len(p)

There are 83 possible sums. What Mr. S has in hand must be one of the numbers. Still quite a large range, but we get the possible list p that we can continue to work on.

possible list p: 
[6, 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 166, 167, 169, 171, 173, 174, 175, 177, 178, 179, 181, 182, 183, 184, 185, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196]
83

Get it done with brute force

Mr. P: Now I know!

Suppose that the smart mathematician Mr. P also comes up with the previous analysis, he shall have that list of possible sums p in hand as well. If he now factorizes the product he got in hand into two numbers between 2-99, he could get a few different pairs, then a few sums from these pairs.

one and only one from the factor pairs, gives a sum in the possible sums list p shown above

This is what makes Mr. P be so sure about the unique answer

Now we can list all the possible products of two numbers between 2-99, then do brute-force search among all using this logic.

Helper function I - Find the factors of a number:

#function: s[] = factors(number)
#find the factors of the number, exclusive of 1 and itself, return as a list of numbers
def factors(n):
    s = set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    s.remove(1)
    s.remove(n)
    return list(s)

Helper function II - Find the list of sums from its factor pairs of a number:

#function: s[] = find_sum_list(number)
#factorize the number into two numbers and find the sum, return a list of such pairs
def find_sum_list(n):
    s_l = []
    f = factors(n) #find factors of n
    for k in f:
        i = n / k
        # only consider it when i is smaller than k since it will be symmetric
        if i < k: 
            s = (i+k, i, k)
            if s not in s_l:
                s_l.append(s)
    return s_l

Helper function III - Base on the logic, check if one and only one sum in sum list for a number is in the possible sum list p:

#function: boolean, () = check_sume_in_p(sum_list, p)
#for a particular number, check if the sum of its factor paris are in the possible sum list. One and only one in possible list is what we want, which will be returned together with a true flag
def check_sum_in_p(sum_list, p):
    #only 0 or 1 pair in the sum list, not suitable
    if len(sum_list) == 0 or len(sum_list) == 1:
        return False, ()

    #store the pairs whose sums are in possible list
    s = [] 
        for k in sum_list:
            if k[0] in p:
                s.append(k)

    #if just one sum in possible list, this is we want
    if len(s) == 1: 
        return True, s[0]
    else:
        return False, ()

Now do the brute-force search among all the products of two numbers between 2-99

#check all the possible multiplicands between two number in 2-99
li = []
for i in range(2, 100):
    for j in range(2, 100):
        if not j == i:
            m = i*j
            s_list = find_sum_list(m)
            #here p is the possible list shown above
            b, s = check_sum_in_p(s_list, p)

            if b and s not in li:
                    li.append(s)

print "sum list from possible multiplication: "
print li
print len(li)

This is a long list which contains 678 possible pairs. We know the answer must be in this list li.

sum list from possible multiplication: 
[(11, 9, 2), (11, 8, 3), (11, 7, 4), (27, 25, 2), (17, 13, 4), (29, 27, 2), (23, 19, 4), (27, 23, 4), (35, 32, 3), (51, 49, 2), (29, 25, 4), (23, 16, 7), (35, 31, 4), (27, 20, 7), (51, 48, 3), (41, 37, 4), (27, 19, 8), (37, 32, 5), (47, 43, 4), (27, 16, 11), (51, 47, 4), (67, 64, 3), (35, 27, 8), (79, 76, 3), (41, 32, 9), (29, 16, 13), (57, 53, 4), (59, 55, 4), (37, 29, 8), (65, 61, 4), (57, 52, 5), (71, 67, 4), (47, 40, 7), (77, 73, 4), (35, 19, 16), (51, 44, 7), (83, 79, 4), (111, 108, 3), (166, 164, 2), (87, 83, 4), (178, 176, 2), (93, 89, 4), (190, 188, 2), (192, 190, 2), (57, 49, 8), (147, 145, 2), (41, 25, 16), (53, 43, 10), (57, 47, 10), (137, 134, 3), (161, 158, 3), (195, 192, 3), (103, 97, 6), (151, 147, 4), (135, 133, 2), (65, 58, 7), (71, 64, 7), (123, 119, 4), (51, 37, 14), (178, 175, 3), (192, 189, 3), (89, 82, 7), (101, 94, 7), (105, 98, 7), (67, 59, 8), (47, 31, 16), (79, 71, 8),...

The hidden special one

Mr. S: well, I will know if you know.

Among such a long list li, how could we identify the particular result? Here is a special case:

the sum that only appears once in the list.

Only in this case, Mr. S could find a unique pair of numbers corresponding to the sum, otherwise ambiguity remains.

Let’s count the occurrence of sums of the 678 possible pairs in list li and print it out

#find the occurrence of sum (first value in the tuple) in li
sum_list = []
oc = []
for k in li:
    sum = k[0]
    if sum not in l:
        sum_list.append(sum)
        oc.append(0)
    else:
        oc[sum_list.index(sum)] += 1

result = zip(sum_list, oc)
print result

In the list, (17, 0) is the only one with 1 occurance. This is excatly what we are looking for. Look back in list li we find (17, 4, 13). These two numbers are 4 and 13!

[(11, 2), (27, 4), (17, 0), (29, 2), (23, 1), (35, 3), (51, 8), (41, 3), (37, 1), (47, 3), (67, 2), (79, 3), (57, 8), (59, 3), (65, 2), (71, 3), (77, 4), (83, 3), (111, 14), (166, 20), (87, 9), (178, 16), (93, 9), (190, 12), (192, 18), (147, 11), (53, 3), (137, 4), (161, 6), (195, 5), (103, 7), (151, 9), (135, 11), (123, 11), (89, 5), (101, 3), (105, 11), (133, 9), (188, 16), (196, 10), (174, 23), (175, 12), (169, 8), (177, 9), (183, 10), (107, 5), (189, 8), (125, 6), (129, 11), (187, 4), (119, 6), (95, 5), (109, 4), (171, 13), (141, 12), (149, 5), (182, 14), (194, 9), (113, 3), (143, 9), (155, 8), (115, 7), (153, 11), (117, 6), (184, 16), (127, 8), (159, 12), (191, 4), (97, 1), (121, 4), (131, 4), (145, 7), (193, 6), (139, 5), (165, 9), (157, 6), (181, 7), (163, 5), (167, 6), (173, 5), (179, 5), (185, 4)]

Some more information about this quiz can be found online. The Impossible Puzzle, also named Sum and Product Puzzle is a puzzle called “impossible” because it seems to lack sufficient information for a solution. It was first published in 1969 by Hans Freudenthal, and the name Impossible Puzzle was coined by Martin Gardner. The puzzle is solvable, though not easily.

I feel good about straight forward logic but start to get headache when math comes in the way :( Maybe this is the reason I could not survive in Acedamia. Anyway, I am back to my little blog and feel really good.