# 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.

-
Did you make this up? Do you know if this has a solution? – Aryabhata Feb 1 '12 at 22:46
@Aryabhata I know this has a solution. This is found in texts available in India for people preparing for Math Olympiads in the form of Census-Taker and ages and blah. Too lazy to write down a solution, though! – user21436 Feb 1 '12 at 22:54
while, the rule states: “I don't know all the numbers” does not necessarily mean that they know any of the numbers. (this is of course mathematically true apriori) – confused Feb 1 '12 at 23:15
Just a comment: Do not remove the question by editing, and replacing it with "Thanks I got it!". Since other people will come to this thread, leaving it that way makes it unreadable for everyone. (In the event that you want to remove the question, it is possible to delete it by clicking the delete button.) – Eric Feb 4 '12 at 13:46
And if you have found the solution yourself, then instead of deleting the question, the best thing for all concerned is if you post the solution as an answer to your own question and accept it! – Rahul Narain Feb 4 '12 at 14:19

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():
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

-
 Can you please explain what function "def any(l)" is doing?and how? – Saurabh Jun 23 '12 at 13:44 The function any checks whether the intersection of all sets in its input is non-empty. – Yuval Filmus Jun 26 '12 at 0:51 Lets say I am Chris so I know the arithmetic mean of the squares i.e. I know 654 = $a^2+b^2+c^2$.So the possibilities for $(a,b,c)$ are $(17,14,13),(19,17,2), (22,11,7),(22,13,1),(23,10,5),(23,11,2),(25,5,2)$.So by only knowing this how can I comment “I don't know all of the numbers” because this would mean I know at least one number.How can I deduce at least one number? – Saurabh Jun 26 '12 at 17:10 That's not how I understood it. I don't know all the numbers is just the negation of I know all the numbers. – Yuval Filmus Jun 27 '12 at 2:53 oh Thanks now I fully understood it. – Saurabh Jun 28 '12 at 11:30

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)

169217
36210
4196
1710
1681
1669
3
(5, 10, 23)
(66, 87, 91)
(80, 81, 84)

-
 A comment on the other posted solution: all_numbers() is wrong. b could be 101, c could be 102. – phunctor Jan 10 at 20:56 range(1,n+1) in Python means all the numbers between 1 and n, so we get all triples $(a,b,c)$ such that $1\leq c\leq b\leq a\leq 100$. – Yuval Filmus Jan 14 at 4:32