It’s been a while since I posted a puzzle and happened upon a nice one today.

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?

Samuel Hansen’s Strongly Connected Components podcast features interviews with all kinds of mathematical luminaries (that sounds familiar!) If you’ve been missing the Math Factor, be sure to check it out!

Here, we discuss, well, Chaim Goodman-Strauss—the tables are turned!

Standard Podcast [ 33:20 ] Play Now | Play in Popup | Download

25 horses have entered your race meeting.  You have to award ribbons to the three fastest, in order.

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

By an amazing coincidence, world-class puzzle creators Ed Pegg (mathpuzzle.com) and James Stephens (puzzlebeast.com) were in Fayetteville Ark. on the very same day! We sit down and discuss the art of puzzle making, their own wonderful puzzles, and their personal favorites.

Standard Podcast [ 39:10 ] Play Now | Play in Popup | Download

Here are some links to some of the things they talk about:

• A sampling of some of Ed’s puzzles (These were for Japan Airlines)
• Jimmy’s Tipover and Antivirus
• Oscar van Deventer’s amazing work on Shapeways and on YouTube.
• Hanayama‘s Cast Series; the Vortex puzzle is terrific.
• Everything by Thinkfun (Rush Hour, the Gordian Knot puzzle) and Smartgames
• Or for pencil and paper games, Nikoli and Games Magazine.
• You can design your own burr puzzles with burr tools or investigate sliding block puzzles on puzzleworld.
• Andrea Gilbert’s click mazes and Robert Abbot’s  logic mazes
• The Art of Puzzles, and Strimko by the Grabarchuk family, on puzzles.com

I don’t know how often we’ll be posting new podcasts, but stay tuned!

Today’s the Nth day of Christmas (The tenth day, to be precise) — as a function of N, about how many gifts total has my true love given me since the first day of Christmas? 

It’s cooler to have a quick estimate of the rate at which the number of gifts grows, rather than the exact formula; there’s a quick way to get a rough sense of the right answer. 

Does the total number of gifts grow exponentially? Factorially? As the square of N? Something else?

Don’t peek until you want the answer!

[spoiler]

Ok: on the Nth day, my true love gives to me 1+2+3+…+N gifts; you might know the formula for that sum, and it’s a good exercise to work it out again, but the really important thing is that when you sum up consecutive integers, the total grows about like N^2 (ignoring pesky constants) 

In fact, if we sum up consecutive kth powers, the total grows about like N^(k+1). This is really a kind of counting version of integration (and in fact, is exactly one of the tools ancient mathematicians, such as Archimedes, used to work out certain integral calculus problems 2000 years before Newton and Leibnitz invented calculus!) So if on day n, we receive about n^2 gifts, by day N, we’ve received about 1^2 + 2^2 + 3^2 + … + N^2 gifts, for a total of roughly N^3.  

Thus the total grows about like N^3, ignoring pesky constants and lower level terms. The exact formula, should you need it for checking your true love’s love, is going to be N^3/6 + N^2/2 + N/3; on day twelve you should be expecting a total of 364 gifts!
 

[/spoiler]

Remarkably, 2011 is the sum of 11 consecutive prime numbers! 

2011 = 157 + 163 + 173 + 179 + 181 + 191 + 193 + 197 + 199 + 211

And of course 2011 is itself a prime number!

What a great prospect for a prime year — our very best wishes to you.

It’s been a few months now since we’ve posted any new podcasts, and  from the many weepy emails asking when, oh when will the mathfactor podcast return, we know we’ve been missed — we’re really grateful that we have so many avid listeners! In the meantime, Stephen Morris has been holding down the fort with many excellent posts here on the site, as you probably know if you’re reading this here. Great work Stephen!

I thought I’d take a moment to share what’s been shaking round here and where things might be going. First off, I have to say, really, it has been nice taking a break from the podcast. After all, we’ve been doing mathfactor pieces steadily for six years! (Still have about 70 early radio segments to post, I think) But I know we’ll get back to it someday, maybe someday pretty soon. Ideas are certainly starting to pile up again…

In my own work, things are going great. Our new course, Mathematical Thought, is chugging along nicely in its second year, with our long-time correspondent Edmund Harriss and colleague Janet Woodland at the helm. This course is really quite radical in its way—students must take significant initiative to succeed, but are free to approach whatever mathematical ideas they want to, in a way that plays to whatever their expertise or interests are. So far, it’s working.

Meanwhile, I’m now teaching geometry for future teachers; I should have done this years ago—it’s obviously the most effective way to have a significant local impact on the culture of mathematics. The students are deep in the midst of wrastling with how to develop and communicate fun mathematical ideas in their classrooms, and the results seem promising.

Some careful listeners may have picked up that I’m now chair of my department, and in that role I’ve been working hard at infusing the place with the sensibility the Math Factor exemplifies:

Serious intellectual engagement is fun, expected of everyone, open-ended into a lifetime.

As happens, our college is in the midst of a major reassessment of our core curriculum, and we have a chance to work in that direction, producing a truly visionary core that will fully model these high ideals. The outgoing dean’s request for innovative course proposals was met by a resounding burst of energy and creativity and it seems we are poised for a really interesting and exciting period here. 

So, when will the Math Factor podcast come back? We’ll see what happens in the next few months, but if all goes we might hope for, I may be in a position to foster a lot more of this kind of fun!

Ciao for now, Chaim

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!

It was very sad to hear that Benoit Mandelbrot has died aged 85.

He is one of very few mathematicians who has both changed the subject and captured the public imagination.  His high idea, that there is a symmetry across scales, is easy to understand especially if you have walked the coast of Britain. 

However it is the images that have really caught the imagination.  This one was iconic in the eighties.  Everyone knew this image, whatever age they were.  

It was also inspirational for a teenager interested in mathematics.

And most people understood the basic idea.  They could see the symmetries, how the main shape was repeated throughout the image on different scales.

This image was already iconic then.  But now we have so much more.  I was struck by this 3D fly-through:

I’m looking forward to putting on my virtual reality helmet and flying through these things, changing scales as I go.

Let’s leave the last word to Benoit Mandelbrot recorded at TED this year.

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?

Read the rest of this entry »