13
$\begingroup$

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.

  • 0
    Did you make this up? Do you know if this has a solution?2012-02-01
  • 0
    This is a riddle that was proposed to me in a serious context, and is supposed to have an answer. I did not make it up, but have similar suspicions about the existence of a solution. Then, I would like to prove that it has no solution.2012-02-01
  • 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!2012-02-01
  • 0
    Aha, thanks Kannappan. Perhaps when you have a little more energy, you could enlighten us? Or, perhaps even just a clue? Thanks for your input, cheers.2012-02-01
  • 0
    In trying to find out where this problem came from, I ran across some Matlab code intended to solve it: http://www.mathworks.jp/matlabcentral/fileexchange/34575-two-cool-problems-solved-by-matlab-codes/content/MyCode_Prob2.m2012-02-01
  • 0
    Thanks, BR! That's really good. Although, this guy makes a mistake: % Part 1 : C says I don't know all of the numbers. % 2. It means that he knows at least one number which he deduced that % from the mean of square.2012-02-01
  • 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)2012-02-01
  • 0
    @BR: the solution to this problem, as well as the other one posted by that guy on matlabcentral are bunk!2012-02-01
  • 0
    confused, I agree, though by reading his solution, I see how to program a correct one! (Well, I can't guarantee it is correct, since I'm not going to actually program it.)2012-02-02
  • 0
    I agree, BR. It is a matter of brut force. This will be the way to prove it has an answer or perhaps has no answer... thanks, cheers2012-02-02
  • 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.)2012-02-04
  • 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!2012-02-04
  • 2
    @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: http://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!2013-05-15

2 Answers 2

3

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
  • 0
    Can you please explain what function "def any(l)" is doing?and how?2012-06-23
  • 0
    The function *any* checks whether the intersection of all sets in its input is non-empty.2012-06-26
  • 0
    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?2012-06-26
  • 1
    That's not how I understood it. I don't know all the numbers is just the negation of I know all the numbers.2012-06-27
  • 0
    oh Thanks now I fully understood it.2012-06-28
  • 0
    @user1963 It's a good opportunity to learn python, then. Python is very useful.2016-03-03
  • 0
    I wrote this answer over 4 years ago. To answer your question, I will need to read and understand the code, something which you can also do. So it makes more sense for you to do it. You can then write your own answer with a better explanation.2016-03-03
  • 1
    @YuvalFilmus: Indeed, my bad, I hadn't considered the possibility that the problem might not be fresh in your mind (sorry, I had overlooked the dates;)!).2016-03-03
2

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)
  • 0
    A comment on the other posted solution: all_numbers() is wrong. b could be 101, c could be 102.2013-01-10
  • 0
    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$.2013-01-14