#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:
I know that you know that I know that you know that I know...
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.
Knowledge gain is nothing but the elimination of the impossible.
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
You are also a master logician.
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: