crazy problem - does it have a solution? number theory perhaps?
A few researchers are trying to crack a code which involves discovering the values of three integers. They know they are between 1 and 100 (inclusive), and that they may be the same.
They each have a different piece of information;
Alice knows the geometric mean
Bob knows the arithmetic mean
Chris knows the arithmetic mean of the squares
They get together to share information and crack the code, but they are being very secretive in an attempt to conceal their results from anyone else. You listen in to their conversation;
Chris: “I don't know all of the numbers”
Alice: “I don't know any of the numbers”
Chris: “You didn't need to tell me that, I knew that already”
Alice: “Well now I know all the numbers!”
Chris: “I still don't know all the numbers”
Bob: “I don't know all of the numbers either”
Chris: “Argh, I still don't know all the numbers”
Bob: “Ah - now I know all of the numbers”
“A ha!” you cry. For they have accidentally revealed the numbers to you. What are they?
You should assume these researchers always tell the truth and make perfect deductions and calculations. However, they might not always be as precise as they could be; “I don't know all the numbers” does not necessarily mean that they know any of the numbers.
Note: You might want to use a computer to solve this.
The code below takes 32 seconds to run on my laptop and outputs the unique answer $23,10,5$.
def add_to_hist(hist, what, where):
if where not in hist:
hist[where] = []
hist[where].append(what)
def all_numbers():
for a in range(1,101):
for b in range(1,a+1):
for c in range(1,b+1):
yield a,b,c
def tally():
global ALICE, BOB, CHRIS
ALICE = dict()
BOB = dict()
CHRIS = dict()
for a,b,c in all_numbers():
add_to_hist(ALICE, (a,b,c), a*b*c)
add_to_hist(BOB, (a,b,c), a+b+c)
add_to_hist(CHRIS, (a,b,c), a*a+b*b+c*c)
ALICE[0] = lambda a,b,c: a*b*c
BOB[0] = lambda a,b,c: a+b+c
CHRIS[0] = lambda a,b,c: a*a+b*b+c*c
def get(a, b, c, who):
return who[who[0](a,b,c)]
def any(l):
"whether any number is known from list l"
s = set(list(l)[0])
for x in l:
s.intersection_update(set(x))
return len(s) > 0
def filter_all(curr, who):
"I don't know all the numbers"
return [(a,b,c) for (a,b,c) in curr if len(get(a,b,c,who)) > 1]
def filter_any(curr, who):
"I don't know any of the numbers"
return [(a,b,c) for (a,b,c) in curr if not any(get(a,b,c,who))]
def filter_know(curr, who):
"I know all the numbers"
return [(a,b,c) for (a,b,c) in curr if len(get(a,b,c,who)) == 1]
def special(l, who):
"who doesn't know any of the numbers for all possibilities in l"
for a,b,c in l:
if any(get(a,b,c,who)):
return False
return True
def filter_special(curr, who1, who2):
"who1 already knew that who2 didn't know any of the numbers"
return [(a,b,c) for (a,b,c) in curr if special(get(a,b,c,who1), who2)]
def initial():
return [(a,b,c) for (a,b,c) in all_numbers()]
def do_filter(f_bef, f_aft):
global ALICE, BOB, CHRIS
for (a,b,c) in set(f_bef).difference(set(f_aft)):
for h in [ALICE, BOB, CHRIS]:
get(a, b, c, h).remove((a,b,c))
def run():
tally()
f0 = initial()
f1 = filter_all(f0, CHRIS)
do_filter(f0, f1)
f2 = filter_special(f1, CHRIS, ALICE)
do_filter(f1, f2)
f3 = filter_know(f2, ALICE)
do_filter(f2, f3)
f4 = filter_all(f3, CHRIS)
do_filter(f3, f4)
f5 = filter_all(f4, BOB)
do_filter(f4, f5)
f6 = filter_all(f5, CHRIS)
do_filter(f5, f6)
f7 = filter_know(f6, BOB)
return f7
While tempted by primes and number theory, I went instead with a general method of successive filtering to represent the dilute knowledge added by the clues. I first used this method for a "mastermind" program 40 years ago. My boss' kid kept on beating me, so I wrote a program...
Needless to say this method is worthless in general for exponential problems.
Nevertheless the program below runs in 0.97 seconds on my laptop, and produces the right answer, among others. I'm puzzled though. I seem to have dropped a couple of bits of information somewhere, since my answer is not unique.
from itertools import *
CHRIS = 3
ALICE = 4
BOB = 5
SIZE = 101
UNIVERSAL = set(xrange(SIZE))
def build(SIZE):
for a in xrange(1,SIZE):
for b in xrange(a,SIZE):
for c in xrange(b,SIZE):
chris = a*a + b*b + c*c
alice = a * b * c
bob = a + b + c
yield (a, b, c, chris, alice, bob)
def partition(ndx, iterable_tuples):
p = {}
for t in iterable_tuples:
assert type(t) == tuple and ndx in (CHRIS, ALICE, BOB)
v = t[ndx]
if p.get(v) is None:
p[v] = [t]
else:
p[v].append(t)
return p
def accept(predicate, partition):
return list(chain.from_iterable(v for k,v in partition.items() if predicate(k,v)))
def reject(predicate, partition):
return list(chain.from_iterable(v for k,v in partition.items() if not predicate(k,v)))
def knows_all(k, v):
return len(v) == 1
def knows_none(k, v):
list_of_sets = map(lambda t: set(t[:3]), v)
common_to_all = reduce(set.intersection, list_of_sets, UNIVERSAL)
return len(common_to_all) == 0
possibles = [tupl for tupl in build(SIZE)]
# Chris: "I don't know all of the numbers"
chris1 = partition(CHRIS, possibles)
chris_doesnt_know_all = reject(knows_all, chris1)
print len(chris_doesnt_know_all)
# Alice: "I don't know any of the numbers"
alice1 = partition(ALICE, chris_doesnt_know_all)
alice_doesnt_know_any = accept(knows_none, alice1)
# Chris: "You didn't need to tell me that, I knew that already"
alice_knows_some = list(set(chris_doesnt_know_all) - set(alice_doesnt_know_any))
ruled_out_set = set(partition(CHRIS, alice_knows_some).keys())
alice_knows_none = list(chain.from_iterable(
[v for (k,v) in chris1.items() if k not in ruled_out_set]
)
)
print len(alice_knows_none)
# Alice: "Well now I know all the numbers!"
alice2 = partition(ALICE, alice_knows_none)
alice_knows_all = accept(knows_all, alice2)
print len(alice_knows_all)
# Chris: "I still don't know all of the numbers"
chris2 = partition(CHRIS, alice_knows_all)
chris_doesnt_know_all = reject(knows_all, chris2)
print len(chris_doesnt_know_all)
# Bob: "I don't know all of the numbers either
bob1 = partition(BOB, chris_doesnt_know_all)
bob_doesnt_know_all = reject(knows_all, bob1)
print len(bob_doesnt_know_all)
# Chris: "Argh, I still don't know all the numbers"
chris3 = partition(CHRIS, bob_doesnt_know_all)
chris_doesnt_know_all = reject(knows_all, chris3)
print len(chris_doesnt_know_all)
# Bob: "Ah - now I know all of the numbers"
bob2 = partition(BOB, chris_doesnt_know_all)
bob_knows_all = accept(knows_all, bob2)
print len(bob_knows_all)
for answer in bob_knows_all:
print answer[:3]
169217
36210
4196
1710
1681
1669
3
(5, 10, 23)
(66, 87, 91)
(80, 81, 84)