#2 - TED-Ed rogue submarine riddle

Here's an interesting problem of "knowledge about knowledge" shown by TED-Ed in the YouTube video bellow.

The problem summary is:

1. The evil boss chose a subset of integers with at least 2 elements from {1, 2, 3, 4, 5, 6}.

2. He told minion A the sum of the elements, and to minion B their product.

3. Knowing all of the above, the minions said to each other:

A: I don't know whether you know my number.

B: I know your number, and now I know you know my number too.

4. The minions are expert logicians.

5. What are the numbers given to A and B?

Although TED-Ed gave the correct answer to the problem, the reasoning wasn't correct.

So what I'm going to do is to present a general method for solving these kinds of problems systematically, then show the solution of the submarine riddle, and then point out some of the mistakes made by TED-Ed.

The method

For problems with master logicians, which say true statements in sequence, heard by all the others, the following method can be used.

1 - Possible worlds

What are the possible scenarios or states of the world, before anybody said anything?

Enumerate each possibility. The set of all the possibilities is called "possible worlds".

We could write the following table:

2 - Initial information

For each possible world, what initial information each logician would have?

Increment the previous representation with it.

3 - Knowledge and knowledge about knowledge

Given their initial information, the logicians usually wouldn't be able to tell in which of the possible worlds they are in.  The worlds they would be considering to be in is called a "belief state". The belief state will be different for each world, and it's represented as a set of numbers from the possible world's enumeration.

With this representation, one possible world can reference another possible world, which in turn can reference other possible worlds and so on. This will take care of representing the recursive nature of knowledge, like in the famous phrase:

Now we could write something like this:

4 - Knowledge gain

In sequence, for each statement made by the logicians discard the worlds where the statement is false. This means discarding them from the full set of possible worlds and

then from the belief states within the remaining worlds.

The statements can be represented as predicates or boolean functions.

5 -  The answer

After integrating the knowledge from each statement, the remaining possible worlds (usually a single one, but not necessarily) will allow you to answer the problem.

Some remarks

The set of all the possible worlds is a representation of your belief state about the reality of the problem. And your belief state evolves after each statement. The actual knowledge of the logicians during each point in their discourse is a subset of your list of possible worlds. But once you are also a master logician, the overall reasoning that you apply over all the possible worlds (discarding the impossible ones) contains all the reasoning that each logician would actually do or have actually done.

After you've solved the problem and found a single real world, it becomes possible to go back and trace exactly what each logician were thinking.

Representing the rogue submarine riddle

Let's see how to use the method on the submarine riddle.

1 - Possible worlds

The numbers given to the minions A and B were calculated from a subset of {1, 2, 3, 4, 5, 6}, where the subset has at least 2 elements.

We can take each of these subsets as a possible world.

There are 57 possible worlds and I have enumerated them from 0 to 56. I've shown just some of them, by way of illustration.

2 - Initial information

For each possible world, A would know the sum of the numbers in the subset and B their product.

3 - Knowledge and knowledge about knowledge

Once there are multiple ways for the same sum or product to be generated, A and B would be considering they could be in many possible worlds.

Let's take as an example the world {2, 3}:

A = sum = 2 + 3 = 5

B = product = 2 × 3 = 6

{2, 3} is not the only world where A is 5.

The sum is also 5 at the world {1, 4}.

So being in the world {2, 3}, A would also consider he could be in {2, 3} or {1, 4}.

In other words:

A's belief state = {{1, 4}, {2, 3}}

Or using the respective worlds indexes:

A's belief state = {2, 5}

The same kind of reasoning goes for B.

{2, 3} is not the only world where B is 6.

The product is also 6 at the worlds {1, 6} and {1, 2, 3}.

In other words:

         B's belief state = {{1, 6}, {2, 3}, {1, 2, 3}}

Or using the respective worlds indexes:

B's belief state = {4, 5, 15}

Adding the belief states to our possible worlds table, we have:

4 - Knowledge gain

Now we need to consider the information given by each statement and how it affects the possible worlds.

Let's consider the questions:

a) When B knows A's number?

Answer: B knows A's number when all of the worlds in B's belief state have the same value for A.

If B knows exactly in which world she is, then automatically she knows A's number. But if she's considering more than one possible world, she'll have to evaluate if the value for A is the same in all of them.

This can be expressed in logical terms as the predicate:

    b_knows_a(world): ∀x,y ∈ b_belief_state(world) A(x) = A(y)

Conversely:

a_knows_b(world): ∀x,y ∈ a_belief_state(world) B(x) = B(y)

b) When A don't know whether B knows his number?

Answer: A don't know whether B knows his number when within A's belief state there is at least one world where B knows his number and at least another world where B doesn't know his number.

This can be expressed as:

a_dont_know_whether_b_knows_a(world):

∃x ∈ a_belief_state(world) b_knows_a(x) ∧

∃y ∈ a_belief_state(world) ¬b_knows_a(y)

c) When B knows A knows her number?

Answer: B knows A knows her number when in all of the worlds in her belief state A knows her number.

This can be expressed as:

b_knows_a_knows_b(world): ∀x ∈ b_belief_state(world) a_knows_b(x)

Now that we have the necessary predicates we can use them to discard the impossible worlds after each statement made the minions.

Solving the rogue submarine riddle

The statements made by the minions are:

A: I don't know whether you know my number.

B: I know your number, and now I know you know my number too.

B's statement is actually two statements. Breaking it up, we'll have equivalently:

A: I don't know whether you know my number.

B: I know your number.

B: And now I know you know my number too.

The sketch of the solution is as follows:

→ Consider all possible worlds.

A: I don't know whether you know my number.

→ Keep the worlds where a_dont_know_wheter_b_knows_a(world) is true

     → Remove the discarded worlds from A and B belief states

B: I know your number.

→ Keep the worlds where  b_knows_a(world) is true

     → Remove the discarded worlds from A and B belief states

B: And now I know you know my number too.

→ Keep the worlds where  b_knows_a_knows_b(world) is true

     → Remove the discarded worlds from A and B belief states

→ You found the real world.

The solution at work

→ All possible worlds:

*Notice that the table is scrollable and has 57 rows.

A: I don't know whether you know my number.

→ Keep the worlds where a_dont_know_wheter_b_knows_a(world) is true

     → Remove the discarded worlds from A and B belief states

Remaining possible worlds:

B: I know your number.

→ Keep the worlds where  b_knows_a(world) is true

     → Remove the discarded worlds from A and B belief states

Remaining possible worlds:

B: And now I know you know my number too.

→ Keep the worlds where  b_knows_a_knows_b(world) is true

     → Remove the discarded worlds from A and B belief states

Remaining possible world:

We end up with a single possible world - the real world. So the number's given to the minions were:

TED-Ed mistakes

I guess you are pretty much excused if you didn't understand TED-Ed's solution.

Nor mine 😅

But at least mine is correct 😆

The method I used, if you understand the basics of it, can be used to solve any problems like these. You cannot escape but to think about possible worlds and what the agents belief states are going to be in each of them.

You might try to find some shortcuts, try to simplify or compactify the complete set of possible worlds using some clever tricks, but at the end of the day it's always good to have a grounded solution to get your reasoning straight.

Anyway, TED-Ed got the answer right, but the reasoning was faulty.

Let's see some examples...

TED-Ed statement:

False.

Why? B could end up knowing A's number in the cases of B being 4, 5 or 8.

And 8 has TWO VALID ways of being factored:

8 = 1x8 = 2x4

The source of the mistake is that the order at which information is integrated matters. If B knew A's number from the beginning, before A's initial statement, then the possible worlds would be:

All of which, indeed, have B's number with exactly one valid way of being factored.

But given that B said she knew A's number AFTER A's initial statement, the possible worlds where B could know A's number became:

The last world has two valid ways to factor B's number.

TED-Ed statement:

False.

 The choice of 8 was an unlucky example. It ended up being one of the valid options for B, as shown above.

 TED-Ed statement:

False.

Given A's initial statement, the possible worlds became:

That is, A's list of B's number is dependent on the specific world. It could contain 4, 5, 6 or 8:

If A's number were 5, A's list of B's number would contain 4 or 6.

If A's number were 6, A's list of B's number would contain 5, 6 or 8.

None of which is TED-Ed's list of 2, 3, 4 or 5.

TED-Ed statement:

Very true.