Puzzle 12 : The hardest puzzle in the world

Since Limji shot down the last one, here goes.

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.

Boolos provides the following clarifications:

It could be that some god gets asked more than one question (and hence that some god is not asked any question at all). What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.) Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely. Random will answer 'da' or 'ja' when asked any yes-no question.

Puzzle 11 : Tribes and Prejudice

from Terry Tao's blog via RawT

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

[Added, Feb 15: for the purposes of this logic puzzle, "highly logical" means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe?

The question is not hust about how to solve it, but a hidden seeming paradox. Apparently very well hidden since Varun didn't see it!

Argument 1. The foreigner has no effect, because his comments do not tell the tribe anything that they do not already know (everyone in the tribe can already see that there are several blue-eyed people in their tribe). 

Argument 2. 100 days after the address, all the blue eyed people commit suicide. This is proven by induction as all first year IITians apparently know.

Puzzle 10 : Error correcting tournaments

Since the NBA playoffs are on the horizon we will be topically appropriate.

You have N NBA teams (say 8) and each is assigned a 'goodness' value between [0,1]. They play a tournament to find the best team. A tournament is a series of games between 2 teams.

Unfortunately, teams can have off days, and so there is a small probability p that in game the weaker team wins.

Design a tournament so that the probability that the best team does not win the tournament is less than some Q.

For the sake of your audience we want only O(N) games!

Adding even more (fake) reality, how many days must the tournament last if each team can play only one game on any given day ?

Puzzle 9 : More gold and more splitting

There are now 1000 Pirates. The treasure is to be divided by the following manner (more democratically :).

Every day, the Pirate vote to either
1) kill the captain, or
2) split the pot of gold up among the remaining pirates equally.

If 50% or more of the Pirates vote to split the pot of gold, the treasure gets split . Otherwise the captain is killed. Assume that all the Pirates know the order of assuming captaincy. The process is repeated until the gold is split.

The question is: When will the gold be split?

Puzzle 8 : Pieces of eight

(from Ravishan)

Five pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all extremely intelligent, treacherous and selfish (especially the captain).

The captain always proposes a distribution of the loot. All pirates vote on the proposal, and if half the crew or more go "Aye", the loot is divided as proposed, as no pirate would be willing to take on the captain without superior force on their side.

If the captain fails to obtain support of at least half his crew (which includes himself), he faces a mutiny, and all pirates will turn against him and make him walk the plank. The pirates start over again with the next senior pirate as captain.

What is the maximum number of coins the captain can keep without risking his life?

Puzzle 7 : Writing on dirty paper

(from RAW-T)

You have blank piece of paper, divided up into n=64 blocks. You have enough 'power' to perform k=1 operations on the paper. An operation would be either erasing or coloring in k of the n blocks.

You hope to communicate with whoever is going to read the paper the next day. You can meet up before hand and decide a strategy. Unfortunately, the adversary knows your strategy.

This adversary can fill in the blocks however he (or she) chooses. How many bits of information can you communicate ?

To illustrate, suppose there is no adversary. Then you have 64 possible messages, [1000..00],[010...0000].....[00...00001] and can thus communicate log(64) bits.

What if, in general, k=nR, for some fraction R<=1 ?

This is a special case of the problems of dirty paper coding, coding with channel information and information embedding which are very important in information theory!

Two variants of the necktie/envelopes problem

Fro wikipedia: (Try it without googling :)

--------------------

Variant 1

The setup: The player is given two indistinguishable envelopes, each of which contains a positive sum of money. One envelope contains twice as much as the other. The player may select one envelope and keep whatever amount it contains, but upon selection, is offered the possibility to take the other envelope instead.

The switching argument:

1. Denote by A the amount in the selected envelope.
2. The probability that A is the smaller amount is 1/2, and that it's the larger also 1/2
3. The other envelope may contain either 2A or A/2
4. If A is the smaller amount, the other envelope contains 2A
5. If A is the larger amount, the other envelope contains A/2
6. Thus, the other envelope contains 2A with probability 1/2 and A/2 with probability 1/2
7. So the expected value of the money in the other envelope is:
8. This is greater than A, so swapping is favored
9. After the switch, reason in exactly the same manner as above, but denote the second envelope's contents as B
10. It follows that the most rational thing to do is to swap back again
11. This line of reasoning dictates that envelopes be swapped indefinitely
12. As it seems more rational to open just any envelope than to swap indefinitely, the player is left with a paradox.

--------------------

Variant 2:

The solution above does not rule out the possibility that there is some non-uniform prior distribution of sums in the envelopes to give the paradox force.

Suppose that the envelopes contain the integer sums {2ⁿ, 2ⁿ⁺¹} with probability 2ⁿ/3ⁿ⁺¹ where n = 0, 1, 2,… and the value of n is not known in advance.^[1]

A sensible strategy that guarantees a win is to swap only when the opened envelope contains 1, as the other must contain 2. Furthermore, suppose the envelope contains 2. Now there are only two possibilities; the envelope pair in front of us is either {1, 2} or {2, 4}. The conditional probability that it's the {1, 2} pair is

and consequently the probability it's the {2, 4} pair is 2/5 since all other envelope pairs have zero conditional probability.

It turns out that these proportions hold in general unless the first envelope contains 1. Thus, denote by x the amount found where x = 2ⁿ for some n ≥ 1, then the other envelope containsx/2 with probability 3/5 and 2x with probability 2/5. So the expected gain by switching is

which is more than x. This means that the player should switch in all cases.

But once again, the player may go through this reasoning before opening either envelope, and deduce that the other envelope should always be chosen. This conclusion is just as clearly wrong as it was in the first and second cases. But now the flaws noted above don't apply; the x in the expected value calculation is a known constant (in every single case) and the probabilities in the formula are obtained from a specified and proper prior distribution.