The Road to Timbuktu

Join Our Community of Science Lovers!

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).

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

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.

It’s Time to Stand Up for Science

If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.

I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.

If you subscribe to Scientific American, you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.

In return, you get essential news, captivating podcasts, brilliant infographics, can't-miss newsletters, must-watch videos, challenging games, and the science world's best writing and reporting. You can even gift someone a subscription.

There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.

Thank you,

David M. Ewalt, Editor in Chief, Scientific American