Main Puzzles Paradoxes Games

My Favorite Paradoxes

The pop quiz paradox:
One Friday afternoon a professor announces the following to his class: "One day next week there will be a surprise pop quiz. By surprise, I mean that you will not be able to deduce prior to any day that the quiz will be that day." One of the students then claims this cannot be so, since obviously the quiz cannot be on Friday. If it were, then after not getting the quiz on any other day, the students could deduce Thursday evening that the quiz is on Friday. With Friday eliminated, a similar argument eliminates Thursday, and so on, until all 5 days are eliminated and the student claims there can be no such quiz. Nevertheless, the following Monday, the professor gives a quiz, and everyone is quite surprised!

To analyze this, I will change the statement of the problem. Suppose there are n cards labelled 1,...,n all face down, each of them has a red or blue face. The cards will be turned up one by one, with card i being turned over at time i. Thus, at time i we know the color of all the cards 1,...,i. Let R_i denote the statement "card i is red," and for any logical statement T, let P_i(T) denote the statement "there is a proof of T at time i." The professor's statement now corresponds to the following axioms:

1. ∃ i, R_i, that is, there is at least one red card.
2. ∀ i, j: i ≠ j ⇒ ¬ (R_i ∧ R_j), meaning, there is at most one red card.
3. ∀ i, ¬ (R_i∧ P_i-1(R_i)), which means that prior to time i it is not the case that card i is red and that this can be proved.

We now set out to prove, as the student did, the following claim:

Claim: ∀ i, ¬ R_i (there are no red cards).
Proof: We proceed by induction on i, beginning with i = n. Suppose R_n. By axiom 2, we then have ∀ i < n, ¬ R_i, as if this were not the case, then we would have ∃ j < i, R_j and thus we have ∃ i,j, j < i ∧ R_i ∧ R_j, contradicting axiom 2. But then at time n-1 we know ∀ i < n, ¬ R_i. Thus at time n - 1 we have the following proof:

1. Suppose ¬ R_n
2. Then ∀ i, ¬ R_i
3. This contradicts axiom 1, so ¬ (¬ R_n)
4. Thus, R_n

Thus, we have R_n ∧ P_n-1(R_n) contradicting axiom 3. Thus, the original assumption R_n must be false. As this proof did not require knowledge of any of the cards, we have P₀(¬ R_n).

Now, for the inductive step, suppose we have ∀i > k, P₀(¬ R_i). Suppose R_k and observe that, similar to the base case, we must have ∀j < k ¬ R_j by axiom 2. Consider, then, the following proof at time k-1.

1. Suppose ¬ R_k
2. Then ∀ i (i < k, i = k, i > k), ¬ R_i
3. which is the same as ∀ i, ¬ R_i
4. This contradicts axiom 1, so ¬ (¬ R_k)
5. Thus, R_k

Thus, we have R_k ∧ P_k-1(R_k) contradicting axiom 3. Thus, the original assumption R_k must be false. Again, this proof did not, in itself, require knowledge of any of the cards, so we have P₀(¬ R_k).

This completes the induction and we conclude ∀ i, P₀(¬ R_i). But P₀(T) ⇒ T for any statement T, so we in fact have ∀ i, ¬ R_i, which contradicts axiom 1.

So what is going on? The problem is that these 3 axioms are inconsistent, that is, they lead to a theoretic system in which anything can be proven, and, thus, not all provable statements are true.

But wait! At the end of the story, the professor gives out a quiz and people are, in fact, surprised! Thus, it would seem that, as the situation panned out, the professor's statement was true, and if it can be true, it must be consistent! A closer look, however, would reveal that the professor's statement was not, in fact true. Let n = 5 to transform the card axioms into the given problem, and note that there is, in fact, the following proof (at time 0) that the quiz will be on Monday, that is to say, we can show P₀(R₁). (Note, there is a fast way to do this using the fact that (A ∧ ¬ A) ⇒ T is a true statement for any A, T, but I wanted to show the contradiction without sneaky tricks. So, here is the proof that R₁:

Claim: ∀ i, ∃ j ≤ i, R_j. That is, for any index i, there is a card with index at most i that is red.
Proof: For i = n, the statement is just ∃ j ≤ n, R_j, which is precisely axiom 1. Thus, the claim holds for i = n. Suppose we have proved ∀ i > k, ∃ j ≤ i, R_j for some k. We will now prove ∃ j ≤ k, R_j under this assumption. Suppose this is not the case, so we have ¬(∃ j ≤ k, R_j), which is the same as ∀ j ≤ k, ¬ R_j. Then, at time k we can observe all of these cards and, using the inductive hypothesis that ∃ j ≤ k+1, R_j we conclude that P_k(R_k+1) ∧ R_k+1, contradicting axiom 3. Thus, our assumption ¬(∃ j ≤ k, R_j) must be false and we have ∃ j ≤ k, R_j, completing the induction.

But now we consider the case of i = 1 and note that we have ∃ j ≤ 1, R_j. The only possible value of j is 1, so we have R₁. Thus, this is a proof of R₁ ∧ P₀(R₁), which not only contradicts axiom 3, but our earlier finding of ∀ i, ¬ R_i as well. More importantly, we see that the professor's statement was not true, in that there was a proof that the quiz would be Monday. In an inconsistent system, you can prove anything.

The Envelope Paradox:
You are shown two sealed envelopes and are told that each contains a positive amount of money, and one envelope contains twice as much as the other. You choose one of them, open it, and find $10,000 inside. The host now gives you the following choice: you may, if you wish, swap for the other envelope and take the money inside it instead. On the face of it, it seems like you had a 50% chance to pick the bigger envelope, so it doesn't matter if you swap or not. But let's compute the expected gain from swapping. If you swap and are correct (a 50%) chance, you gain $10,000. If you swap and are wrong (a 50% chance) then you lose only $5,000. The expected gain is thus (50% • $10,000) - (50% • $5,000) = $2,500. Thus, you expect to gain $2,500 by swapping! But wait, there's nothing special about the amount $10,000, so suppose you were to open your envelope and find $M, a similar analysis would show that you expect to gain $M/4, and you know this before even looking in your envelope. So you may as well swap immediately. Now that you've figured that out, the host tells you that you may swap as may times as you want until you actually open one envelope (at which point you may perform one final swap, but then you're done). Based on the above reasoning, you would continually switch back and forth forever, and expect to gain each time. That can't be right... what's going on?

The problem is actually found inside an assumption so subtle you may not have noticed it. It is certainly true that before you look at either envelope, you have a 50% chance of choosing the better one, but we assumed that even with the knowledge of how much money is in your envelope, that there is still a 50% chance that you chose the better one. What does this assumption actually mean. To answer that, we define a few variables:

• Let M be the event "You found m dollars." Note that I've switched to lower-case for variables and upper-case for events.
• Let L_m be the event "The envelopes contain m and 2m dollars."
• Let U_m be the event "The envelopes contain m/2 and m dollars."

The assumption above translates to P(L_m|M) = P(U_m|M), where P(A|B) is the probability that A happens, given that B happens. We use the formula P(A|B) = P(A ∧ B)/P(B) twice to obtain Bayes' Rule P(A|B) = P(B|A)P(A)/P(B). Applying this rule to both sides of the above equation P(L_m|M) = P(U_m|M) gives P(M|L_m)P(L_m)/P(M) = P(M|U_m)P(U_m)/P(M). We cancel out P(M) from the denominator (we assume you're working with an amount of money for which there is a positive probability of obtaining it) we are left with P(M|L_m)P(L_m) = P(M|U_m)P(U_m). But, note that for each of the events U_m, L_m the probability of getting M is just 50%, as prior to any information you have equal probability of picking each envelope. The two terms P(M|L_m), P(M|U_m) are thus equal, so we can cancel them out as well and obtain P(L_m) = P(U_m). But now if there is any value m such that P(U_m) > 0 then we inductively have that P(U_2^km) = P(U_m) for all k, and thus thue sum of the probabilities is at least infinity times P(U_m), which is still infinite. Thus, this is not a valid probability distribution. The assumption that seeing how much money you had at first does not affect your view of how much is in the other envelope, though it seemed simple, is actually an assumption of the impossible.

But we're not done yet! Let's suppose the possible values for the amount in the lesser envelope are the powers of 2: $1, $2, $4, $8, and so on. One of the simplest probability distributions on these numbers is a geometric series with initial value a = 1-r and ratio r. The sum of such a series is a/(1-r) = (1-r)/(1-r) = 1 so this is a valid distribution. We then have that P(L_2^k) = a • r^k. Can we pick r so that we still have a paradox? We want to find r such that for any value m that you find in your envelope, you will want to swap. Clearly you always swap on m = 1 as the better envelope always contains at least $2. Suppose you find 2^k with k > 0. Using the same events as before, we want to find P(L_2^k|M), P(U_2^k|M). For the first of these, we have (using Bayes' rule again) P(L_2^k|M) = P(M|L_2^k)P(_2^k)/P(M). Now, P(M) = 1/2 • P(L_2^k) + 1/2 • P(U_2^k), so we have that P(L_2^k|M) = (1/2 • (ar^k)) /( 1/2 • ar^k + 1/2 • ar^k-1), and this simplifies to r/(r+1). Thus, the probability that you will gain if you swap is r/(r+1) and the probability you will lose is 1/(r+1).

Next, we compute the expected value of swapping. If correct, this will gain $2^k, and if wrong, it will lose $2^k-1. The expected gain is thus r2^k/(1+r) - 2^k-1/((1+r)) = (2r-1)2^k-1/(1+r). This is positive as long as r > 1/2. Thus, we can let r = 2/3, for example, and choose the number 2^k with probability 1/3 • (2/3)^k as the amount for the lesser envelope, and then put double that (2^k+1) in the other envelope. Then, no matter what amount you found when opening the 1st envelope, you would still swap. What's wrong this time? We were careful to pick a valid distribution, so how come we got the same nonsensical result. Consider determining what the expected value of a single play of the game is. We won't even worry about whether to swap or not, we'll compute the expected amount of money in the lesser envelope. The expected winnings must be at least this big. This value is the sum over k=1,...,∞ of 2^k • 1/3 • (2/3)^k. The k term here is 1/3 •(4/3)^k, which is bigger than 1/3 for all k. Thus, the expected winnings are infinite, so no matter how much money you find in the first envelope, you win less than the expected value of the game by keeping it. It's just one more example that weird things happen at infinity.