Interview brainteasers

If I interviewed you at an open-day and left you a brainteaser or problem to think about, then look below for a reminder of the problem and the solution.

The problem with hats

There are 100 people 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?

Solution

Saving half of them is easy! Person 1 says the colour of Person 2's hat (and may die); then Person 2 knows their own hat colour, so can save themselves. Repeat this process down the line to save Person 4, Person 6, ..., Person 100: in total, 50 people.

However, we can do significantly better by following the strategy below.

Let Person 1 count the number of white hats they can see. If Person 1 sees an odd number, then they say 'white'. Otherwise, they say 'black'. Person 2 looks at the remaining 98 hats and counts the number of white hats.

Using the information from Person 1, they can deduce with certainty the colour of their own hat, so are saved. But in fact, the same works for Person 3, Person 4, ..., all the way up to Person 100. So we have saved 99 of the people. A surprising result!

But spare a thought for Person 1.

Squaring the circle

It is well known that x² + y² = 1 is the equation of a circle with radius 1, centred at the origin.

Now, suppose we let n be some positive integer. What does the graph of x²ⁿ + y²ⁿ = 1 look like? Try thinking about how x⁴ + y⁴ = 1 compares to x² + y² = 1, before thinking about what will happen as n gets larger and larger.

Solution

The shape becomes squarer and squarer as n increases.

Why did we not just look at x^n + y^n = 1, do you think?

The pigeon-hole principle

As a reminder, 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.

This is, of course, totally obvious, but it is surprisingly useful. 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 1,000.

Can you prove it?

Proof

Label 1,000 pigeon-holes with the numbers 0, 1, ..., 999. Put each of the numbers n⁰, n¹, n², ..., n¹⁰⁰⁰ into the pigeon-hole corresponding to its remainder on division by 1,000.

There are 1,001 integers and 1,000 pigeon-holes, so by the pigeon-hole principle there are two numbers in the same pigeon-hole.

These two powers of n have the same remainder on division by 1,000. If we take one number from the other we will end up with something that has zero remainder on division by 1,000. In other words, there are two different powers of n whose difference is divisible by 1,000.

This is taken from a third-year course, Combinatorics, which is full of interesting bits of easy to understand, but hard to apply counting mathematics.