I will offer the puzzle below, but the best way to experience it is to watch Paul’s talk, Mindware Upgrades For Fun And Profit.  No special technical or other background is necessary to enjoy it.

Albert is looking at Betty.  Betty is looking at Charlie.  Albert is a computer programmer.  Charlie is not.  Is there a computer programmer looking at a non-computer programmer?

What was most interesting to me is that the audience of about a thousand really smart people is then invited to raise their hands for “Yes” “No” or “Not Enough Information” and all but fewer than 10 people raised their hand for the same wrong answer!  I failed along with the vast majority, and the other wrong answer outweighed the right answer (which might have had zero votes… I don’t remember.)

If no one posts the right answer here after a while, I’ll come back with an explanation, but I do encourage you to go watch Paul explain.

Devise an alternate set of denominations for coins and bank notes requiring a minimum number of denominations and such that any amount from $0.01 to $100 could be paid with four units of currency.

I’ve looked at this from another perspective before after it was discussed on Freakonomics but that has to do with minimizing the average number of coins needed and doesn’t go too much into the math.

What’s remarkable is that my friend nearly instantly came to an upper bound that isn’t huge and after hours five of us have failed to improve upon it.  I’ll avoid stating that bound here for now, but will come back and add it to the comments in a bit if there is no traction.

 Another interesting tidbit is that unlike U.S. denominations where a greedy algorithm can verify a minimal number of units that are required (take as many of the largest as you can, then as many of the next largest, etc.) denominations where the denominations aren’t multiples of each other don’t allow this.  Making 15 in 12-5-1 shouldn’t be 12-1-1-1 — it should be 5-5-5.  Even doing verification requires dynamic programming solutions.

You find yourself babysitting a friend’s marble collection while he’s away at a conference of collectors.  The housekeeper, being an honest type, admits to having disturbed one of the displays.  She assures you that she returned all the marbles and shows you ten marbles laid out thus:

* * * * *

* * * * *

That looks fine, but the note to the side of it says five lines of four marbles each.  Since this is two lines of five marbles, must there be marbles missing or can they be laid out in a manner consistent with the note?

Only five horses can compete in one race.  

Assuming each horse always runs at the same pace, and that all 25 horses have different abilities, what is the fewest number of races you can use?

You can’t use stopwatches, you can only use the finishing order of each race.

UPDATE: Thanks for all the great comments.  At the time of writing we’ve had three correct answers; Mike and Blaise in the comments and Jim via email.

I have a follow up question: can you prove that this answer is minimal?  There is a neat spot, can you find it?

Apparantly this was an interview question for Facebook.  I found it in this list of impossible interview questions.  Math Factor afficionados will recognise some of these problems and not find them so impossible.  Have fun!
http://skymcelroy.tumblr.com/post/6244020081/impossible-interview-questions-from-facebook-goldman

If you are anything like me, and I hope for your sake that you aren’t, then you will often ask yourselves questions such as:

    Late at night, when they’re peckish, do Vampires ever bite themselves?

    Was Hitler’s moustache homage to Charlie Chaplin?

    Can I find an exact formula for the Fibonacci sequence?

I can only answer one question. Which one?  

Yup, it’s the last one.

In Yoak: Miles, Kilometers and Fibonacci Numbers Jeff showed a lot of fun stuff about the Fibonacci sequence and how it relates to the golden ratio. He didn’t explain how this comes about.

The Golden Ratio, phi (I’ll use g), was beloved by classical architects and is still loved today. It was thought to be the most aesthetically pleasing ratio. It was the ratio used for the Parthenon.

It has a simple definition, if you have a rectangle with proportions 1:g then you can remove a square from one end and the leftover is a rectangle with the same proportions.

From that you can work out that g² = g + 1 and g = 1 + 1/g. There is a revealing symmetry in that last equation which is better shown by g – 1/g = 1, if you switch the sign and invert g then you get another solution. 

Anyway:

    g = (sqrt(5) + 1)/2 ~= 1.618

    1/g= (sqrt(5) – 1)/2 ~= 0.618

The Fibonacci sequence goes 1, 1, 2, 3, 5, 8, 13, 21, 34 …

The Fibonacci rule is F_n+2 = F_n+1 + F_n

There are lots of sequences that fit this rule. Any particular sequence is fixed by specifying two elements, for example the actual Fibonacci sequence starts 1, 1. Another sequence that fits the rule is 1, 3, 4, 7, 11, 18, 29 …

We note that if xⁿ⁺² = xⁿ⁺¹ + xⁿ then the sequence 1, x, x², x³, x⁴ … satisfies the Fibonacci rule.

We can solve for x. Dividing by xⁿ and rearranging gives x² – x – 1 = 0.

This gives two solutions for x:

        g =                      (1+sqrt(5))/2

       (-1/g) = (1-g) = (1-sqrt(5))/2

Both of these solutions for x generate sequences that satisfy the Fibonacci rule.

    1, g, g², g³ …

    1, (1-g), (1-g)², (1-g)³ …

But we can go further. Put X_n = Agⁿ + B(1-g)ⁿ  then X_n satisfies the Fibonacci rule.

    A + B, Ag + B(1-g), Ag² + B(1-g)², Ag³ + B(1-g)³ …

A particular sequence that satisfies the Fibonacci rule is fixed by just two entries. I claim that we can always find values for A and B that will create any sequence which satisfies the Fibonacci rule.

We have two simultaneous equations with two unknowns, A and B. This always gives a unique solution (it matters that (1, g) and (1, 1-g) are linearly independent vectors). For example lets calculate A and B for the actual Fibonacci sequence. F₁ =1 and F₂ = 1. Using the Fibonacci rule backwards gives F₀ = 0.

So     F₀ = A + B = 0      F₁ = Ag + B(1-g) = 1

Working this through

    B = -A

    Ag – A(1-g) = 1

    A(2g -1) = 1

    A(2(sqrt(5) + 1)/2 -1) = 1

    A = 1/sqrt(5)

Which solves to give A = 1/sqrt(5), B = -1/sqrt(5)  

So we have : F_n = (gⁿ – (1-g)ⁿ) /sqrt(5)

Now there is something very bizarre going on here. We know that the Fibonacci sequence is a sequence of integers. We have found that it has an exact formula but the formula involves lots of irrational numbers, raising them to powers, adding and dividing them. Somehow this process always ends up with an integer. Knowing that we will always get an integer we can short-circuit the calculation.

Note that 1/ sqrt(5) is about 0.447, (1-g)/ sqrt(5) is about -0.276 and that (1-g)ⁿ/ sqrt(5) always has a magnitude of less than a half. Knowing that we will always get an integer we can just ignore this term and round to the nearest integer.

    F_n = round(gⁿ /sqrt(5)) for n >= 0

It is also true that

    F_-n = (-1)ⁿ⁺¹round(gⁿ /sqrt(5)) for n >= 0

To see this remember that 1-g = -1/g so F_n = (gⁿ – (-1/g)ⁿ) /sqrt(5). For negative n it is the first term that is smaller than a half and can be ignored. I’ll let you work out the rest.

In fact extending the Fibonacci sequence backwards gives … -3, 2, -1, 1, 0, 1, 1, 2, 3 …

What is most wonderful about this is that the ratio between successive members of the Fibonacci sequence is about g. It becomes very close very quickly. Also wonderful is that this technique extends to other sequences which are defined by similar rules. In general you can find an exact formula, involving taking powers of irrational numbers, which will always give you the integer you were looking for.

I find that quite amazing!

It shows that you cannot take one part of mathematics in isolation, if you want to understand integers you have to understand irrational numbers, and for many sequences complex numbers. It’s all interconnected, you can’t pick and choose. Even the simplest parts of mathematics are tied up in the most complex!

All good fun though!

In Golden Earring – Radar Love I had a big problem.

This the solution so please read the problem first and have a go at solving it yourself.

My wife has lost a golden earring, I can buy a bunch of similar earrings but I know one is a fake.

I can weigh two groups of earrings, each weighing can give one of three results: they weigh the same; the left group is heavier, the right group is heavier.

The question is – how many earrings can be in the bunch I buy and leave me confident that I can find the fake with just three weighings?

You may have noticed that ears normally come in pairs.  So do earrings.

My wife still has one earring.  We know this earring is good and we can use it in our weighings if that helps us.

Always try the simplest case first and see if that gives any insights.

Suppose we are not allowed any weighings, then we can cope with a bunch of one earring; as it is the only earring it must be the fake.  We don’t learn if it is heavier or lighter than a genuine earring.

If we are allowed one weighing then we can cope with a bunch of two earrings. First we compare earring 1 with my wife’s other earring which we know is good.  

• If they differ then earring 1 is fake and we learn if it is heavier or lighter.  
• Otherwise they weigh the same and earring 2 is the fake, but we don’t learn if it is heavier or lighter.

A good approach to these sorts of problems is to think about the amount of information you can gain.  One possibility is that each weighing is equal; then we know that we haven’t weighed the fake earring, the fake is the one earring we haven’t weighed.  There are 26 other possible results; they must involve weighing the fake and so finding out if it is heavier or lighter than a good earring.

So the 27 possible results from three weighings will differentiate between:

  an earring which is never weighed is the fake;

  earring 1 is the fake and is light;

  earring 1 is the fake and is heavy;

  earring 2 is the fake and is light;

  earring 2 is the fake and is heavy;

…

  earring 13 is the fake and is light;

  earring 13 is the fake and is heavy.

So the maximum number of earrings is 14.

We have shown that 14 is the maximum, but we haven’t shown that it is possible.  Can you find a method?

Can you find a general formula for n weighings?

Always think about how much information you can gain from the remaining weighings; if you leave yourself with four earring candidates and one weighing then you have gone wrong.  That’s the best clue I can give you.

I’ll answer these in the comments in the near future if no-one else gets there first.

Smart shows have smart writers, and none are smarter than the writers of Futurama.  We’ve seen a number of clever math references in Futurama and the Simpsons.  Now a fully fledged theorem is written up on screen.

If I had a TV show that’s exactly what I would do.  As it is I just post on Math Factor.

The theorem is by staffer and Math PhD Ken Keeler.  In the show Harlem Globetrotter, and all-round genius, Sweet Clyde comes up with a theorem to solve an apparantly intractible problem.

To quote Professor Farsnworth ‘Who says pure maths isn’t useful in the real world!’

Professor Farnsworth invents a mind-switching machine.  A lot of plot later nine people have their minds in the wrong bodies.  Unfortunatley the machine has a limitation, it cannot process the same two bodies twice.

There seems to be no way out until Clyde and EthanTate enter.  Clyde comes up with ‘Sweet Clyde’s Inversion Theorem’ and saves the day.

He shows that however many people there are, and however mixed up their minds, it is always possible to get every mind back in the right body as long as you have two extra bodies to help, and you know your maths!

This is the mess they are in:

Fry’s mind is in Zoidberg’s body

Professor’s mind is in Bender’s body

Bucket’s mind is in Amy’s body

Leela’s mind is in Professor’s body

Emporer’s mind is in Bucket’s body

Hermies’ mind is in Leela’s body

Zoidberg’s body is in Fry’s body

Bender’s mind is in Emperor’s body

Amy’s mind is in Hermies’ body

Take a moment to solve this yourselves.  Remember you need to get each mind back in the right body by repeatedly switching the minds of two bodies.  No switch can be repeated.  You cannot switch two of the original nine bodies because we have lost track and assume those combinations have already been used.  So every switch must involve Clyde and/or Ethan.  

Read on for the solution.

Mathematically this is a permutation on nine elements.  Any such permutation consists of a number of disjoint cycles.  To see what I mean lets find the cycles here.

Starting with Fry’s body we find the matching mind is in Zoidberg.  So now we look for Zoidberg’s mind and find it in Fry.

So now we start with another character and follow the cycle which gives the following:

Fry and Zoidberg form a 2-cycle.  The other characters form a 7-cycle.

Enter Clyde and his basketball team-mate Ethan.

Clyde come’s up with’Sweet Clyde’s Inversion Theorem’ and saves the day.

We’ll get to that later but first lets see how  we unscramble this mess using Clyde and Ethans’ bodies as parking places for the mind.

Easiest to sort out are Fry and Zoidberg as they are only a 2-cycle.

We perform the following switches:

This switches Fry and Zoidberg but also switches Clyde and Ethan.  We could just switch Clyde and Ethan but first let’s sort out the other guys.

Hopefully it is clear that we did need two extra bodies to make this work.  We couldn’t have done it with just Clyde’s body.

We have sorted out a 2-cycle, now to sort out the 7-cycle.  This will be a bit tougher.

Let’s track what happens to the characters:

Bucket -> Ethan -> Emperor

Professor -> Clyde -> Leela

Leela -> Clyde -> Hermies

and so on.

All of the seven original characters end up in the right bodies. It reverses the 7-cycle that messed them up in the first place.

Clyde and Ethans’ minds are switched but this just reverses the switch that happened when we sorted out Fry and Zoidberg.  If it hadn’t we could still switch Clyde and Ethan.

Hopefully you can see we have used the same approach to sort out the 2-cycle and the 7-cycle.  In both cases we switch the two extra bodies (Clyde and Ethan) while sorting out the original characters.  This would work for any permutation, if we had more cycles we would just apply the same technique for each cycle.  If there were an odd number of cycles we would need to switch Clyde and Ethan at the end.

Now it’s time to explain ‘Sweet Clyde’s Inversion Theorem’

We need to introduce some notation.

For cycle’s we use round brackets so (a b c) means ‘move a to b, b to c and c to a’.

(a b c) = (b c a) = (c a b)

The inverse cycle would be (c b a) = (b a c) = (a c b)

These are the only two possible cycles on three elements which move all three elements.  There are others which move fewer elements.  The complete list is (), (a b), (a c), (b c), (a b c), (a c b).  Together they form a group and we can do algebra on them if we want to.

Cycles can be combined.  Applying cycles from left to right we find (a b)(b c) = (a c b).  The order we apply the cycles matters.  (b c)(a b) = (a b c).

Clyde introduces the notation <a,b> to mean a ‘switch’ of a and b.  This is equivalent to the cycle (a b) but Clyde is keen to differentiate between the two concepts because he needs to prove that the solution can consist of distinct switches.  He combines switches in the same way as cycles.  He wraps switches in round brackets to represent the equivalent cycle.

So (<a,b>) = (a b), but the point is made that we are constructing the cycle from a switch.

Clyde also uses a ‘double-decker’ notation for cycles for clarity.  In his proof PI = (1 2 3 … k), a k-cycle.

Now whatever mix up has happened it consists of a set of k-cycles.  Clyde needs to perform another set of  k-cycles to reverse the process. Remember he cannot switch any two of the original bodies because they have already had lots of switches.  So he can only use switches that use at least one of Clyde and Ethan.

Using X to represent Clyde and Y to represent Ethan we have:

 (<x,1><x,2>…<x,i>)(<y,i+1><y,i+2>…<y,k>)(<x,i+1>)(<y,1>)

= (1 2 3 … k)(x y)

So we can reverse any cycle in this way.  At the end we can do a <x,y> switch if necessary.

I know that one of his earrings is fake, but that’s okay because I can work out which one, replace my wife’s earring and still make a profit. 

I will have to bring out my earring weighing machine, the Radar Love, which lets me compare two groups of earrings and tells me whether one group is heavier or lighter than the other, or whether they are the same wieght.  This is the only clue I will get.

The Radar Love only has three charges.  At most how many earrings can I have bought and still be confident that I will find the fake?

Can you find a general formula for a given number of charges?

It is the things that don’t make sense that teach us the most.  

If you want to learn something new, start with something you don’t understand, something which doesn’t make sense.

However much you know there will always be chinks in your knowledge, chinks of light that may lead you to somewhere beautiful.

Consider this:

On a Sunday afternoon your prison guard tells you that he will conduct a surprise inspection at 10am over the next seven days.

You work out that he can’t wait until next Sunday, because then it wouldn’t be a surprise. 

So, could he do it on Saturday?

On which days would the inspection be a genuine surprise?

There is no consensus on this, which is why I describe it as a chink of light, a way to get at something deeper.  But what do you think?

One of his books is on my coffee table.  This is not a coincidence, there is always one of his books on my coffee table.

Many of my puzzles have come from these books.

I know him as the greatest collator and populiser of math puzzles, but of course his talents went far beyond this.

Rather than try to do my own second-rate obituary I will just point you at some links.

Scientific American, for whom he wrote for 25 years.  http://www.scientificamerican.com/report.cfm?id=Martin%20Gardner,%201914-2010

Make your own Martin Gardner Flexagons here, http://www.youtube.com/watch?v=4DETMhTC0H0.

The Daily Telegraph on his deconstruction of Lewis Carroll’s Alice books, http://www.telegraph.co.uk/news/obituaries/culture-obituaries/books-obituaries/7765184/Martin-Gardner.html

He wrote over 70 books.  Nothing I can say can begin to encompass his long and amazing life.  He is someone you need to discover for yourself.

He is already missed.