¿problema loco - tiene una solución? ¿Teoría del número tal vez?

Question

Algunos investigadores están tratando de descifrar un código que consiste en el descubrimiento de los valores de tres enteros. Ellos saben que están entre 1 y 100 (ambos inclusive), y que puede ser el mismo.

Cada uno de ellos tiene una pieza diferente de la información;

Alice sabe que la media geométrica

Bob sabe que la media aritmética

Chris sabe que la media aritmética de los cuadrados

Se reúnen para compartir información y romper el código, pero están siendo muy reservado en un intento de ocultar sus resultados de otra persona. Usted escuche su conversación;

Chris: "no sé todos los números"

Alicia: "yo no conozco a ninguno de los números"

Chris: "no es necesario que me diga eso, eso yo ya lo sabía"

Alice: "Bueno, ahora sé que todos los números!"

Chris: "todavía no sé de que todos los números"

Bob: "no sé todos los números"

Chris: "Argh, yo todavía no se conocen todos los números"

Bob: "Ah, ahora sé que todos los números"

"¡Ja!" le grito. Para que haya revelado los números. ¿Qué son?

Usted debe asumir estos investigadores siempre decir la verdad y hacer perfectos a las deducciones y los cálculos. Sin embargo, pueden no ser tan precisos como podrían ser; "no sé de que todos los números" no significa necesariamente que ellos saben que cualquiera de los números.

Nota: es posible Que desee utilizar un ordenador para resolver esto.

Answer 1

El código siguiente tarda 32 segundos en mi portátil y salidas el % respuesta única $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

Answer 2

Mientras tentado por los números primos y la teoría de los números, me fui en su lugar con un método general de sucesivas filtrado para representar la diluir el conocimiento agregado por las pistas. La primera vez que utiliza este método para un "cerebro" programa de hace 40 años. Mi jefe' kid mantenerse en vencer a mí, así que escribí un programa...

Huelga decir que este método es inútil, en general, para exponencial de los problemas.

Sin embargo, el siguiente programa se ejecuta en el 0.97 segundos en mi laptop, y se produce la respuesta correcta, entre otros. Estoy desconcertado, aunque. Me parece que han caído un par de bits de información en algún lugar, ya que mi respuesta no es única.

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)