# Brainteasers

Here are some fun brainteasers. The solutions can be found on Sam Marsh's homepage.

## The problem with hats

There are 100 prisoners stood in a line, each with either a black or a white hat on. Each person can see everybody else's hat, but not their own. One by one, moving down the line, they have to say one word - either black or white. If the colour they say matches that of their hat, they survive, otherwise they die.

Now, the people were allowed to devise a strategy before being given the hats. The question is, what's the best strategy to pick? In other words, **how many people can you save?**

## The pigeon-hole principle

The pigeon-hole principle is the following statement.

*If there are more than n letters to be placed into n pigeon-holes then some pigeon-hole will contain more than one letter.*

Here's a statement which looks like some difficult number theory, but just comes down to the pigeon-hole principle.

*Let n be any positive integer. Show that there exist two different powers of n whose difference is divisible by 1000.*

**Can you prove it?**