In the early 19th century, the very existence of Timbuktu was in doubt among Europeans. Stories of its great wealth drove many to try to reach the fabled city. Unfortunately, penetrating into what is now northern Mali was off-limits for outsiders. Expeditions that set off with substantial funding, weapons and misplaced confidence were attacked and the leader usually killed or enslaved. It was not a gentle time.

Rene Caillé a penniless orphan from France, didn't have the resources to mount an expedition. So he tried a different strategy. He learned Arabic and Islamic culture and joined various caravans in the guise of a convert. This overcame the religious barrier, but a lone traveler was always vulnerable to enslavement or theft. It was all a question of whom to trust.

For our puzzle, imagine that there is a topology of acquaintances (that is, a map of who knows whom). Your interlocuters know that topology but know the trustworthiness and addresses only of the people to whom they can point you (via the arrows).

For example, consider this figure:

http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig1.doc

The leftmost circle, marked A, is the first person you visit, say in Sambatikila (the Ivory Coast). Each vertical collection of shapes represents a level of referrals, labeled A through D. The person in A knows the trustworthiness of the two people at level B and their addresses so she sends you to one of them. The person at level B sends you to someone at level C (always following the arrows), who sends you to someone at level D. The person at level D may either help you or enslave you.

Before you set out you know that one person among all those at levels A, B, and C (the circles) may be bad.

*Warm-Up:*

In addition to the possibly one bad person among the circles, how many of the people among the squares must be good for you to be sure there is no real risk?

*Solution to Warm-Up:*

If three out of four of the squares at level D were good, then there is at least one good square in either the lower half or the upper half. If A is bad, then the people you meet at levels B and C will steer you to some good square at level D. If A is good, then he will steer you to an honest B, who will steer you to an honest C who will steer you to some good square at level D.

You find out that the topology has changed to what you see in this figure:

http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig2.doc

Even if there is only one liar among levels A, B, and C, at least five squares would have to be good for you to be safe when you arrive at level D. The reason is that if four or fewer squares were good, then they might all be, say, in the lower half. If the circle at level A is bad, then he might direct you to the upper half and then you would have no hope.

**Problems:
1**. Suppose there is one bad person among all the the circles of levels A, B, C (but you don't know who) and there are three bad people at level D (again you don't know who) for this figure:

http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig2.doc

Are you guaranteed to end up with a good person?

**2.** Assume the topology of this figure:

http://cs.nyu.edu/cs/faculty/shasha/papers/Caillefig3.doc

What is the maximum number of bad people who could be at level D for you to be sure to be safe?

**3.** Continuing with the topology of the figure from the previous problem: suppose that we allowed you to return to someone you visited previously if your current interlocutor tells you that there is danger ahead. Of course he may be lying. We assume however that each informant knows about the goodness status of the two people he points to and the person who points to him. If there are three liars at level D, but only one among levels A, B and C, can you be sure to find a good home at level D?

*Solutions will be posted on or around October 19th.*