I was linked to a collection of Edsger Dijkstra’s writings today, and spent an interested half hour reading some of them. Djikstra was known for composing his manuscripts in longhand, using a fountain pen. He would then make a dozen or so photocopies, and mail them out to people he knew to be interested in his work. They would then be further disseminated by those people, and so on, until his work had reached a wide audience. Each article was coded with his initials EWD, followed by a three or four digit number — they thus became known as EWDs in the computer science world.

The most interesting article I read today was EWD831, whose full title is Why numbering should start as zero. Djikstra argues persuasively that counting should start from zero, and thus that all arrays should be indexed beginning from zero. This runs counter to the natural intuition (and to what we are taught at school) that counting begins at 1.

In brief, Dijkstra’s argument runs like this. There are four possibilities for notating the range of numbers 1, …, 10 without using ellipsis notation, which can be ambiguous:

1. 1 ≤ i < 11
2. 0 < i ≤ 10
3. 0 < i < 11
4. 1 ≤ i ≤ 10

There are several desirable properties that we might want our system of notation to have. For example:

• (a) the difference between the bounds is equal to the number of terms in the sequence
• (b) two ranges are adjacent if the upper bound of one is equal to the lower bound of the other.

Both 1 and 2 satisfy these properties, but 3 and 4 don’t. If we want to use our notation to specify a range of natural numbers, then it seems sensible to ask for the following two properties:

• (c) the lower bound is a natural number
• (d) the upper bound is a natural number, even when defining the empty sequence

Property (c) is only satisfied by 1 and 4 and property (d) is only satisfied by 1 and 3 So we see that it is only notation 1 that satisfied all of the properties we desire.

Now we move on to the question of whether we should start indexing at 0 or at 1. This is simply an issue of aesthetics. If we want to describe the range of an array with N entries, then by starting at 0 we would write the range as 0 ≤ i < N, whereas if we start indexing at 1 then it is written as 1 ≤ i < N+1, which is significantly more ugly. So we see that we should start indexing at 0. Note that programming languages such as C, Java and Python all follow this convention, as do most widely adopted languages. The only commonly used languages I can think of that don’t use it are Fortran and R.

Quick post to mention some of the more useful Mac OS X keyboard shortcuts in Google Chrome, to make your browsing simpler, faster and more effective. More as a reminder to myself than anything else, because I keep reading these, swearing that I will remember them, and then not doing it. Many of these come down to making Chrome behave more like a decent text editor, à la emacs or vim.

Tabs and windows

+T opens a new tab

+W closes the current tab

+shift+T opens the last tab you closed (Chrome remembers the last ten tabs you had open)

+alt+left and +alt+right move left and right along your open tabs

+H hides Chrome

+L jumps to the address bar

+alt+F jumps to the address bar and prefixes a ‘?’ so that whatever text you enter will be interpreted as a Google search (on Windows you can do this by pressing ⌘-K — I wonder why it’s more complicated on a Mac?)

⌘+D bookmarks the current page

Webpage shortcuts

⌘+ and ⌘- change the zoom level of the page; use ⌘+0 (zero) to return to default zoom

⌘+F find text within the current page

⌘+E use the current highlight to find text within the page

Text editing

alt+left and alt+right move the cursor left and right by words

+left and +right move the cursor to the beginning or end of the line

Hold down shift to highlight the characters that the cursor passes through.

Suppose you have a set of cards labeled 1, 2, …, N. You shuffle them, and start dealing out the deck. As you deal it out, you keep a card if it’s the highest card you’ve seen so far. Otherwise you discard it.

You always end up keeping the first card; you keep the second only if its higher than the first, the third only if its higher than both of the previous two, etc.

On average, how many cards do you keep once you’ve dealt through the entire pack?

A related problem to the last post. You toss a fair coin, and keep going until the number of tails you’ve seen is n more than the number of heads. On average, how many times do you toss the coin before you stop?

Unlike the last problem, I don’t know the answer to this one, so I’d be interested in hearing anyone else’s approach. I believe that I have a good method for getting at the answer, but that I’m missing one crucial step that I haven’t yet been able to fill in.

I have a lot of coin-tossing problems floating around in my head, of varying levels of difficulty. Here’s one which requires some thought, but shouldn’t present too much of a challenge if you’ve seen this kind of problem before.

You start flipping a fair coin, and keep going until you’ve seen n heads in a row, when you stop. On average, how many times do you flip the coin before stopping?

This is what spaghetti looks like

Here’s a nice problem in probability. I like it because at first sight it seems fiercely complicated, but thinking about it in the right way makes it seem much simpler.

You have a bowl filled with n strands of spaghetti. You pick two ends from the bowl at random, and tie them together. You keep doing this until there are no more loose ends. Obviously, you will have made some number of loops when you reach the end of this process.

What is the average number of loops created?

Let’s play a game. I pick a number — any number at all (whole number, fraction, whatever). I then flip a coin to decide whether to add 10 or subtract 10 from it, and I tell you the result. You win the game if you can tell me what my original number was.

For example, suppose the number I picked was 31. I flip a coin, getting heads, and therefore add 10, getting 41, and that’s the number I tell you. Now you know that I picked either 31 or 51. It seems that you have no way of deciding between those, so your chance of winning the game is 1 in 2.

I contend that you can win the game with a probability of greater than 1 in 2, although I will admit that I can’t tell you how much greater the probability is.

Let’s introduce a bit of terminology. We’ll call the first number that I pick X. This is the number that you’ve got to guess. Then I flip a coin and add or subtract 10 from it, getting Y, which is the number I tell you. So we know that Y = X + 10 or Y = X – 10.

The secret to you winning the game is to pick your own number, Z, before I tell you Y. It doesn’t matter how you pick Z, so let’s just say that you have a computer program that generates a random number for you (from the standard normal distribution, if you want to get picky).

Now you play the following strategy:

• If Y < Z then you guess that X = Y + 10 (ie I subtracted 10)
• If Y > Z then you guess that X = Y – 10 (ie I added 10)

I claim that this strategy will win you the game more than half the time. To see why, we have to consider three cases:

1. If X < Z – 10 then we always have Y < Z, so you guess X = Y + 10 and get it right 1 time in 2.
2. If X > Z + 10 then we have Y > Z, so you guess X = Y – 10 and get it right 1 time in 2.
3. But if X is in the interval [Z – 10, Z + 10] then your guess will always be right. If X = Y – 10 then we always have Y > Z, so you guess X = Y – 10, which is right. And if X = Y + 10 then we have Y < Z, so you guess X = Y + 10, which is right.

As long as there is some chance that X is in this interval, then there is a greater than 50% chance of you winning the game.

I’m flat hunting at the moment. This is possibly one of the most infuriating tasks to undertake, especially if you’re doing it in London, where the property market moves so fast that you can hear of a property coming onto the market in the morning, make an appointment to see it in the afternoon, and get a call at lunchtime to say that it’s been taken already.

But I have good news! My flatmate and I found a great place in Wapping, we’ve made an offer on it and we’re just waiting to see if that goes through. In the process, an interesting little puzzle came to light that I thought I’d share with you.

Like most two bedroom flats, the apartment we’ve seen has a master bedroom and a second bedroom. The master bedroom is better in every way — it has an ensuite bathroom, it’s about 50% larger, it looks cooler and it has a TV built into the wall. Obviously, both of us would prefer to have that room over the smaller room.

The question is, what’s the fairest way to decide which of us gets that room? We’re willing to split the rent up differently, but how should we decide on an appropriate split that leaves us both happy now and, more importantly, will leave us both happy for the foreseeable future?

Both me and my flatmate are ex-mathematicians, and thus are willing to put up with almost any amount of complicated wrangling if it means that we get to the right answer – so feel free to make it as involved as you like.

A little while back, science punk Frank Swain posted a mathematical puzzle on his blog. The puzzle can be described simply — space n points equally around the unit circle, and draw all possible lines connecting those points. How many triangles are there in the resulting graph?

The first couple of cases, n = 3 and n = 4 are easy — the answers are 1 and 8. For n = 5 it requires a little more thought, but stand-up mathematician Matt Parker has a very clear explanation of why the answer is 35 on his website.

The six-sided mystic rose

After that, it gets progressively more difficult to count the triangles. The diagram for n = 6 is on the right. Try keeping track of all those triangles in your head (although CloudoidLtd has a very pretty, and easy to understand, solution for n = 6 and n = 7 on his blog.) The answers there are 110 and 287.

I was inspired by a comment on Frank’s blog to try a more traditionally combinatorial approach to solving the problem. The key observation is that each triangle is made up of exactly three chords. These chords can intersect at one of the points around the circle, or they might intersect somewhere inside the circle. We just have to classify the different ways that three chords can intersect to form a triangle, and then count up how many there are in each case.

A guide to choosing

The explanation will require that we understand how to calculate the number of ways of choosing a set of k objects from a larger set of n objects. We use the notation (n,k) as a shorthand for this. We pronounce it “n choose k“, and we definite it mathematically by

(n,k) = n! / k! (n-k)!

The exclamation mark is the factorial function, which means that we multiply together every number from n all the way down to 1, so that for example 4! = 4 x 3 x 2 x 1 = 24 (we also have the useful convention that 0! = 1). If you’ve not seen this before, it can be a fun exercise to try and work out why (n,k) has to take this form.

Counting the triangles

We’re trying to count the number of ways that three chords of the circle can intersect to form a triangle. Each chord involves two points around the circle, so there are only four cases to consider:

Triangle with 3 points

1. The chords form a triangle between three points. This is the simplest case to consider. Every set of three points around the edge of the circle contributes one triangle, so the number of triangles is simply the number of ways of choosing 3 objects from a set of n objects, which is (n,3).

Triangle with 4 points

2. The chords form a line connecting four points. There are (n,4) ways of choosing a set of four points, and for each set of four points there are four ways we can arrange the chords so that they form a triangle. So this contributes another 4 * (n,4) triangles.

3. Two of the chords share a point, and the third chord cuts across them. This involves five points in total. There are (n,5) ways of choosing 5 points, and for each set there are five ways to arrange the chords so that they form a triangle. This contributes another 5 * (n,5) triangles.

Triangle with 5 points

4. None of the chords share a point, so there are six points in total. To make a triangle we have to join opposite points, so there is only one way of arranging the chords so that a triangle is formed. This gives another (n,6) points.

With all of this counting done, we have a formula for the number of triangles formed by the mystic rose with n points, which we denote by T(n):

T(n) = (n,6) + 5 (n,5) + 4 (n,4) + (n,3).

So how does this formula stack up when we compare it to the results we already know? With suitable adjustments for when n < 6 (because (n,k) is meaningless when k > n) we get

T(3) = 1, T(4) = 8, T(5) = 35, T(6) = 111, T(7) = 287 and T(8) = 644.

This works for most of the cases, but the actual answers for n = 6 and n = 8 are 110 and 632. The formula overcounts by one triangle for the 6-sided rose, and it overcounts by 12 triangles for the 8-sided rose. What’s going on?

Overcounting, and why the problem is hard

We can see the problem by looking at the 6-sided rose at the beginning of the post. The three chords which cut the circle in half all meet at the center. They don’t form a triangle, but our formula treats them as if they do. This is why it overcounts by 1.

It’s interesting to note that if the points weren’t equally spaced around the circle, but instead were randomly spaced, then we wouldn’t have this problem. It’s unusual for three lines in a plane to all intersect at the same point — it requires some special structure, and in this case the special structure is given by demanding that all the points lie on the vertices of a regular polygon. Injecting some more randomness into the problem would actually make it easier. The problem would be one of pure combinatorics — that is, just a problem of counting. Because of the additional regularity, we have made it a problem of geometry. Not only do we have to think about how the points are connected by lines, we also have to worry about the exact locations of the points. This is why the mystic rose puzzle is hard!

Finding the intersections

Whenever we have three or more chords intersecting at a point inside the circle, our formula is going to overcount the number of triangles, so we need to correct for this somehow.

Intersections at the center of the circle are easy to deal with. When there are n points, and n is even, then there are n/2 chords which pass through the center of the circle. Each set of three chords contributes one false triangle, and there are (n/2,3) ways of choosing 3 chords from a set of n/2, so we can modify our formula to:

T(n) = (n,6) + 5 (n,5) + 4 (n,4) + (n,3) – a(n) (n/2,3)

where a(n) = 1 if n is even, and a(n) = 0 if n is odd. This formula now gives the correct result for n = 6, although it still fails for n = 8.

A number of interesting hypotheses spring to mind, which would simplify the problem if they were true:

1. The intersections only occur at the center of the circle.
2. The intersections all occur along lines joining two points at opposite sides of the circle.
3. The intersections all occur along symmetry axes of the rose.
4. Except at the center, only three chords ever intersect at one point.

Unfortunately, none of these is true. Hypothesis 1 can be seen to be untrue if you look at the 8-sided roses in the pictures above. Around the center of the rose there are 8 points where three chords intersect. These explain 8 of the overcounted triangles. The other 4 are from the intersection of four chords at the center — every set of three chords intersecting at the center gives a false triangle, and there are (4,3) = 4 ways of choosing a set of three chords from four.

To see why Hypotheses 2 and 4 are false, we have to look at the 12-sided rose. Using the mystic rose drawer at nrich you can draw mystic roses with up to 20 points. For the 12-sided rose pictured on the right, we see that there is an intersection of 4 chords which doesn’t occur along a line joining two points on opposite sides of the circle. Damn!

The 4-chord intersection

To see why Hypothesis 3 is false, we have to look at the 16-sided rose. Now the three-point intersection doesn’t occur on a symmetry axis (can you see it? It’s in the top left quadrant of the picture). This means that this intersection is repeated 32 times around the circle, rather than the 16 times that we’d see if the intersection was on a symmetry axis.

A 3-chord intersection for n = 16

One hypothesis that does seem to be true is this one:

5. When n is odd, there are no intersections of three or more chords.

This means that our formula should work for all odd n, and indeed for every n that I’ve checked, the formula holds. I still don’t have a proof, though!

With all of these hypotheses rejected, we have to come up with a criterion for the intersection of three or more chords of the circle, and a way of determining how many such intersections there are when there are n points spaced equally around the edge of the circle. This is to come in Part II of this blogpost.

My favorite kind of puzzles are those which sound like they’re going to be an absolute nightmare, but turn out to have a particularly beautiful solution. They’re even better if you don’t really need to know any math to solve them. Here’s such an example, which absolutely delighted me when I first solved it.

An irrelevant picture

I presented it to two of my friends on a long train journey — one of them is a mathematician (in fact he’s a research fellow at Queens’ College, Cambridge) and the other works for a pharmaceuticals company. The non-mathematician got it first. It really is a problem that anyone can have a crack at.

First, I’ll describe a warm-up puzzle. It’s kind of a barometer for the real puzzle.

The challenge: produce a deck of cards, each with a whole number painted on it, with which you can make any number between 1 and 1 million, by picking out some of your cards and adding together the values. You should do this with the least number of cards possible.

Got that? You may want to stop reading and think about it for a second, because the solution is coming up in the next paragraph. I’ve found that computer scientists and programmers tend to get this one faster than most people — often with less than a second’s thought.

The answer is that you should label your cards with the powers of two, so that your deck starts 1, 2, 4, 8 … If you didn’t come up with this solution, the way to think about it is to figure out what cards you’d need to make each of the numbers from 1 up to 1 million. You need to be able to make 1, so you’d better have a card labeled ‘1’. Similarly you need a card labeled ‘2’. But with those two cards you can already make 3, so the next card that needs to be added to your deck is labeled ‘4’. After a while you should spot the pattern, and come up with an argument for why this will work for every number up to a million.

Now here’s the real puzzle, which is a bit more tricky, but fun to think about. I’m not going to give the answer now — I’ll post it in a couple of days.

Produce a deck of cards with which you can make any number between 1 and a million by picking cards and adding together their values, even if you have lost one of the cards in the deck.

The requirement that your deck is insensitive to the loss of a card makes the problem tricker to think about, but a similar approach to that described for the easier problem can work. For example, you know that you need to include two cards labeled ‘1’, so that even if you lose one of them you can still pick cards that add up to give 1.

For those inclined to a challenge, there are three levels of answer:

1. Describe the deck of cards that solves the puzzle (easy, requires almost no math.)
2. Prove that you can make any number between 1 and a million, even if you lose a card (not too hard, requires a little bit of math.)
3. Prove that this is the minimal deck of cards that solves the puzzle (difficult, but still needs no math beyond high school.)

I learned this from my office mate, Toby Wood, but I’m not certain where he got it from. If you know, please leave a comment!

Proto-hacker, ex-mathematician and aspiring flaneur. Now living in London and making my living from algorithmic trading.