Personal Blogs

I'm a big doodler. Last night I drew some dots in a rough octagon and started drawing lines joining pairs of dots.

Then I wondered how many lines I could draw before I formed a triangle. I don't mean a triangle formed by three lines (although that's an interesting question too), but one with dots at its three corners.

With any problem where you have a series it's always a good idea to look at the small cases. Sometimes it can be misleading though. Still I drew some little sketches

It's easy to be sure the count is right for n = 2, 3 and 4, but even by 5 it gets less obvious. Is there a general formula? I wondered if this was a novel puzzle (and hoped it was); sadly it turns out no, it was investigated by Mantel in 1907. There are various proofs of the result Mantel found, but they are more or less technical and not intuitive. So I wondered if I could present the basic idea of one proof in a more accessible way.

With 5 dots consider a pair x and y that are joined by a line. That leaves 3 others and if we think about any one of these, let's call it z, we see x and y cannot both be joined to z. Otherwise we would have a triangle! So the maximum of lines from either x and y to the other dots is 3. Finally focusing on the 3 other dots, the maxiumum number of lines possible amongst these is 2, otherwise we would have a triangle.

Adding this all up as shown the greatest possible number of lines is 1 + 3 + 2 = 6.

Let's see if we can generalise this idea. Suppose we have n dots and the maximum number of lines that can be drawn without forming a triangle is f(n).

Following the same argument as before, if we are to avoid a triangle, we can have one line joining x to y, a maximum of n - 2 lines joining either x or y to one of the remaining n - 2 dots, and f(n - 2) lines amongst tos n - 2 others. So

f(n) = 1 + n - 2 + f(n - 2) = n - 1 + f(n - 2)

So we can immediate calculate further values

f(6) = 6 - 1 + f(6 - 2) = 5 + f(4) = 5 + 4 = 9

f(7) = 7 - 1 + f(7 - 2) = 6 + f(5) = 6 + 6 = 12

f(8) = 8 - 1 + f(8 - 2) = 7 + f(6) =  7 + 9 = 16

So now we have (for completeness we include n = 1 with 0 lines)

0, 1, 2, 4, 6, 9, 12, 16

Can you spot a pattern?

I’ve got a new job; vaccinating people. Can’t wait to get stuck in.

Repeat five times after me

"On an anonymous ominous omnibus."

I worked with a men’s neckwear company for many years. But it’s all over now, and we've severed our ties.

The police caught me in their dragnet. First they threw an edible water plant over me. Then they shouted, “You’re under a cress!”

Suppose inhabitants of Diss in Norfolk UK had been left without voting rights, as a result of some historical mix-up, and this anomaly was corrected. Then they’d be Diss-enfranchised. Hmm.

There actually is a place called Epsom Downs. Think about it.

The famous American inventor Thomas Edison said genius is 1% inspiration and 99% persperation. He never gave up.

For example he invented the heavy bulb, a total failure.

So he moved on to invent the light bulb, which did a lot better.

Responsive device when a person is out (11)

See comments for solution.

What Came Before Toucans?

Onecans!

My policy about sweeping away cobwebs is put it off until the last possible moment. I call it Dust in Time.