Wednesday, June 26, 2013

The hollow triangular numbers are divisible by three

You might be familiar with the triangular numbers: the number of objects that form equilateral triangles like this:

The sequence is 3, 6, 10, 15, 21, ... The first one, 3, is 1 + 2, the second one, 6, is 1 + 2 + 3, the third one, 10, is 1 + 2 + 3 + 4 and so on. For a triangle with a base of \(n\) blobs the number of blobs in the triangle is \(n * (n + 1) / 2\) (which can be proved by various means and was famously figured out by the mathematician Gauss while a school boy).

But what about the hollow triangular numbers? The ones where you take the middle blobs out of the triangles and just leave the border. Like this:
The pattern there is very simple. They are all multiples of three. And the formula would be that the hollow triangle with a base of size \(n\) has \(3 * (n-1)\) blobs in it (and since that's a multiple of three so is the number of blobs in a hollow triangle).

Here are three ways to prove that that formula is correct.

Subtracting the middle

Because we already have a formula for the filled in triangle (see above) we can use it to figure out the formula for the hollow triangle. Look at the triangle with a base of 6 blobs.

You can see that the number of blobs in the hollow triangle with a base of six is the number of blobs in the filled in triangle of base six minus the number of blobs in the filled in triangle of base three. Or, more, generally the number of blobs in a hollow triangle of base \(n\) is

\[\begin{aligned}
&n * (n+1) / 2 - (n-3) * (n-3 + 1) / 2 \\
&= 1/2 * (n^2 + n - n^2 + 5n - 6) \\
&= (6n - 6)/2 \\
&= 3 * (n - 1) \\
\end{aligned}\]
Which is the formula above.

Counting around the outside

Another way is to follow around the edge of a triangle and observe that, for example, for the hollow triangle with a base of six the total number of blobs is \(6 + 5 + 4\) (the blue blobs, plus the red blobs, plus the yellow blobs).

And the more general formula would be that for a hollow triangle of base \(n\) the total number of blobs is \(n + (n-1) + (n - 2)\) which simplifies to \(3 * (n - 1)\).

Mathematical induction

But a real mathematician is likely to prove this in a different way using mathematical induction. That works by beginning with some starting case that can be seen to meet the required statement and a way of going from one case to another.

For example, it's pretty clear that the hollow triangle with four blobs in its base (see above) has nine blobs in total and since nine is divisible by three the statement we are trying to prove 'all hollow triangular numbers are divisible by three' is at least true for it.

Then you just need a way of working up from there. For example, if there was a way to prove that the next hollow triangular number is divisible by three if we know that the previous one was, it would be possible to know that they all were. That's because you'd start with the hollow triangle with four blobs in the base and know that the one with five blobs was divisible by three and then you'd know that the one with six blobs was divisible by three and so on... forever.

So, all you need is to examine one step in this infinite chain of reasoning.

First let's say that \(hollow_n\) is the number of blobs in the hollow triangle with a base containing \(n\) blobs. And let's assume that it is divisible by three. For mathematical induction to be applicable we just need to show that \(hollow_{n+1}\) (the next hollow triangular number) is divisible by three. So, we just need to know how to go from \(hollow_n\) to \(hollow_{n+1}\).

Take a look at the following diagram showing the hollow triangular number with base six (on the left).

You can think of going from \(hollow_6\) to \(hollow_7\) as the same adding a row of seven blobs (on the right) and removing the inside of the old bottom row (coloured in red). So, \(hollow_7 = hollow_6 + 7 - 4\) which simplifies to \(hollow_7 = hollow_6 + 3\). Since we've added three and know that \(hollow_6\) is divisible by three we know that \(hollow_7\) is also.

That can easily be generalized \(hollow_{n+1} = hollow_n + (n+1) - (n-2)\) (added on a row of \(n+1\) at the bottom and removed the interior \(n-2\) blobs leaving just the two blobs on the outside). That simplifies to \(hollow_{n+1} = hollow_n + 3\). And so if we know that \(hollow_n\) is divisible by three then so is \(hollow_{n+1}\) and thus by mathematical induction we know that all hollow triangular numbers are divisible by three.

Back to the triangular numbers

Now that we've got the idea of mathematical induction it's possible to return to a claim a made at the start: for the filled in triangles the number of blobs is \(n * (n + 1) / 2\) when the base has \(n\) blobs. That too can be proved by induction.

The starting case is a base of two blobs. Just by looking at it we can see that it has three blobs in the triangle and \(2 * (2 + 1) / 2 = 3\). So the formula works for that case.

Then consider going from a triangle with a base of \(n\) blobs to one with \(n+1\). All that happens there is that \(n+1\) blobs get added (the new bottom row). So, if the triangle with a base of \(n\) blobs has \(n * (n + 1) / 2\) in total, the triangle with base \(n +1\) has \(n * (n + 1) / 2 + (n + 1)\) which can be simplified as follows:

\[\begin{aligned}
&n * (n + 1) / 2 + n + 1 \\
&= 1/2(n * (n +1) + 2(n+1)) \\
&= 1/2(n^2 + n + 2n + 2) \\
&= 1/2(n^2 + 3n + 2) \\
&= 1/2(n+1)(n+2) \\
&= (n+1) * ((n+1)+1)/2
\end{aligned}\]
Which is just what was expected.

PS I spotted all this staring at the duvet cover the other night. But then again there was that flight I took back in 2008.

PPS In the comments reader tz points out another way to see that the number of blobs in a hollow triangle is a multiple of three. There are three corners and three equal length sides (when ignoring the corners).


Monday, June 03, 2013

Some things I've learnt about public speaking

In the past I've written a couple of blog posts titled Some things I've learnt about programming and Some things I've learnt about writing. People seem to have enjoyed those posts (judging by the page view counts and comments) and so I thought I'd write something about public speaking and specifically about conference speaking.

0. It really does help to know what you are talking about

If you know your subject well then you will be able to talk well within the limits of your knowledge and be interesting and informative. You'll also be more comfortable and your comfort will come across to the audience.

If, on the other hand, you are giving a talk about a subject you know little about you are likely to come across poorly. This is partly because you won't have confidence in what you are saying and partly because it helps to leave audience wanting more. Also, when you are ill informed it's easy to be repetitive and therefore tedious.

I like when there's a very restricted amount of time for the talk, it forces me to figure out what's interesting to say. It's good if I don't have enough time to say everything. I can always continue with a Q&A session, individual chats with audience members or a blog post.

A common mistake amongst speakers is trying to say too much. There's no need: be interesting and you'll get the opportunity to say much more at another time.

1. It really does help to practice

Last year I gave a TEDx talk titled The greatest machine that never was. It was about Charles Babbage's Analytical Engine. As a speaker you are under pressure at a TEDx event because the audience expects you to be interesting, and because the organizers keep to a rigid timetable.

One thing that made my talk enjoyable for the audience was that the organizers of that TEDx forced me to do the talk for them live beforehand. I had been dreading doing that, but it turned out to be key to making the talk flow smoothly. With the slides (which were mostly just single images) printed on paper, I ran through the talk and was able, instantly, to feel what did and did not work. It also helped to cement the flow of the talk in my mind.

And practicing also gave me the freedom to ad lib. On the day I said a few things that were not planned; I was able to do that because the rest of the talk was solid. An entirely ad libbed talk would likely have been tedious and made me seem erratic.

And now I make a point to practice, even if it's just me talking to the teddy.

2. It's good to tell stories

Even if you are giving a technical talk about the internals of the JVM stories help the audience. They provide a framework for the points you are making and they link slides together. Without a story talks can sometimes be a jarring sequence of slides with tenuous connections. Stories act as mental lubricant that helps keep your listeners' minds working.

At StrataConf London last year I gave a talk titled The Great Railway Caper: Big Data in 1955. The talk is intended to be about Big Data and helping to define what that term means (a rather boring topic). But the talk itself is entirely about the Lyons' Electronic Office and one particular program that was written for it in the 1950s. The story of that program tells a story about Big Data today.

And the LEO story starts with another short story. The introductory story is used to tell the audience what I'm going to talk about.

3. Unless you are fascinating don't talk about yourself

You probably aren't fascinating. And the audience probably doesn't care about you or what you've done. They care about your subject matter. It's rare that your subject matter will be you.

Imagine for a moment that you are Neil Armstrong. A talk by Armstrong about the experience of being on the Moon would be more interesting that a talk by Armstrong about himself.

And, ironically, the less you talk about yourself the more interesting you'll be and the more interested the audience will be in you.

4. Passion doesn't mean shouting at the audience

Genuine passion for a topic comes across effortlessly. Pick a subject you really care about and talk about that.

Sometimes you'll see a speaker faking passion by speaking emphatically and shouting at the audience. It's often a sign that they don't have much to say; that's probably why the emphatic, over-the-top style is so popular amongst 'motivational speakers'.

5. Watch yourself

I cringe every time I watch myself giving a talk, but it's important that I do.

When you watch yourself, you can see all the mistakes you make and the mannerisms you'd rather not know you have. You can then be mindful of those problems when you speak.

6. Don't waste words on a "Table of Contents"

If you have a story to guide your talk there's little point having any "table of contents" slides. They just bore the audience and provide an unnecessary structure. The real structure of your talk should be a narrative that leads the audience through your points. Listing the points may be useful as a summary, but I'd even be wary of that. Tell a good story and they'll remember what you said and think you're a great speaker.