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?