Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
@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
2  
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
3  
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 Naslund Feb 4 '12 at 13:46
2  
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 Feb 4 '12 at 14:19
1  
@BR As the original author of this puzzle I can tell you that I devised this as a deliberate variant on a much older puzzle: en.wikipedia.org/wiki/Impossible_Puzzle. Ironically, the reason for its construction was because the 2 number puzzle was too easily solved by looking on the internet! –  Corone May 15 '13 at 15:57
show 8 more comments

2 Answers

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
share|improve this answer
    
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
add comment

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)
share|improve this answer
    
A comment on the other posted solution: all_numbers() is wrong. b could be 101, c could be 102. –  phunctor Jan 10 '13 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 '13 at 4:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.