The deranged postman problem

There are various ways to introduce this neat little bit of combinatorics, but my favourite starts with Postman Pat in the Specsavers ad. Pat is trying to deliver n items of mail to n different addresses, but having broken his glasses he simply posts one item at random through each letterbox. What is the probability p(n) that no letter gets delivered to the right address? Remarkably, it turns out that as n \to \infty, the probability p(n) \to 1/e.

In a week or so I’ll post the proof of this result, but in the meantime you might like to have a go at it yourself. It doesn’t require any really advanced mathematical knowledge, but it does require some good clear thinking. If you want to “cheat” and look for starting points online, useful concepts include those of a permutation and a derangement… Have fun!

(DP)

Advertisements
This entry was posted in Puzzles. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s