Constructing interesting "Don't Know - Don't Know - Now I know!" type puzzles

Question

The professor has a piece of hidden information $C$. Alice is given an envelope containing information $A$, Bob is given information $B$. It is possible to deduce $C$ from $A$ and $B$. The conversation goes like this:

Alice: I don't know $C$.

Bob: I don't know $C$.

Alice: I don't know $C$.

Bob: Oh, now I know $C$!

Bob then correctly announced $C$. "We already know this game." he said.

"I've only just gotten started." said the professor. "Give me a non-negative integer. Any non-negative integer."

Alice said, "Alright, how about my birthday? It's $n$."

The professor thought for a moment, then said, "Alright, I'm thinking of a new piece of information $C_n$.". He then handed new envelopes $A_n$ and $B_n$ to Alice and Bob.

Alice: I don't know $C_n$.

Bob: I don't know $C_n$ either...

... after exactly $n$ iterations ...

Alice (her year of birth is an odd number): Finally! I know $C_n$.

"So you could have done this for any non-negative integer $n$?" asked Bob.

"Any non-negative integer." said the professor. He handed them a new pair of envelopes. "These should keep you going for exactly $1001$ iterations."

"How many!?" Bob said, "But it's almost lunch time!"

"Wait!" exclaimed Alice, "We don't actually need to play. We know that after $1001$ iterations, I'll have enough information to deduce the professor's secret - since it'll be my turn then. But the only information I'll have gained at that point is that we played the game for $1001$ iterations without yet figuring it out - but the professor's already told us that! So I should be able to deduce the information just by knowing the number of iterations..."

She stared intensely at her card for a moment, and then triumphantly announced the solution.

The professor smiled and wrote down two new cards for the two players. "But finite numbers are so provincial. Let's play another round, shall we?"

Just as the pair were about the begin, the professor interrupted: "I should probably tell you, though... no matter how many iterations you play through, you will never figure this one out."

"So you're saying $n$ is infinity?" said Bob.

"Yes, sort of - it's actually the ordinal number $\omega$, which works similar to an 'ordered infinity'. You can do a lot of the same things with it that you can with the numbers we're all familiar with. The only major issue with throwing in $\omega$ is that addition and multiplication pay attention to the order now."

"I have it!" said Alice, "There's only one possible value of $C$ compatible with the information on my card and which would keep us playing forever."

She then announced the correct value.

"Impressive." said Bob. "Got one I can solve?"

The professor handed them fresh cards. "Again, this one can't be figured out after any finite number of iterations."

Alice frowned. "I still can't deduce it."

"Me neither." said Bob.

"Indeed." said the professor, "In fact, even with the information I've given you, you still will never deduce the solution."

"Well... what about now?" said Bob.

"Now you can." the professor said. "After 24 iterations, that is."

"I see." said Bob. "So the solution is..."

"Correct." said the professor. "In this case, we had $n=(\omega\times 2)+ 24$, as it were. And in the same way, I can come up with pieces of information $A, B$ and $C$ corresponding to any number of iterations of the form $\omega n+m$, where $n$ and $m$ are positive integers."

"Wow." said Alice and Bob.

"And even $\omega^2$!" the professor said proudly. "That is, no finite number of iterations of my telling you that you still can never deduce $C$ would be enough information for you to solve the puzzle, but the previous part of this sentence would. We could go farther, too! $\omega^3$, $\omega^4$, even $\omega^\omega$!"

---

How can we come up with a puzzle like that of the professor? Standard ways are for $C$ to be a pair of numbers, $A$ the sum and $B$ the product, but I don't know this allows us to obtain any number of iterations, not even any finite number.

Can anyone come up with $A, B$ and $C$ corresponding to some of the professor's infinite numbers of iterations? What about a standard scheme to produce $A, B$ and $C$ corresponding to any $n$?

Answer 1

The professor says:

I have written on Alice's paper an even ordinal and on Bob's paper an odd ordinal. Who has the lesser ordinal?

Then, after $\lambda$ iterations of the game, it is common knowledge that both players have an ordinal of at least $\lambda$. Obviously, if the player whose turn it is has $\lambda$, they immediately know that they have the lesser ordinal, but if they have some greater ordinal, they do not know.

Answer 2

Here is an example of a situation in which Alice and Bob will never learn the value of $C$, but if they are told this they can work out the value. $$ \begin{array}{c|cc} &0&1&2&3&4&5&6&7\\\hline 0& W&X&\\ 1& Y&Z&\omega\\ 2& &&1&0&1\\ 3&&&3&&2&3\\ 4&&&5&&&4&5\\ 5&&&7&&&&6&7\\ \end{array} $$ The top line represents the values of $A$, the leftmost column the value of $B$, and the corresponding entry in the table gives the values of $C$. So e.g. if Alice is give $3$ and Bob is given $2$, the value of $C$ $0$. Here $W$, $X$, $Y$, $Z$, and $\omega$ represent five distinct values of $C$ different from $0$, $1$, $\ldots$ (we could shift every other value of $C$ up by $5$ and stick these values at the bottom, if we wanted, but I chose the numbering the way I did for convenience).

The claim is that after the $n$-th statement "I don't know" (I've started counting at $0$), it becomes common knowledge that the value of $C$ is not $n$. In the case $A=2$, $B=1$, $C=\omega$, neither Alice nor Bob can ever determine $C$, but if they are told they will never determine $C$ (i.e. if they are told that $n=\infty$), Alice can conclude that $C=\omega$.

Answer 3

Here is an extension of Julian Rosen's method which works for all ordinals up to and including $\omega^2$. In what follows, I will write some numbers in "base-$\omega$", so that $23_\omega$ refers to $\omega\times 2+3$ and $100_\omega$ refers to $\omega^2$.

The professor says that he is mentally pointing to one of the numbers in the below infinite picture. He tells Alice which of the red groups the number is in, and tells Bob which of the blue groups it is in. He then asks them each to state, over and over, whether or not they know what number is being pointed to (he is not asking the location, just what the number is).

If the professor points to the number $n$, then there will be $n$ "I don't know" statements before someone says "I know the number." This works for infinite $n$ as well, where the professor helps out by saying "You two won't know the number in a finite amount of time" some number of times.

Edit: Corrected a mistake: $100_\omega$ wasn't contained in any blue group, so I had to add the "numbers" X and Y to the diagram. If the professor points to these numbers, then the process will never end.

Answer 4

Let us take the following special case of this sort of puzzle:

For every possible piece of information $C$, there is only one possible $(A,B)$ pair that would lead to the conclusion.

In particular, this means that Alice will figure out $C$ exactly when she figures out $B$ and similarly for Bob. This lets us forget about $C$ entirely and work with only the structure of the pairs $(A,B)$ which are admissible - i.e. that correspond to some possible $C$.

We model the situation as follows: Consider a graph $G_0$ where every possible piece of information $A$ that Alice knows or $B$ that Bob knows is a vertex. An edge connects $A$ and $B$ if and only if $(A,B)$ is admissible. This graph is common knowledge, implicit in however the professor frames the puzzle. The professor has selected some edge $(A,B)$ and told Alice one vertex and Bob the other, and the goal is to determine the edge the professor chose.

When Alice says "I don't know $C$", she is exactly telling Bob that $A$ is connected to more than one $B.$ Thus, we model this by constructing a graph $G_1$, which is $G_0$ with all the $A$'s connected to only one $B$ removed. Similarly, when Bob afterwards says "I don't know $C$", we can make a new graph $G_2$ by removing all the vertices $B$ of $G_1$ connected to only one $A$. We continue this process until one player's knowledge is a vertex of degree one, which reveals a unique admissible pair $(A,B)$ to them, corresponding to the value of $C$. At limit ordinals like $\omega$, we simply take the intersection of all the previous graphs.

We can set this up so that at step $2k$, there would be no gain from Bob saying "I don't know $C$" and at step $2k+1$, there would be no gain from Alice asaying "I don't know $C$" - that is, so that $G_{2k}$ never contains a node in $B$ of degree $1$ and similarly for Alice. This leads to a more uniform treatment:

Define a function $f(G)$ on graphs to be the graph $G$ minus its vertices of degree $1$. Now, $G_0$ will be some arbitrary bipartite graph with some identified edge $(A,B)$. $$G_{k+1}=f(G_k)$$ $$G_{\lambda}=\bigcap_{\lambda'<\lambda}G_{\lambda'}$$ where $\lambda$ is a limit ordinal. The game last $k$ rounds when $G_{k+1}$ is the first ordinal from which $(A,B)$ is not in $G_n$.

For instance, if we play this game on the graph of the non-negative integers with edges $(n,n+1)$, then we get a solution for the finite case: The professor chooses a non-negative integer $n$ and tells Alice $\lceil n/2\rceil$ and tells Bob $\lfloor n/2\rfloor$ (using floor and ceiling functions). After $n$ steps, the answer will be announced.

Now, to handle the infinite case, the trick is finding a graph $G_0$ that doesn't stabilize at a fixed point $f(G_{\lambda})=G_{\lambda}$ before our desired ordinal. We can do this in a rather brute-force manner for any ordinal:

Let us first define a sequence of graphs $H_{\lambda}$ and identified vertices $v_{\lambda}$ which we will call the root. Define $g(H,v)$ as $H$ with all degree one vertices except $v$ removed. If $v$ has degree $0$, remove it as well. We will consider iterating $g$ by taking that for limit ordinals $g^{\lambda}(H_i,v_i)$ is the intersection of the graphs $g^{\lambda'}(H_i,v_i)$ for $\lambda'<\lambda$. We want $g^{\lambda}(H_{\lambda},v_{\lambda})$ to be the graph consisting of one point. This condition says that the graph "vanishes" at the right rate. We imagine that $H_{\lambda}$ will be a subgraph of a larger graph, where the root is connected to elements outside the subgraph, which is why we wait until it has degree $0$ to remove it.

Secondly, we want $H_{\lambda}$ to be possible to partition into two independent sets $A$ and $B$ such that the degree one elements of $g^{2\lambda'}(H_{\lambda},v_{\lambda})$ are always in $A$ and the degree one elements of $g^{2\lambda'+1}(H_{\lambda},v_{\lambda})$ are always in $B$. This condition says that Alice and Bob can appropriately be assigned the information.

Now, we construct the sequence inductively: Let $H_0$ be the graph containing one identified vertex. Let $H_{\lambda+1}$ be $H_{\lambda}$ with an additional vertex connected to the root of $H_{\lambda}$. The added vertex will be the root of $H_{\lambda+1}$. If $\lambda$ is a limit ordinal, define $H_{\lambda}$ by first taking the union of all the graphs $H_{2\lambda'}$ for all $2\lambda' < \lambda$. Now, identify together all the roots of the included graph and make this the root of $H_{\lambda}$. One can check that this sequence satisfies the properties. Note that $H_n$ is just a path with $n$ edges for finite $n$ and $H_{\omega}$ is a point included in paths of all even length.

Then, to get a suitable $G_0$ and an edge that will take exactly $\lambda$ iterations to reach, take two copies of $H_{\lambda}$ and one additional vertex $v$. Connect $v$ to the roots of each copy of $H_{\lambda}$. One can see that the two edges connecting to $v$ will be removed after exactly $\lambda$ iterations, so if the professor chooses that edge, the players will need $\lambda$ iterations.

As this works for all ordinals, I suggest the professor break out their favorite large cardinal axiom and see how their victims participants react.

---

For reference, here's what the graph $G_0$ looks like for $\omega$; obviously, both sets of paths should continue on to every finite natural number, but that would be hard to picture, and the people here are probably pretty good at imagining how patterns continue:

If the professor chooses one of the leftmost edges, it will take $\omega$ iterations to determine it, since that suffices to eliminate all the edges except the leftmost two.

For fun, here's the start of the graph for $2\omega$:

Obviously, each of those little subtrees actually extends infinitely, like before, and there are infinitely many of them under each of the two branches.