Submarine puzzle: What do I know?

By Sai Nane2026-03-05

In May 2023, a friend asked me to replicate some interesting results from a logic puzzle. TED-Ed had published a logic puzzle by Alex Rosenthal, where the viewer is asked to find two numbers.

The video implied there was one unique solution, showing their reasoning, but my friend had found two solutions, and wanted to see if I would do the same. Instead, knowing that two existed, I found three. We joked that we should post this online, and that knowing that three solutions existed, someone would find four.

This post follows our original reasoning, and presents a retraction and additional analysis from about halfway through.

The puzzle

The video summarizes the puzzle on a single page:

Spoilers for the puzzle follow, below.

Official solution

Officially, the solution comes from the hidden state (1, 4), with the sum 5, and product 4.

Transcribed discussion and official solution from video

Ignorance based puzzles like this are notoriously difficult to work through. The trick is to put yourself in the heads of both characters, and narrow down the possibilities based on what they know, or don’t know.

So let’s start with A’s first statement (“I don’t know whether you know my number”). It means that B could conceivably have something with the potential to reveal A’s number, but isn’t guaranteed to. That doesn’t sound very definitive, but it can lead us to a major insight: The only scenarios where B could know A’s number, are when there’s exactly one valid way to factor B’s number.

Try factoring a few, and you’ll find the pattern. It could be prime, where the product must be of 1 and itself, or, it could be the product of 1 and the square of a prime, such as 4. In both cases, there’s exactly one sum. For a number like 8, factoring it into 2 and 4, or 1, 2, and 4, creates too many options. Because the boss’s numbers must be less than 7, A’s list of B’s possibilities only has these four numbers:

1x2

1x3

1x4

1x5

Here’s where we can conclude a major clue: To think B could have these numbers, A’s number must be a sum of their factors, so 3, 4, 5, or 6. We can eliminate 3 and 4, because if the sum was either, the product could only be 2, or 3. In which case, A would know that B already knows A’s number, contradicting A’s statement. 5 and 6 however, are in play, because they can become sums in multiple ways. The need to consider this is one of the most difficult parts of this puzzle.

The crucial thing to remember is that there’s no guarantee that B’s number is on A’s list. These are just the possibilities from A’s perspective, that would allow B to deduce A’s number. That ambiguity forces us to go through unintuitive, multi-step processes, like: Consider a product, see what sums can result from its factors, then break those apart, and see what products can result. We’ll soon have to do something similar going from sums to products, and back to sums. But now we know, when A made his first statement, he must have been holding either 5 or 6. B has access to the same information we do, so he knows this too.

Let’s review what’s in each brain at this point: Everyone knows a lot about the sum, but only B knows the product. Now let’s look at the first part of B’s statement (“I know your number”). What if A’s number was 5? That could be from 1+4, or 2+3, in which case, B would have either 4 or 6. 4 would tell B what A had, like he said, because there’s only one option to make the product, four times one. 6 on the other hand, could be broken down three ways. Which sum like so: 2+3=5, 1+2+3=6, 1+6=7. 7 isn’t on B’s list of possible sums, but 5 and 6 both are. Meaning, that B wouldn’t know whether A’s number was 5 or 6. And we can eliminate this option, because it contradicts his statement. So this is great, 5 and 4 could be the override code.

But how do we know it’s the only one? Let’s consider if A’s number was 6. Which would be 1+5, 2+4, or 1+2+3, giving B 1x5=5, 2x4=8, or 1x2x3=6 respectively. If B had 5, he’d know that A had 6, and if B had 8, the possibilities for A would be 2+4=6, or 1+2+4=7. Only 6 is on the list of possible sums. So B would again know that A had 6. To summarize, if A had 6, he still wouldn’t know whether B had 5 or 8. That contradicts the second half of what B said (“now I know you know my number too”), and 5 and 4 must be the correct codes.

Second “solution”

My friend wrote a script to brute force the solution, and found another solution, with the hidden state (1, 5), with the sum 6, and product 5.

So how is this consistent with the final paragraph in the official solution, claiming “if A had 6, he still wouldn’t know whether B had 5 or 8”?

When A makes their first statement, A knows only that the sum is 6. Here, the potential hidden states are (1, 5), (2, 4), and (1, 2, 3). A doesn’t know which of these is the hidden state, so A doesn’t know whether B has 5, 8, or 6. This is consistent with A’s first statement (“I don’t know whether you know my number”).

When B makes their statement, B knows the product is 5, which only comes from the hidden state (1, 5). So B knows the full hidden state, and therefore that A has 6. This is consistent with the first part of B’s statement (“I know your number”).

For the second half of B’s statement, B knows that A knew the hidden states could be (1, 5), (2, 4), or (1, 2, 3). The A in B’s world initially didn’t know which of these is the hidden state, but filters possible worlds based on B’s statement, that B knows A’s number. Follow A considering each of these worlds in turn:

Hidden state `(1, 5)`

In this world, A’s model of B knows A’s number, as above. A correctly does not filter this world out.

Hidden state `(2, 4)`

In this world, A’s model of B has 8, which could come from the hidden states (2, 4) or (1, 2, 4). A’s model of B’s model of A could have either 6 or 7, so B doesn’t know A’s number. This contradicts B’s statement that B knows A’s number, so A rules this world out.

Hidden state `(1, 2, 3)`

In this world, A’s model of B has 6, which could come from the hidden states (1, 2, 3), (1, 6), or (2, 3). A’s model of B’s model of A could have either 5, 6, or 7, so B doesn’t know A’s number. This contradicts B’s statement that B knows A’s number, so A rules this world out.

Synthesis

After filtering, A is left with only the world where the hidden state is (1, 5), so A now knows B’s number. This is consistent with the second half of B’s statement (“now I know you know my number too”), despite the official solution’s claim otherwise.

Script

from collections import Counter
from pprint import pprint

basis = [1,2,3,4,5,6]

def get_all_subsets(l):
    if l == []:
        return [[]]
    subs = get_all_subsets(l[1:])
    return subs + [[l[0]] + el for el in subs]

all_subsets = get_all_subsets(basis)
all_subsets = sorted([sub for sub in all_subsets if len(sub) >= 2])
# all_subsets = sorted([sub for sub in all_subsets if len(sub) >= 2])
# all_subsets = sorted([sub for sub in all_subsets if sum(sub) < 9])

def product(sub):
    if len(sub) == 0:
        return 1
    return sub[0] * product(sub[1:])

def sort_keys(counter: Counter) -> Counter:
    out = Counter()
    for key in sorted(counter.keys()):
        out[key] = counter[key]
    return out

def print_sorted_by_key(counter: Counter) -> Counter:
    print('{')
    for key in sorted(counter.keys()):
        print(f'    {key}: {counter[key]},')
    print('}')


sum_counter = Counter(sum(sub) for sub in all_subsets)
product_counter = Counter(product(sub) for sub in all_subsets)

#debug
print_sorted_by_key(sum_counter)
print_sorted_by_key(product_counter)

# solve it one way
for sub in all_subsets:
    if sum_counter[sum(sub)] > 1 and product_counter[product(sub)] == 1:
        display(sub, sum(sub), product(sub))

# solve it another way
for answer_sum in range(100):
    if sum_counter[answer_sum] == 0:
        continue
    has_some_determined = False
    has_some_undetermined = False
    for sub in all_subsets:
        if not sum(sub) == answer_sum:
            continue
        if product_counter[product(sub)] > 1:
            has_some_undetermined += True
        if product_counter[product(sub)] == 1:
            has_some_determined += True

    if not (has_some_determined and has_some_undetermined):
        continue

    display(answer_sum, has_some_determined, has_some_undetermined)

Third “solution”

I wrote a script of my own to brute force the solution. This found both the official solution, and the second solution my friend found, but also a third solution: the hidden state (3, 4, 5, 6), with the sum 18, and product 360.

Interestingly, this diverges from the initial discussion in the official solution. Rather than the set of chosen numbers being too small for B to have ambiguity about possible decompositions, the hidden state is too full for B to have ambiguity about possible decompositions.

The insight is that B gets to narrow their set of hidden states, based on A’s first statement, before they make their own statement.

My friend was able to replicate this finding by broadening what worlds are considered unambiguous for B, based on A’s first statement:

product_counter = Counter(product(sub) for sub in all_subsets)

becoming:

product_counter_unique_sum = Counter(product(sub) for sub in all_subsets if sum_counter[sum(sub)] > 1)

Script

from itertools import chain, combinations
from functools import reduce
from collections import defaultdict

def powerset(iterable):
    """powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"""
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

a_to_inputs = defaultdict(lambda: set())
b_to_inputs = defaultdict(lambda: set())

def prod(iterable):
    return reduce(lambda a,b: a*b, iterable, 1)

for l in powerset((1,2,3,4,5,6)):
    if len(l) <= 1:
        # Must have at least two elements
        continue
    a_to_inputs[sum(l)].add(l)
    b_to_inputs[prod(l)].add(l)

display(a_to_inputs)
display(b_to_inputs)

defaultdict(<function __main__.<lambda>()>,
            {3: {(1, 2)},
             4: {(1, 3)},
             5: {(1, 4), (2, 3)},
             6: {(1, 2, 3), (1, 5), (2, 4)},
             7: {(1, 2, 4), (1, 6), (2, 5), (3, 4)},
             8: {(1, 2, 5), (1, 3, 4), (2, 6), (3, 5)},
             9: {(1, 2, 6), (1, 3, 5), (2, 3, 4), (3, 6), (4, 5)},
             10: {(1, 2, 3, 4), (1, 3, 6), (1, 4, 5), (2, 3, 5), (4, 6)},
             11: {(1, 2, 3, 5), (1, 4, 6), (2, 3, 6), (2, 4, 5), (5, 6)},
             12: {(1, 2, 3, 6), (1, 2, 4, 5), (1, 5, 6), (2, 4, 6), (3, 4, 5)},
             13: {(1, 2, 4, 6), (1, 3, 4, 5), (2, 5, 6), (3, 4, 6)},
             14: {(1, 2, 5, 6), (1, 3, 4, 6), (2, 3, 4, 5), (3, 5, 6)},
             15: {(1, 2, 3, 4, 5), (1, 3, 5, 6), (2, 3, 4, 6), (4, 5, 6)},
             16: {(1, 2, 3, 4, 6), (1, 4, 5, 6), (2, 3, 5, 6)},
             17: {(1, 2, 3, 5, 6), (2, 4, 5, 6)},
             18: {(1, 2, 4, 5, 6), (3, 4, 5, 6)},
             19: {(1, 3, 4, 5, 6)},
             20: {(2, 3, 4, 5, 6)},
             21: {(1, 2, 3, 4, 5, 6)}})



defaultdict(<function __main__.<lambda>()>,
            {2: {(1, 2)},
             3: {(1, 3)},
             4: {(1, 4)},
             5: {(1, 5)},
             6: {(1, 2, 3), (1, 6), (2, 3)},
             8: {(1, 2, 4), (2, 4)},
             10: {(1, 2, 5), (2, 5)},
             12: {(1, 2, 6), (1, 3, 4), (2, 6), (3, 4)},
             15: {(1, 3, 5), (3, 5)},
             18: {(1, 3, 6), (3, 6)},
             20: {(1, 4, 5), (4, 5)},
             24: {(1, 2, 3, 4), (1, 4, 6), (2, 3, 4), (4, 6)},
             30: {(1, 2, 3, 5), (1, 5, 6), (2, 3, 5), (5, 6)},
             36: {(1, 2, 3, 6), (2, 3, 6)},
             40: {(1, 2, 4, 5), (2, 4, 5)},
             48: {(1, 2, 4, 6), (2, 4, 6)},
             60: {(1, 2, 5, 6), (1, 3, 4, 5), (2, 5, 6), (3, 4, 5)},
             72: {(1, 3, 4, 6), (3, 4, 6)},
             90: {(1, 3, 5, 6), (3, 5, 6)},
             120: {(1, 2, 3, 4, 5), (1, 4, 5, 6), (2, 3, 4, 5), (4, 5, 6)},
             144: {(1, 2, 3, 4, 6), (2, 3, 4, 6)},
             180: {(1, 2, 3, 5, 6), (2, 3, 5, 6)},
             240: {(1, 2, 4, 5, 6), (2, 4, 5, 6)},
             360: {(1, 3, 4, 5, 6), (3, 4, 5, 6)},
             720: {(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6)}})

initially_ambiguous_for_a = {k:v for k,v in a_to_inputs.items() if len(v)>1}

display(initially_ambiguous_for_a)

{5: {(1, 4), (2, 3)},
 6: {(1, 2, 3), (1, 5), (2, 4)},
 7: {(1, 2, 4), (1, 6), (2, 5), (3, 4)},
 8: {(1, 2, 5), (1, 3, 4), (2, 6), (3, 5)},
 9: {(1, 2, 6), (1, 3, 5), (2, 3, 4), (3, 6), (4, 5)},
 10: {(1, 2, 3, 4), (1, 3, 6), (1, 4, 5), (2, 3, 5), (4, 6)},
 11: {(1, 2, 3, 5), (1, 4, 6), (2, 3, 6), (2, 4, 5), (5, 6)},
 12: {(1, 2, 3, 6), (1, 2, 4, 5), (1, 5, 6), (2, 4, 6), (3, 4, 5)},
 13: {(1, 2, 4, 6), (1, 3, 4, 5), (2, 5, 6), (3, 4, 6)},
 14: {(1, 2, 5, 6), (1, 3, 4, 6), (2, 3, 4, 5), (3, 5, 6)},
 15: {(1, 2, 3, 4, 5), (1, 3, 5, 6), (2, 3, 4, 6), (4, 5, 6)},
 16: {(1, 2, 3, 4, 6), (1, 4, 5, 6), (2, 3, 5, 6)},
 17: {(1, 2, 3, 5, 6), (2, 4, 5, 6)},
 18: {(1, 2, 4, 5, 6), (3, 4, 5, 6)}}

inputs_given_ambiguous_a = reduce(lambda a,b: a.union(b), initially_ambiguous_for_a.values())

# --- just for fun, not used later

initially_unambiguous_for_b = {k:v for k,v in b_to_inputs.items() if len(v) == 1}

inputs_given_unambiguous_b = reduce(lambda a,b: a.union(b), initially_unambiguous_for_b.values())

# Initially unambiguous for b (without necessarily being ambiguous for A):")
display(initially_unambiguous_for_b)

# --- end just for fun

{2: {(1, 2)}, 3: {(1, 3)}, 4: {(1, 4)}, 5: {(1, 5)}}

for k,v in b_to_inputs.items():
    v.intersection_update(inputs_given_ambiguous_a)

unambiguous_for_b = {k:v for k,v in b_to_inputs.items() if len(v) == 1}

# Unambiguous for b, given that it was ambiguous for A:
display(unambiguous_for_b)

{4: {(1, 4)}, 5: {(1, 5)}, 360: {(3, 4, 5, 6)}}

inputs_given_unambiguous_b = reduce(lambda a,b: a.union(b), unambiguous_for_b.values())

for k,v in a_to_inputs.items():
    v.intersection_update(inputs_given_unambiguous_b)

unambiguous_for_a = {k:v for k,v in a_to_inputs.items() if len(v) == 1}

# Now unambiguous for a:
display(unambiguous_for_a)

{5: {(1, 4)}, 6: {(1, 5)}, 18: {(3, 4, 5, 6)}}

Retraction: What do I know?

That was my reasoning at the time.

My reasoning was wrong.

I realized when rewatching the video, having tracked it down years later for this post. At the time, I solved for ambiguous hidden states, rather than ambiguous numbers for the counterparty.

A’s first sentence is not “I don’t know the hidden set”. It is “I don’t know whether you know my number”.

By A’s statement, A must have a number permitting both worlds where B would know A’s sum, and worlds where B would not know A’s sum. This is a statement about B’s knowledge, not about the hidden state.

My third solution fails at A’s statement

If A has 18, A knows the hidden states can be {(3, 4, 5, 6), (1, 2, 4, 5, 6)}:

If (3, 4, 5, 6), B knows 360, which for A can be {(3, 4, 5, 6)=18, (1, 3, 4, 5, 6)=19}. B does not initially know A’s number.
If (1, 2, 4, 5, 6), B knows 240, which for A can be {(2, 4, 5, 6)=17, (1, 2, 4, 5, 6)=18}. B does not initially know A’s number.

Either way, B does not initially know A’s number, and so A cannot make the first statement “I don’t know whether you know my number.”

The second solution passes A’s statement

If A has 6, the hidden states can be {(2, 4), (1, 2, 3), (1, 5)}:

If (2, 4), B knows 8, which for A can be {(2, 4)=6, (1, 2, 4)=7}. B does not initially know A’s number.
If (1, 2, 3), B knows 6, which for A can be {(2, 3)=5, (1, 6)=7, (1, 2, 3)=6}. B does not initially know A’s number.
If (1, 5), B knows 5, which for A can be {(1, 5)=6}. B would then initially know A’s number.

B might or might not initially know A’s number. A can make the first statement “I don’t know whether you know my number.”

Valid states after A’s statement

Prior to any statement being made, the hidden states where B would know A’s number are {(1, 2), (1, 3), (1, 4), (1, 5)}. This was generated by a revised script, available at the end of this section.

In order for A to make their statement, A must have a number consistent with a world which is one of these hidden states, and a world which is not one of these hidden states.

The states where A doesn’t know whether B knows A’s number are {(1, 2, 3), (1, 4), (1, 5), (2, 3), (2, 4)}. This is public knowledge: Both A and B have at least the same information that we have, and can deduce this.

Grouping these five states by what A and B would have been given:

Minion A “Sum”:

5: {(1, 4), (2, 3)}
6: {(1, 2, 3), (1, 5), (2, 4)}

Minion B “Product”:

4: {(1, 4)}
5: {(1, 5)}
6: {(1, 2, 3), (2, 3)}
8: {(2, 4)}

Valid states after the first half of B’s statement

B indicates that they know A’s number. This means that B cannot have been given 6, and so states {(1, 2, 3), (2, 3)} are filtered out (publicly).

Minion A “Sum”:

5: {(1, 4)}
6: {(1, 5), (2, 4)}

Minion B “Product”:

4: {(1, 4)}
5: {(1, 5)}
8: {(2, 4)}

The second solution fails at B’s second clause

B indicates that now they know that A knows B’s number, too. This means that A cannot have been given 6, and so states {(1, 5), (2, 4)} are filtered out (publicly).

The only remaining valid state is (1, 4), with the sum 5, and product 4.

Revised script

from collections import defaultdict
from itertools import chain, combinations
from functools import reduce
from typing import Iterable
import operator

def powerset[T](iterable: Iterable[T]) -> Iterable[tuple[T, ...]]:
    """powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"""
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def product[T](iterable: Iterable[T]) -> T:
    return reduce(operator.mul, iterable, 1)

def union[T](sets: Iterable[set[T]]) -> set[T]:
    return set().union(*sets)

type HiddenState = tuple[int, ...]
type IndexedStates = defaultdict[int, set[HiddenState]]

def group_states_by_prodsum(states: Iterable[HiddenState]) -> tuple[IndexedStates, IndexedStates]:
    """Group states by what A and B would be given"""
    a_to_states: IndexedStates = defaultdict(set)
    b_to_states: IndexedStates = defaultdict(set)

    for l in states:
        a_to_states[sum(l)].add(l)
        b_to_states[product(l)].add(l)

    return a_to_states, b_to_states

# States grouped by minion info, knowing that the state is a subset of {1,2,3,4,5,6} with at least 2 elements:

initial_a_to_states, initial_b_to_states = group_states_by_prodsum((subset for subset in powerset((1,2,3,4,5,6)) if len(subset) >= 2))

display(initial_a_to_states)
display(initial_b_to_states)

defaultdict(set,
            {3: {(1, 2)},
             4: {(1, 3)},
             5: {(1, 4), (2, 3)},
             6: {(1, 2, 3), (1, 5), (2, 4)},
             7: {(1, 2, 4), (1, 6), (2, 5), (3, 4)},
             8: {(1, 2, 5), (1, 3, 4), (2, 6), (3, 5)},
             9: {(1, 2, 6), (1, 3, 5), (2, 3, 4), (3, 6), (4, 5)},
             10: {(1, 2, 3, 4), (1, 3, 6), (1, 4, 5), (2, 3, 5), (4, 6)},
             11: {(1, 2, 3, 5), (1, 4, 6), (2, 3, 6), (2, 4, 5), (5, 6)},
             12: {(1, 2, 3, 6), (1, 2, 4, 5), (1, 5, 6), (2, 4, 6), (3, 4, 5)},
             13: {(1, 2, 4, 6), (1, 3, 4, 5), (2, 5, 6), (3, 4, 6)},
             14: {(1, 2, 5, 6), (1, 3, 4, 6), (2, 3, 4, 5), (3, 5, 6)},
             15: {(1, 2, 3, 4, 5), (1, 3, 5, 6), (2, 3, 4, 6), (4, 5, 6)},
             16: {(1, 2, 3, 4, 6), (1, 4, 5, 6), (2, 3, 5, 6)},
             17: {(1, 2, 3, 5, 6), (2, 4, 5, 6)},
             18: {(1, 2, 4, 5, 6), (3, 4, 5, 6)},
             19: {(1, 3, 4, 5, 6)},
             20: {(2, 3, 4, 5, 6)},
             21: {(1, 2, 3, 4, 5, 6)}})



defaultdict(set,
            {2: {(1, 2)},
             3: {(1, 3)},
             4: {(1, 4)},
             5: {(1, 5)},
             6: {(1, 2, 3), (1, 6), (2, 3)},
             8: {(1, 2, 4), (2, 4)},
             10: {(1, 2, 5), (2, 5)},
             12: {(1, 2, 6), (1, 3, 4), (2, 6), (3, 4)},
             15: {(1, 3, 5), (3, 5)},
             18: {(1, 3, 6), (3, 6)},
             20: {(1, 4, 5), (4, 5)},
             24: {(1, 2, 3, 4), (1, 4, 6), (2, 3, 4), (4, 6)},
             30: {(1, 2, 3, 5), (1, 5, 6), (2, 3, 5), (5, 6)},
             36: {(1, 2, 3, 6), (2, 3, 6)},
             40: {(1, 2, 4, 5), (2, 4, 5)},
             48: {(1, 2, 4, 6), (2, 4, 6)},
             60: {(1, 2, 5, 6), (1, 3, 4, 5), (2, 5, 6), (3, 4, 5)},
             72: {(1, 3, 4, 6), (3, 4, 6)},
             90: {(1, 3, 5, 6), (3, 5, 6)},
             120: {(1, 2, 3, 4, 5), (1, 4, 5, 6), (2, 3, 4, 5), (4, 5, 6)},
             144: {(1, 2, 3, 4, 6), (2, 3, 4, 6)},
             180: {(1, 2, 3, 5, 6), (2, 3, 5, 6)},
             240: {(1, 2, 4, 5, 6), (2, 4, 5, 6)},
             360: {(1, 3, 4, 5, 6), (3, 4, 5, 6)},
             720: {(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6)}})

# Find worlds where A's statement is true:
# A has a number that could come both from worlds where B would know A's number, and worlds where B would not know A's number.

states_where_b_would_know_a: set[HiddenState] = union(v for v in initial_b_to_states.values() if len({sum(e) for e in v}) == 1)
display(states_where_b_would_know_a)

{(1, 2), (1, 3), (1, 4), (1, 5)}

ambiguous_whether_b_would_know = lambda v: any(e in states_where_b_would_know_a for e in v) and any(e not in states_where_b_would_know_a for e in v)
states_by_a_where_a_doesnt_know_whether_b_knows_a: dict[int, set[HiddenState]] = {k:v for k,v in initial_a_to_states.items() if ambiguous_whether_b_would_know(v)}
display(states_by_a_where_a_doesnt_know_whether_b_knows_a)

states_where_a_doesnt_know_whether_b_knows_a: set[HiddenState] = union(states_by_a_where_a_doesnt_know_whether_b_knows_a.values())
display(states_where_a_doesnt_know_whether_b_knows_a)

{5: {(1, 4), (2, 3)}, 6: {(1, 2, 3), (1, 5), (2, 4)}}



{(1, 2, 3), (1, 4), (1, 5), (2, 3), (2, 4)}

# We can now group these filtered states by what A and B would have been given.

# States grouped by minion info, also knowing that A doesn't know whether B knows A's number)

a_to_states_given_a_statement, b_to_states_given_a_statement = group_states_by_prodsum(states_where_a_doesnt_know_whether_b_knows_a)

display(a_to_states_given_a_statement)
display(b_to_states_given_a_statement)

defaultdict(set, {5: {(1, 4), (2, 3)}, 6: {(1, 2, 3), (1, 5), (2, 4)}})



defaultdict(set,
            {6: {(1, 2, 3), (2, 3)}, 8: {(2, 4)}, 5: {(1, 5)}, 4: {(1, 4)}})

# Find worlds where the first half of B's statement is true:
# B knows A's number, after hearing A's first statement.

b_would_know_a = lambda v: len({sum(e) for e in v}) == 1
states_where_b_knows_a_after_a_statement: set[HiddenState] = union(v for v in b_to_states_given_a_statement.values() if b_would_know_a(v))
display(states_where_b_knows_a_after_a_statement)

{(1, 4), (1, 5), (2, 4)}

Generalization

When brute forcing larger state spaces, (1, 4) remains the unique solution, even when the boss can select numbers up to and including 25.

Putting on a more mathematical hat, can we generalize this?

Let \(U\) be the set of all subsets \(S \subseteq \{1, 2, \ldots, l\}\) with \(|S| \geq 2\), where \(l\) is the largest number the boss can select.

Let the functions:

\[ \sigma(S) = \sum_{x \in S}\, x \]

\[ \pi(S) = \prod_{x \in S}\, x \]

be the functions mapping a hidden state to the sum and product given to A and B respectively.

A state \(S \in U\) is initially unambiguous for B iff \(\pi(S)\) determines \(\sigma(S)\) uniquely among all states in \(U\).

S is initially unambiguous for B iff \(S = \{1,q\} \in U\) and \(q\) is a prime or a prime square

\(1 \in S\): If \(1 \notin S\), then \(S\prime = \{1\} \cup S \in U\) has \(\pi(S) = \pi(S\prime)\) and \(\sigma(S) \neq \sigma(S\prime)\), so \(S\) would be ambiguous for B.

\(|S| = 2\): If \(1 \in S\) and \(|S| \geq 3\), then \(S\prime = S \smallsetminus \{1\} \in U\) has \(\pi(S) = \pi(S\prime)\) and \(\sigma(S) \neq \sigma(S\prime)\), so \(S\) would be ambiguous for B.

So the only possible states that are unambiguous for B take the form \(S = \{1, q\}\).

If q is not a prime or a prime square, then q can be written as a product of at least two distinct integers \(q = nm \text{ s.t. } n, m \gt 1 \land m \neq n\). Then:

\(\pi(\{n,m\}) = \pi(\{1,n,m\}) = \pi(\{1,q\})\) \(\sigma(\{n,m\}) \neq \sigma(\{1,n,m\})\)

so \(S\) is not unambiguous for B.

Therefore, \(S = \{1, q\}\) with \(q\) being a prime or a prime square is necessary for \(S\) to be initially unambiguous for B.

If \(q\) is a prime or a prime square, then the only valid factorizations are:

\(q = q\)
\(q = 1 \times q\)

If \(q\) is a prime square \(q = p^2\), then the following are also valid:

\(q = p \times p\)
\(q = 1 \times p \times p\)

A valid state in U must have distinct elements, eliminating \(q = p \times p\) and \(q = 1 \times p \times p\). A valid state in U must have at least two elements, eliminating \(q = q\). The only valid state is \(\{1, q\}\) so \(S\) is initially unambiguous for B.

Therefore, \(S = \{1, q\} \in U\) with \(q\) being a prime or a prime square is sufficient for \(S\) to be initially unambiguous for B.

Therefore, \(S = \{1, q\} \in U\) with \(q\) being a prime or a prime square characterizes \(S\) being initially unambiguous for B. In the revised script, this is states_where_b_would_know_a.

Necessary conditions for states where B knows A after A’s statement

A’s sum \(s\) must be consistent with some state in states_where_b_would_know_a and some state outside it. Equivalently, among all \(S \in U\) with \(\sigma(S) = s\), at least one must be of the form \(\{1, q\}\) (such that \(q\) is a prime or prime-square), and at least one must not be.

The first condition means \(s - 1\) must be prime or a prime square, with \(s - 1 \geq 2\). This gives the unambiguous witness \(\{1, s-1\}\).

The second condition means there must exist another \(S \in U\) with \(\sigma(S) = s\) that is not of the \(\{1,q\}\) form.

The only solution

For any viable sum \(s = \sigma(S) > 5\), the initially unambiguous witness is \(\{1, s - 1\}\), where \(s - 1 = q\) is a prime or prime square. \(s\) is therefore even.

Now, conditional on the strong Goldbach conjecture, there exist odd primes \(n, m \geq 3\) such that \(s = n + m\).

Case: Distinct primes

If \(n \neq m\), then \(S\prime = \{1, q\}\) and \(S\prime\prime = \{n, m\}\) are distinct states in \(U\) with \(\sigma(S\prime) = \sigma(S\prime\prime) = s\) and \(\pi(S\prime) \neq \pi(S\prime\prime)\).

As \(\sigma(S\prime\prime) = s\), this state survives A’s first statement.

As the product of two primes, B’s only valid decompositions which are compatible with A’s statement are \(\{n, m\}\) and \(\{1, n, m\}\). Only one of these can be successor to a prime or prime square, as for all primes > 2, both they and their square are odd. So, knowing A’s first statement, B unambiguously knows the full hidden state, and therefore A’s number. So this survives B’s first clause.

With two states surviving B’s first clause, A would not know B’s number after B’s second statement. Therefore, no such world can survive B’s second clause.

Case: Same prime

This leaves the case where the only valid Goldbach decomposition is two of the same prime.

For \(s \le 6\), we already covered the cases in our analysis of \(l = 6\).

Are there any cases for \(s > 6\) where the only valid Goldbach decomposition is two of the same prime?

In comments on OEIS A071681:

The conjecture follows from a slightly strengthened version of Goldbach’s conjecture: that every even number > 6 is the sum of two distinct primes.

In comments on OEIS A295424:

Tomas Oliveira e Silva in 2012 experimentally confirmed that all even numbers 4 <= n <= 4 * 10^18 have at least one Goldbach partition (GP) with a prime 9781 or less.

That is a pretty relevant property! If all numbers up to \(4 \cdot 10^{18}\) have a Goldbach partition with a prime no higher than 9781, we know all numbers over \(2 \times 9781\) (up to \(4 \cdot 10^{18}\)) have a Goldbach partition with two distinct primes.

This looks like the paper referenced. Table 4 lists record breaking values of \(p(n)\) for \(n \le 4 \cdot 10^{18}\), where \(p(n)\) is the smallest prime in a Goldbach partition of \(n\):

n p(n)

6 3

12 5

30 7

98 19

220 23

308 31

556 47

992 73

2642 103

5372 139

7426 173

43532 211

54244 233

63274 293

113672 313

128168 331

194428 359

194470 383

413572 389

503222 523

1077422 601

3526958 727

3807404 751

10759922 829

24106882 929

27789878 997

37998938 1039

60119912 1093

113632822 1163

187852862 1321

335070838 1427

419911924 1583

721013438 1789

1847133842 1861

7473202036 1877

11001080372 1879

12703943222 2029

21248558888 2089

35884080836 2803

105963812462 3061

244885595672 3163

599533546358 3457

3132059294006 3463

3620821173302 3529

4438327672994 3613

5320503815888 3769

8342945544436 3917

10591605900482 4003

12982270197518 4027

15197900994218 4057

28998050650046 4327

46878442766282 4519

76903574497118 4909

184162477860248 5077

217361316706568 5209

389965026819938 5569

1047610575836828 6469

6253262345930828 6961

24925556008175266 7559

31284177910528922 7753

121005022304007026 8443

255329126688555994 8501

258549426916149682 8933

555274351556750822 8941

887123803077837868 9161

906030579562279642 9341

2795935116574469638 9629

3325581707333960528 9781

n	p(n)
6	3
12	5
30	7
98	19
220	23
308	31
556	47
992	73
2642	103
5372	139
7426	173
43532	211
54244	233
63274	293
113672	313
128168	331
194428	359
194470	383
413572	389
503222	523
1077422	601
3526958	727
3807404	751
10759922	829
24106882	929
27789878	997
37998938	1039
60119912	1093
113632822	1163
187852862	1321
335070838	1427
419911924	1583
721013438	1789
1847133842	1861
7473202036	1877
11001080372	1879
12703943222	2029
21248558888	2089
35884080836	2803
105963812462	3061
244885595672	3163
599533546358	3457
3132059294006	3463
3620821173302	3529
4438327672994	3613
5320503815888	3769
8342945544436	3917
10591605900482	4003
12982270197518	4027
15197900994218	4057
28998050650046	4327
46878442766282	4519
76903574497118	4909
184162477860248	5077
217361316706568	5209
389965026819938	5569
1047610575836828	6469
6253262345930828	6961
24925556008175266	7559
31284177910528922	7753
121005022304007026	8443
255329126688555994	8501
258549426916149682	8933
555274351556750822	8941
887123803077837868	9161
906030579562279642	9341
2795935116574469638	9629
3325581707333960528	9781

From just the final row, every number up to \(4 \cdot 10^{18}\) has a Goldbach partition with a number no higher than 9781. So there are no even numbers which could only decompose into two of the same prime in the range \((2 \times 9781, 4 \cdot 10^{18}]\).

This pattern repeats going up the table: every time a higher lower bound for the smallest prime in a decomposition was found, \(n\) is more than twice \(p(n)\). The only exception is the very first row, with \(n=6\) and \(p(n)=3\), which was already analyzed.

So, there are no cases in the range \((6, 4 \cdot 10^{18}]\) where the only valid Goldbach decomposition is two of the same prime. Since the hidden state must admit a witness of the form \(\{1, q\}\) from A’s perspective for there to be initial ambiguity, we can say that for all \(l\) where \(6 \le l < 4 \cdot 10^{18}\), the only valid solution to the puzzle is the original solution.

Unique solution

Therefore, the only valid solution to the puzzle, for all values of \(l\) where \(6 \le l < 4 \cdot 10^{18}\), is the original solution:

The hidden state (1, 4), with the sum 5, and product 4.

If the slightly strengthened Goldbach’s conjecture holds, then this is also the only valid solution for all \(l \ge 6\).

This post ended up taking a very different direction than I initially expected. Yet, interesting negative results are still interesting results!

It is my hope that someone will read this, and find it as fascinating as I did.

Acknowledgements

Many thanks to Domnomnom for introducing me to this puzzle, reviewing early drafts, and being a good sport about being led astray two years ago.