## Monday, January 18, 2010

### The Fortune-Tellers

I asked a second fortune-teller my future. She answered: "The next fortune-teller you ask will tell you true."

The fourth would not read my future, but said: "The first fortune-teller you sought answered false."

Bob Michael said...

So by my calculation, if each one can either tell you the truth or lie to you, and if each one reflects accurately on the next one, then its a cycle that never ends and each one reinforces the other. Or did I mess up somewhere?

Danimal said...

Hmm, let's see. If one fortune teller says the next one will tell false, this can be consistent either if the first tells false and the second tells true, or if the first tells true and the second tells false.

If one fortune teller says the next one will tell true, this can be consistent if the first tells true and the second tells true, or if the first tells false and the second tells false.

Assume the first one tells the truth. Then the above reasoning implies the second must tell false, thus the third must tell false, thus the fourth must tell true, and then finally the first must have told false. Contradiction with assumption.

So, assume the first one tells false. Then the second must tell true, the third must tell true, the fourth must tell false, and finally the first must have told true. Contradiction with assumption again.

It's fun to think of true as "1" bit and false as "0" bit. A prediction of truth transfers the current bit (0 or 1) faithfully to the next teller, whereas a prediction of falsehood flips the bit before sending it to the next teller. In order to wind up with the same bit when arriving back at the first teller, you'd need to flip the bit an even number of times.

That is, regardless of how many tellers are in the chain, you'd need an even number of predictions that the next teller (or in the case of the last teller, a retrodiction that the first teller) tells false.

Very nice puzzle, Jason! That is, assuming I've thought it out right...

JasonZimba said...

Thanks for the comments you guys!

One day I realized that the classic Liar's Paradoxes "This sentence is false" and "The next sentence is true/The previous sentence is false" were the n=1 and n=2 terms in a series. "The Fortunetellers" is a variant of n=4.

I tried to craft the language in such a way that it draws the reader in, as opposed to sounding 'like a math problem.' And I formulated the paradox in the context of fortune-telling because I thought this was a situation with 'dramatic potential.' At the end of his quest, the speaker finds himself unable to believe or disbelieve the statements the fortune-tellers make. He reaches a despondent endpoint. There is some hint in this of the futility of trying to know fate...some idea maybe that asking certain questions opens doors to labyrinths that might be better left unentered. Philetus of Cos is said to have perished of insomnia as a result of his obsession with the Liar's Paradox.

Paradoxes of this kind suggest a graph coloring problem of mixed edge/vertex type: Given a graph with edges colored black and white, color the vertices black and white so that vertices connected by white edges have the same color and vertices connected by black edges have different colors.

With reference to the paradox, vertices represent sentences, and edges represent assertions that a given sentence makes about others. "This sentence is false" is a graph with one vertex and a loop. The loop would be colored black (say) because it is an assertion of falsehood.

Finding a coloring of the specified kind means finding an assignment of truth values for the sentences that respects the semantics of the network as a whole. When no coloring exists, the network is paradoxical.

I think it is not hard to see that a network is paradoxical if and only if it contains a cycle with an odd number of black edges. The classic one-sentence paradox is a loop with 1 black edge; the classic two-sentence paradox is a two-cycle with 1 black edge; The Fortune-Tellers is a four-cycle with three black edges.