Some maths puzzles that are actually clever

Someone passed me a ridiculous ‘maths problem’ they’d seen on Facebook the other day and it has really rubbed me up the wrong way (I would say it ‘grinds my gears but nothing grinds my gears because I am am engineer). A quick google search, and I’ve found it all over the usual places (daily mail, buzzfeed etc) under ‘this weird spooky maths trick’ and that sort of thing. Here it is:

 

stupid problem cropped

For anyone who is just looking at the pictures and skim reading, this is NOT one of the ‘actually clever problems’! I feel like posting it lowers the IQ of my blog by 50 points.

I won’t dignify it with a proof. But for anyone who hasn’t realised what a stupid ‘problem’ this is – here it is summarised:

 

stupid summary

 

I appreciate that the folk that come up with this drivel do so to get kids into maths. That’s fine. My issue is when this sort of thing gets plastered all over the internet as ‘clever’.

Anyway, rant over. Let’s look at some problems that I find genuinely clever. Most of them don’t need much maths knowledge. I’ll list them in increasing order of how cool I think they are.

All of these are famous problems – don’t go thinking I came up with anything this clever myself! The solutions given are all summaries and further info is available at the links provided in the solutions.

The Two Child Problem

This is a simple one, originally posed by Martin Gardner – the master of tricky maths puzzles. It goes like this:

Alice has 2 children. The older is a boy. What is the probability that both are boys?

Bob has 2 children. At least one is a boy. What is the probability that both are boys?

Answer:

The first question is straightforward. It’s 1/2 as you’d expect.

The second question is the weird one. Note we didn’t specify which one of the children is a boy. So, if we write the possible combinations we get: BG, BB, GB. All of these are equally likely so the probability is 1/3.

Gauss’s addition

The story goes that a young Carl Gauss was asked by his teacher to do the following:

1+2+3+4+………..+98+99+100

He responded with the answer in seconds (and went on to become one of the greatest mathematicians of all time but let’s not get bogged down with that). How?

Answer:

Rather than adding sequentally, add the first number to the last number like this:

1+2+3+….+98+99+100 is the same as (1+100)+(2+99)+(3+98)+….(49+52)+(50+51)

The 50 at the end is the only number to not have a ‘partner’ because it is in the middle of the sequence. It is easy to see that all the bracketed sums are 101. And there are 50 of them.

So, the sequence = 50 X 101 = 5050

Testing a really tough lightbulb

This one doesn’t come as high up in my list solely because it’s been tainted by certain companies who use is as one of those stupid ‘think outside the box’ problems in interviews.

I manufacture ‘nearly unbreakable’ lightbulbs. I want to test them by dropping them from stories of my 100 story building and seeing what the highest floor I can drop a bulb from without it breaking . 2 questions:

a) If you have an unlimited number of bulbs, what is the minimum number of drops to guarantee you find the ‘threshold floor’?

b) If you have just 2 bulbs, what is the minimum number of drops to guarantee you find the threshold floor?

Answer:

a) We just do a ‘binary search’. Start at floor 50. If the bulb smashes, go down halfway (to floor 25). If it doesn’t, go up halfway (to floor 75). Repeat, each time halving the number of floors we go up or down by. It is easy to see the number of drops will be 7.

b) We need to step up in decreasing increments for the first drop and if it smashes, perform the second drop from the previous drop +1, increasing by 1 each time. Let the increment = ‘n’:

n+(n-1)+(n-2)+….+1=100

his solves for n=14 (to the nearest integer). The worst case number of drops is therefore either for the case where the bulb smashes on the top floor (ie we go through all the ‘big steps’) or it smashes on the first drop, and then on the 13th floor.

A far more comprehensive proof is given at http://www.programmerinterview.com/index.php/puzzles/2floors-

 

The German Tank Problem

This is the first on this list which ‘actually happened’. In 1941 the Allies had no real idea how many tanks the Germans were producing. However, the Germans were labelling their tanks with sequential serial numbers ie the first tank built had serial#1, the second had serial #2 etc.

They had, however captured a number of tanks and knew their serial numbers. Let’s say they had tanks 4,7,9,13,67. How can we estimate the total number of tanks?

Answer:

The highest numbered tank produced is obviously equal to or higher than the highest number captured. But how much higher is it most likely to be? Thinking on first principles, if we have captured a lot of tanks, the highest produced number is unlikely to be significantly higher than the highest captured – since we have captured loads with smaller numbers.

The formula, which is derived at the wikipedia page is:

estimated number of tanks = max serial number captured + (max serial number captured/number captured) -1

 

So, basically, the estimated number of tanks is the max serial number found plus the average ‘gap’ between serial numbers found.

https://en.wikipedia.org/wiki/German_tank_problem

When applied in real life during WWII, this estimate turned out to be far closer than the previous estimates based on intelligence.

 

The tile stacking problem

I have a collection of tiles, all with a length of 1. I want to build a bridge with them by stacking them like this:

tiles

Given an unlimited supply of tiles, how far can I build the overhang horizontally?

Answer:

For ‘n’ tiles, take moments above the edge of the table to balance the stack. From this, it is easy to show that block ‘n’ protrudes (1/2n) beyond the previous block. Summing for all the tiles in the stack, we get the total overhang:

Overhang = (1/2)*(1+1/2+1/3+1/4+…+1/n)

The series 1+1/2+1/3+…. is called the harmonic series and it has no upper bound

So, as long as you have a supply of tiles, you can keep extending the overhang (albeit by a smaller amount of each time).

In other words, there is no upper limit, you can build an overhang as large as you like provided you have enough tiles.

A great proof is given here:

http://pages.pacificcoast.net/~cazelais/222/block_problem.pdf

 

The prisoner’s chessboard

I only came across this one a few days ago and it’s fantastic. I’ll confess I didn’t manage to solve it (I got really close and gave up at the last minute!). 

You and a friend are imprisoned in seperate cells. The jailer gives you a chance to win your freedom:

  • In your cell is a chessboard. The jailer places a coin on each square of the board eith either heads or tails up. He completely chooses which coins are heads and which are tails. You cannot interfere with this at all.
  • The jailer then points at one square and declares that it is the ‘magic square’.
  • You are then allowed to change one and only one coin of your choice on the board from heads to tails or vice versa..
  • You then leave the cell and your friend enters. If he can deduce which square is the magic square, you are both freed.
  • Prior to all this, you were informed of the rules and allowed to confer with your cellmate to devise a plan. Obviously, you only get to see the board and the configuration of the coins after you have conferred with your friend. So, when you were conferring, neither of you had any idea what the configuration would be.

Is it possible to communicate the location of the magic square to your friend with just the flip of one coin? Bear in mind this is not a daft trick question – you have to play exactly by the rules above.

 

Answer:

At first this seems impossible. You effectivley need to communicate 6 bits of information using a coin, which can only carry one bit. However, there is already plenty information on the board itself.

By dividing the board into appropriate sections and declaring an odd number of heads in each section is a ‘zero bit’ and an even number is a ‘positive bit’, we can communicate any number from 1 to 64 in binary to our friend. Crucially, the sections must overlap such that flipping one coin somewhere on the board can alter the state of every section in every possible way.

This is a very brief explanation. For a full explanation, visit the datagenetics blog (which also happens to be one of my favourite blogs of all time):

http://datagenetics.com/blog/december12014/index.html

 

Boring a hole into a sphere

Here is an absolute belter from Martin Gardner:

‘A cylindrical hole, 6 inches long, has been drilled straight through the centre of a solid sphere. What is the volume remaining in the sphere?’

That is all you get. Solve it!

Answer:

Astonishingly, the size of the sphere is completely irrelevant. If we bored a 6 inch long cylinder through the sun, and then bored one through a bowling ball, we’d be left with exactly the same volume in each case. Think about it, in the case of the sun, the cylinder would have a huge radius – very nearly the sun’s radius, so we’d bore almost all of the volume out.

The answer is 36*pi cubic inches. Every time.

The full proof requires only basic geometry knowledge and is given at the DataGenetics blog:

http://datagenetics.com/blog/july22014/index.html

 

My favorite problem of all time: the bomber armour problem

I love this one so much. Not only is it a real life problem that actually saved lives, but it’s also so simple. Anyone can solve it, regardless of mathematical ability.  

During WWII, the Allies were taking heavy losses due to enemy fire. A new type of engine was developed which increased the payload of the bombers, therefore allowing them to carry armor plates. The armor could only cover a small area on the bombers due to it’s weight. The Navy asked a highly skilled statistician called Abraham Wald where best to place the armor to minimise their losses.

Wald surveyed every bomber which returned to base and plotted the location of the enemy’s bullet holes. After plotting all the bullet holes on every bomber which made it back onto a single template, he had a picture something like this:

armour problem

Where should the armor be placed?

Answer:

Almost everyone tries to put the armor where the most bullet holes are – on the wings and tail. However, this is exactly the wrong place to put it.

Remember how we plotted the bullet holes from the planes that made it back to the base? These are only the planes that made it back. So, clearly a plane can withstand hits to the tail and wings. None of the planes that made it back had hits to the cockpit area. That is because these planes were shot down and never made it back to base.

In other words, the distribution of bullet holes isn’t due to the enemy’s aim. It is due to the fact that bullet holes in the vulnerable areas mean the plane doesn’t make it back so we never see those bullet holes!

This problem has far reaching implications and is known as the survivorship bias.

 

Bonus problem – the blue eyed islanders

This isn’t really a maths problem – it’s a logic problem. And it’s a total and utter nightmare. I doubt many people get the solution. That’s not even the difficult bit, it’s convincing yourself that the solution is correct. This one hurts my head every time I think about it.

Still, it’s one of the best problems I’ve ever come across:

There is an island inhabited by a particularly unusual tribe of 1000 people. They go by the following rules:

  • All of them are perfect logicians and can deduce anything deducible instantly.
  • They are forbidden to speak to each other at all about their eye colour.
  • No one knows their own eye colour.
  • If anyone finds out their eye colour, they must kill themselves at noon the next day.
  • There are no mirrors or any funny tricks. The inhabitants can only find out their own eye colour through logical deduction
  • 100 of the tribespeople have blue eyes. The remaining 900 have brown eyes.

You visit the tribe one day and over dinner, with the entire tribe present, remark ‘it is unusual to see someone with such blue eyes’.

At first glance, we haven’t given the tribe any new information. What you said is exactly the same as saying ‘at least one of you has blue eyes’. Surely this isn’t giving them any new information since they can see other members with blue eyes……or is it?

Get ready for the answer:

 

 

At noon on the 100th day after your visit, all the islanders commit suicide.

Huh!!?

As previously stated this one is a nightmare.

You actually have provided new information. By stating that at least one of the islanders has blue eyes in front of all of them, you have ensured that everyone knows that everyone else knows there is at least one blue eyed islander. 

The only way to prove this is by induction:

Suppose there was only one blue eyed islander. He would see no one else with blue eyes and kill himself the next day.

Suppose there were two with blue eyes, call them A and B. A would know that there are either one or two islanders with blue eyes. He can see that B has blue eyes but doesn’t know about himself. When B does not kill himself the next day (following exactly the same logic as A), he knows that he himself must have blue eyes too. So on the second day, they both kill themselves.

We can continue this reasoning for any number of islanders.

Obviously, no one sees the above proof as satisfactory. But the more you think about it the more you convince yourself about it. See Terry Tao’s post for all kinds of discussion and links on this problem (warning, I spent a whole day reading about this when I should have been working when I originally came across it):

https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/

 

 

Advertisements

2 thoughts on “Some maths puzzles that are actually clever

  1. My solution to the chessboard puzzle was: confer with your friend and agree on a 6th degree CRC polynomial such as P= x**6 + x + 1. You are going to treat the warden’s coins as a 64-bit vector B with heads=1 and tails=0. Let the magic square be indexed by a 6-bit number M. Choose a coin X to flip that makes the CRC=M modulo P. Now your friend comes and computes the CRC of the coins he sees, that tells him what M is. You should be able to get every possible CRC by flipping one of B’s 64 bits. This is basically arithmetic in the field of 64 elements, GF(2**6).

    Like

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