Explanation of a solved puzzle' solution

Question

This question pertains to the solution of a puzzle offered some times ago here.

However, as suggested by the author of the original answer, it might be a good idea to rewrite a more fleshed out version of his answer as it has become difficult to understand the original version.

From the rest of the original answer we know the solution is (23,10,5). We also have a computer code that computes this solution. But there is very little explanation of the logic that lead to this code. Unfortunately, that (the reasoning), more than the actual solution, is what I am most interested in.

To put things in context, the puzzle starts like so:

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”

For Chris the list of candidates is (these all have the same sum of squares):

$$(17, 14, 13), (19, 17, 2), (22, 11, 7), (22, 13, 1), (23, 10, 5), (23, 11, 2), (25, 5, 2)$$

For Alice the list of candidates is (these all have the same geometric mean):

$$(23, 10, 5), (25, 23, 2), (46, 5, 5), (46, 25, 1), (50, 23, 1)$$

Now Chris adds:

Chris: “You didn't need to tell me that, I knew that already”

Alice: “Well now I know all the numbers!”

My question is: how does Alice uses this information to exclude the spurious numbers from her list?

---

So for example, the reason Chris says:

Chris: “You didn't need to tell me that, I knew that already”

is I believe as follows. Consider for example any element from Chris's list, say $C_1=(17, 14, 13)$. Chris knows that this element has the same fingerprint for Alice as:

$$A(C_1)=\{(17, 14, 13), (26, 17, 7), (34, 13, 7), (91, 17, 2), (91, 34, 1)\}$$

and the intersection of all the members of $A(C_1)$ is empty. This is I think the meaning of Alice's “I don't know any of the numbers”: She can't point to a single number she is sure will be in the solution.

Because this holds for each candidate solution $A(C_1),\ldots,A(C_7)$ in Chris's list, Chris already knows that all of Alice's candidate solutions must have an empty intersection (which is the meaning, I think, of Chris's "You didn't need to tell me that, I knew that already")

Answer 1

For closure, this formally summarizes the comments:

Alice has five candidates which we call $A_1, \dots, A_5$. For each of these candidates $A_i$, she can compute the list $C(A_i)$, which is the list of elements with the same sum of squares as $A_i$. In Alice's mind, the five lists $C(A_1),\dots,C(A_5)$ are the possible lists which Chris is looking at.

When Chris says "you didn't need to tell me that, I knew that already," he is telling Alice that the list $C(A_{i^*})$ he is looking at has the following property: $$\mbox{For every } j, \mbox{ the elements of the list } A(C(A_{i^*})_j) \mbox{ have empty intersection}.$$

Thus Alice can deduce the value of $i^*$, because there is only one $i = i^*$ for which the above statement holds. That is, for every $i \neq i^*$ the following (negation of the statement above) holds: $$\mbox{There exists } j \mbox{ such that the elements of the list } A(C(A_{i})_j) \mbox{ have nonempty intersection.}$$

---

Edit by the O.P.: I am adding to the answer the result of the computations to illustrate Michael Harrison's answer.

Alice knows that the geometric mean of the correct solution is $1150^{1/3}$. Given this information, she knows the correct solution is one of:

$$A=\{(23, 10, 5),(25, 23, 2),(46, 5, 5),(46, 25, 1),(50, 23, 1)\}$$

Consider the first element in this set. Let us call it $A_1$. The sum of squares of the elements in $A_1$ is 654. If $A_1$ were the correct solution, Chris's list would be:

$$C(A_1)=\{(17, 14, 13), (19, 17, 2), (22, 11, 7), (22, 13, 1), (23, 10, 5), (23, 11, 2), (25, 5, 2)\}$$

The members of $A(C(A_i)_j)$ are all elements that have same geometric mean as $C(A_i)_j$. For $C(A_1)_1$, these are:

$$A(C(A_1)_1)=\{(17, 14, 13), (26, 17, 7), (34, 13, 7), (91, 17, 2), (91, 34, 1)\}$$

As explained in Michael Harrison's answer above, the elements of $A(C(A_1)_1)$ have an empty intersection. The python code from the original answer can be used to show that the same holds for all the $A(C(A_1)_j)$'s (the code to produce these output is placed below this answer):

A(C_1)_1): [(17, 14, 13), (26, 17, 7), (34, 13, 7), (91, 17, 2), (91, 34, 1)]. Empty intersection: True
A(C_1)_2): [(19, 17, 2), (34, 19, 1), (38, 17, 1)]. Empty intersection: True
A(C_1)_3): [(14, 11, 11), (22, 11, 7), (77, 11, 2), (77, 22, 1)]. Empty intersection: True
A(C_1)_4): [(13, 11, 2), (22, 13, 1), (26, 11, 1)]. Empty intersection: True
A(C_1)_5): [(23, 10, 5), (25, 23, 2), (46, 5, 5), (46, 25, 1), (50, 23, 1)]. Empty intersection: True
A(C_1)_6): [(23, 11, 2), (23, 22, 1), (46, 11, 1)]. Empty intersection: True
A(C_1)_7): [(10, 5, 5), (25, 5, 2), (25, 10, 1), (50, 5, 1)]. Empty intersection: True

However, as explained in Michael Harrison's answer, the set corresponding to $i=1$ is the only one of Alice's 5 candidate solution for which the corresponding $A(C(A_i)_j)$ have an empty intersection for all $j$'s (the last code below can be easily modified to show that this in indeed the case).

Self contained code from original answer linked in the question:

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

Code to show all members of $A(C(A_1)_j)$:

tally()
f0=initial()
i=0;
L=ALICE[ALICE[0](23,10,5)]      #A_1,...,A_5
(a0,b0,c0)=L[i]:
M=CHRIS[CHRIS[0](a0,b0,c0)] #C(A_1)_j
j=0
for a1,b1,c1 in M:
     j=j+1
     P=ALICE[ALICE[0](a1,b1,c1)]
     print("A(C_"+str(i+1)+")_"+str(j)+"): "+str(P)+". Empty intersection: "+str(bool(~any(P))))