Put the following in order

YouTube channel, College Humor, has a game show series called 'Um, Actually' - a game of nerdy corrections, and general nerd trivia.

One of the 'shiny questions' involves putting things is order, for example, putting space ships or fictional creatures in order by size.

The way the scoring works (as far as I can tell) is you get one point for each item you put in the right 'position'. So if you guess (1,3,2,4), then you would get 2 points for getting 1 and 4 in the correct position.

The problem was, in the creatures game, there was this one creature which looked like a single-celled organism, but was actually the size of a galaxy (or something), making it the largest.

So suppose you get everything else in the right order, but you fell for the trap and put this surprisingly massive organism as smallest e.g. (2,3,4,1)

In that case, everything is in the wrong position, so no points. But I would argue since all but one are in the right order you should only lose one point.

The FineBros channel does a similar game - e.g. put the top 10 most liked videos of 2019 in order. Under their scoring system, you get 2 points if an entry is in the right position, and 1 point if it's off by one. So (1,3,2,4) would be worth 6 points and (2,3,4,1) would be worth 3 points

This is slightly better, but you still have a case where you can lose significant points for getting just one or two entries out of place. For example, if you had (3,4,5,6,7,1,2), then you would get 0 points, even tho 5 of 7 are in the right order.

So, can we come up with a better scoring system?

Levenshtein Distance

The first things that comes to mind is Levenshtein or 'minimum edit' distance.

This measures the distance between two strings (words) based on the minimum number of edits to get from one to the other. In this context, an edit is a single character addition (cats -> chats), deletion (cats -> cat), or substitution (cats -> bats)

Now, this doesn't seem quite relevant to our problem; we're not adding, deleting, or substituting, we're swapping. For Levenshtein, a swap would be considered a deletion + an addition (or 2 substitutions) e.g. cats -> cas -> cast

We could calculate the Levenshtein distance and just divide it by 2 - effectively treat delete+add (2 edits) as equivalent to a swap (1 edit). Or else, we can just take the general principle of finding the minimum number of swaps required to get from the guess solution to the correct order.

As for the actual score, we can take the number of entries in the list (N) minus the minimum number of swaps.

So for our original examples, (1,3,2,4) is worth 3, and (2,3,4,1) is also worth 3.

In the latter case, 1 wasn't 'swapped' with an actual element, but you could think of it as a swap with an implied 'null' element - (..,null,1,2,3,4,null,..) -> (..,null,null,2,3,4,1,null,...)

Dynamic Programming

Dynamic programming is an approach to solving a certain class of problem which would take a ridiculous amount of time to solve by brute force. With dynamic programming, these problems can be solved in a more reasonable amount of time by breaking them down and solving recursively.

One of the classic problem in dynamic programming is - find the longest increasing sub-sequence in a list of numbers?

For example, in (2,3,1,7,4,9,5,8) the longest increasing sub-sequence would be (2,3,4,5,8). So in this case, we might say the score is 5/8

Going back to our other examples, (1,3,2,4) would have sub-sequence (1,2,4) or (1,3,4), worth 3 in either case. And (2,3,4,1) would be (2,3,4) which is also worth 3

Weighted Error

This is all well and good, but doesn't it feel like (2,3,4,1) is 'more wrong' than (1,3,2,4). Each has one element out of order, but in the former that one element if further from where it's 'supposed' to be.

One correction might be to calculate the error as sum[abs(x-x')] where x is the position of an element, and x' is where it's supposed to be. So (1,3,2,4) would be (abs(1-1) + abs(3-2) + abs(2-3) + abs(4-4)) = 2

However, this is flawed. For the (2,3,4,1) example, the error comes out at 6. Once again, we're being penalised for all the elements that are in the right order but off-by-one

So a slight modification would be to only calculate the error for those elements which are out of place - that is, find the longest sub-sequence, and then calculate the error for all elements which don't belong to that sub-sequence.

For (1,3,2,4) the error would be 1 and for (2,3,4,1) it would be 3

But how do we get from the error to the actual score?

We can start by calculating the maximum error, then subtracting the calculated error from it. So what's the maximum error?

The most wrong you can be would be to get everything in the wrong order - i.e. all elements reversed. So if we have N elements, the error would be

abs(1 - N) + abs(2 - N-1) + ... + abs(N -1) = (N - 1) + (N - 3) + ... + (N - 1) = 4 * (N - 2)

Actually, there's a subtle flaw in this reasoning - even if all the elements are reversed, there is technically a longest sub-sequence of 1, so one of the entries shouldn't count towards the maximum error. The element we chose as the 1 correct one will affect the maximum error. If we chose the first element in the sequence, the max error is reduced by N-1, whereas if we chose one from the middle the max error is reduced by 1 or 0 (depending if there is an odd or even number of elements)

For simplicity, we'll just assume the middle entry and say max error adjustment is 0

So going back once more to our original examples, (1,3,2,4) has a score of 8 - 1 = 7, and (2,3,4,1) has a score of 8 - 3 = 5, making the latter 'more wrong' as desired.

Conclusion

I'm not sure if there was a point to all this. I don't think this is useful outside of scoring this particular kind of game.

It might be interesting to run an neural net or genetic algorithm or similar using this as the score function. I'd be interested to see how a neural net performed at sorting, in terms of performance and correctness.

But anyway,


Chris.

Lights Out (Game)

I was watching this year's RI Christmas Lectures, and it reminded me of this game I had when I was much younger. It was, I think, a Christmas present from my grandparents, back in '96. It was called Lights Out, and it looked something like this.

Basically, the console had a 5x5 grid of these rubbery, transluscent buttons with little red lights underneath them. When you press a button, that button and the four adjacent buttons switch state - light on to light off, or off to on. So, in the example below (where blue square are lights), if you press the centre square, the centre square turns off and the four adjacent squares turn on.

In the game, you're given a pattern of lights, such as the one above, and the task is to press buttons until all the lights are out.

Interestingly, in the pattern above (on the left), you can clear the board by just pressing the squares that are on at the start (in any order).

Anyway, I was reminded of that. Meanwhile, I'd been learning some Pygame for this other thing (that I'll talk about in a later blog). Now, Pygame is a Python library for making games (amongst other things). So you can probably see where this is going...

Coding a 'Lights Out' clone was straightforward enough - the code is short and not too complicated. The above images are actually screenshots. You can look at my code/download it here. You'll need Python and Pygame to run it.

This is a very threadbare version of the game. You can load a level as a text file of five lines of ones and zeros, like here. Or else you can just play from a blank board - make patterns then try to get rid of them again (not necessarily as easy as it sounds).

If you want something more fancy, or if you don't want to install Python and all that, there are probably loads of playable clones online.

Now, at this point you're probably thinking "Yeah, that's great. But what about the maths of Lights Out?". And you'd be damn right to ask. If you're interested, there's a good summary, as well as links to articles/papers, on the wikipedia page. I don't want to just repeat what's written there. Basically, it all comes down to linear algebra.


Anyway, have fun with that.


Oatzy.


[Call this a late Christmas present.]

Is There a Formula for The 'Perfect' Christmas Tree?

The other week I was waiting for my tram, reading Metro, and I see this article - Treegonometry: Formula for perfect Christmas tree discovered

In other word, a set of equations that will tell you, for example, how much tinsel, or how many baubles are 'required' for the 'perfect' Christmas tree.

Here is the press release, with the actual formulas.

Now, I have a few issues with this. For one thing, it's a bit silly. Surely the perfect tree is a matter of personal preference, and in that sense can't be defined by a set of mathematical rules.

Plus, it seems kind of arrogant to declare that their way is the 'perfect' way, and that (implicitly) any other way is wrong.

Also, the fact that the equations are preposterously simple (perfect thing = constant*tree height) makes me suspicious of them. But, worse than that, it really bothers me that I have no idea how they were derived.

But I'm starting to rant.

The equations in question were actually from a 'study' by the Sheffield University Maths Society (student from my university), and were commissioned by Debenhams (department store). So, I dunno, maybe I'm just bitter that no-one's ever commissioned me to do maths.

Anyway. If they'd said that these were equations for an 'ideal' Christmas tree, then I'd consider that more reasonable. You can say, for example, that the ideal Christmas tree should strike a balance between too many and too few decorations, etc.

So, to that end, I'm going to have a crack at deriving some, more general, 'Equations for an Ideal Christmas Tree' of my own.


Lights

Before we start, there's one simplification we need to make - we will assume that Christmas trees can be approximated to a smooth, regular, right-circular cone - height h, and base radius r.

There's going to be a certain degree of error as a result of this approximation, but I'm not going for perfect.

Okay. So, for lights, there's actually a justifiable basis for an ideal - the ideal tree should have its lights evenly distributed.

Or, to put it another way, you ideally want to wrap your lights such that you have a (roughly) constant light surface density (lights per unit surface area); because you don't want your tree to be covered in clumps and bald spots.

This seems like a vague point; how do you decide on the correct 'density'?

Well, we actually have two constraints to work from: firstly, we have to wrap a single line around our conical shape, and second, the distance (s) between each pair of adjacent lights on a string will be fixed.

From this, we can layout a (hypothetical) grid on the surface of the tree, so that all the lights are equally spaced out.

So, how do we do that?

1) Draw yourself a cone (tree)
2) Draw a grid
3) Draw lights at the points where the grid lines meet
4) Draw in the proper row lines - these represent the actual string of lights

In this cases, I've drawn the grid a little tight, so you'd probably want two strings of lights to get this layout (hence the two colours).

And if you like, you can play with the distances between rows, and the angles, to get some slightly different layouts

The best grid to try for would be a triangular grid, where the distances between each light and the six nearest are the same

So, let's say we've picked a grid. How many light will we need?

There's a nice short-cut to working this out, without having to worry about lengths of spirals on conic surfaces. To do this, we take advantage of the regular grid layout to work out the lights density (lights per unit area).

Each section of grid is roughly a diamond, with all sides about the same length

So with a bit of trigonometry, you can get an approximate equation for the area of this diamond

Then, the density is one over that area (since there's one light per grid diamond).

We then multiply this density by the total conic surface area (excluding the base) to get the total number of lights needed

And, finally, multiplying that by the separation between lights (s), we get the total length needed:

Easy. Though, somewhat more complicated than the L = pi*h equation, derived by SUMS.

So, then, for the triangular grid (theta=60), you get

Cool.

The only problem then is getting the lights to line up on a grid on the actual tree. So... good luck with that.

Realistically, all of this is mostly irrelevant anyway - you can't go out and ask for, say, exactly 5.83m of lights; you buy your lights in pre-cut lengths. Can't get hold of the 'perfect' length of light? Then your tree is imperfect, and you should feel bad.

Anyway. The point is, if you can get your lights more or less even - so that there aren't any clumps or bald spots -, then as far as I'm concerned, you're on to a winner.


Tinsel

What's interesting about their equation for tinsel is this factor of 13/8. Now, again, I don't know how these equations were derived, so I don't know if this was intentional; But, 8 and 13 are consecutive Fibonacci numbers. Why is this important? Well, the Fibonacci sequence is closely related to spirals.

In particular, there's this thing you see in nature; for example, if you look at the spirals on a pineapple, the spirals going in one direction might be 13 and the number in the opposite direction might be 8. Or the numbers might be 21 left and 13 right... The point is, the numbers of spirals on a pineapple are always consecutive Fibonacci numbers (or sometimes Lucas numbers).

And you get the same effect on other things, like the spirals of seeds in the head of a sunflower, or the seeds on a strawberry, or the spirals on a pinecone, or a cauliflower, or all sorts of things. Hell, maybe the branches on a Christmas tree form Fibonacci spirals.

Vi Hart explains it better than me.

So maybe that has something to do with that pre-factor. Or maybe not. It's an interesting tidbit, though.

Anyway.


The thing with tinsel is different people like to do tinsel differently - some like to elegantly drape it across the outer branches, others like to wrap up their tree light they're restraining a hostage. It's a matter of preference. But it's going to affect the amount of tinsel you'll need.

Where tinsel differs from lights is, you're not trying to set up a grid, or get an even surface density. Rather, in this case, you'd probably want to wrap it such that the rows are more horizontal, with a roughly constant vertical separation.

Here's where things get messy; the equation for the length of a spiral on the surface of a cone is given by

I know, right? Maybe you would be better using the SUMS equation for this one.


Extras

The star/angel is going to be some fraction of the height of the tree.

I don't know what the ideal value of the fraction (alpha) would be, but the 10th they came up with seems reasonable.

Baubles, I haven't a clue how they came up with those numbers. The factor of sqrt(17) makes me think some geometry was probably involved, but I dunno.

You would probably want to figure it out as some ideal ornament surface density, Db (like with the lights). In this case, the number of baubles needed would be something like

In fact, if your baubles are all, more or less, the same, you can lay them out on a grid, like the lights. Though, this time, you'd want to have them a little more spaced out, since baubles are much bigger than fairy-lights. But at least this time you don't have the separation constraint.


Thoughts

Here are various things Ben Goldacre, of Bad Science, has said on the subject of commissioned, 'perfect' formulas. Here is an article by mathematician, Simon Singh. Here is an article on BBC News. And here is a collection of such formulas on Apathy Sketchpad.


To be honest, I wouldn't bother with any of this; their equations, or mine. I mean, would you really want a tree that was 'perfectly' decorated? Cold and artificial are the words that come to mind.

And, frankly, I'm not sure my equations would actually work in practice.

I'd say, use your best judgement on how much of everything you'll need, and just do your own thing. Have fun with it!


Our Christmas tree is imperfect. In fact, it's gloriously imperfect. No, seriously, it's a mess.

My ex's family used to construct these massive, elaborate, works-of-art trees; with yearly colour schemes, and matching baubles, and everything. By comparison, she described our tree as kitsch.

But it's adorned with all the baubles, and tinsel, and decorations we accumulated over the last 20-odd years; at least, the ones that haven't been lost or broken. And, in a sentimental sort of way, it is perfect.

Well, okay, not perfect. But, damn it, it's ours.





Oatzy.


[I want you to know, I had no part in decorating that tree.]

[...And, yes, that's a weeping angel on top.]

Sharing a Burger Between Three

There are several ways to divide a burger evenly between three people.

Probably the best is to cut it radially (like a pizza). It can be tricky working out exactly where to make the cuts, but if you can pull it off, then all the pieces will be roughly identical (topping distribution notwithstanding).

But for the sake of arguing, lets say you want to divide the burger by making two parallel cuts: Where, then, do you make the cuts so that all three people get the same amount of burger?

NB/ This gets quite maths-heavy, so if you're not interested in that sort of thing, feel free to skip right to the end for the solution.



Geometry

For simplicity, we're going to consider the burger as a circle, and make the cuts so that each chunk has the same area. The two cuts are going to be the same distance from, and parallel to, the central axis of the burger, so we only need to consider the position of one of the cuts.

Here's the set-up

We work out the area of the cut-off as the area of the circular segment, minus the area of the triangle.


- Aside: Radians

Radians are basically an alternative way of measuring angles. For maths and physics they're generally more useful than degrees.

They're relatively easy - there are 2pi radians in a full circle, so 2pi radians = 360 degrees

1 radian = 180/pi = 57.3 degrees
1 degree = pi/180 = 0.017 radians, etc.

*    *    *

Back to the circle; with angle x in radians, the area of the circular segment is

The area of a triangle is half base times height..


- Aside: Area of the Triangle

We start by splitting the triangle down the middle, so that we have two identical right angle triangles

The height, l = r*cos(x/2)

The base, b = 2*(r*sin(x/2))

So the area of the triangle is (l*b)/2 = r^2 sin(x/2)cos(x/2)

Finally, use the identity sin(2x) = 2sin(x)cos(x)
to get

*    *    *

So the area of the cut-off is

and it needs to equal a third the area of the circle = 1/3 pi r^2.

So first, we need to find x satisfying

or

Once we have a value for x, we find where to make the cut from

Intermission

The thing about this equation is it doesn't have an exact, analytical solution - to find the solution you have to use numerical methods. Well, I say you have to use numerical methods; these days you can just type the equation into WolframAlpha, and you'll get a solution like *snaps fingers*

Which is nice. I even have the WolframAlpha app on my phone. But when I thought up this question I was on holiday in Sherwood forest, where there was literally no mobile singal.

So that was out of the question. And since I'm not in the habit of carrying a scientific calculator around with me, I was stuck with the basic calculator on my phone. It looks like this:

No trig functions, no square roots, no pi button. It doesn't even do brackets, or have a memory function. Luckily, I am in the habit of carrying around a notepad and pen.

Anyway, there are two ways of working this out with only a basic calculator. The first is 'easier', but only if you know some stuff, and the numbers happen to be nice (in this case, they kind of are). The second is harder, in that it requires more number crunching, but it'll work with any numbers, and can be more precise.

Again, feel free to skip to the solution if you're not interested in the gritty details.



Method One

First of all, here's a graph of the two sides of the equation

hand-drawn with Skitch

We want to find the point at which the two graphs cross. We can see that that happens somewhere between 2pi/3 and pi (120 and 180 degrees). So, lets make a guess that it's exactly halfway between these two values: 5pi/6 (150 degrees).

For the right hand side of the equation: 5pi/6 - 2pi/3 = 0.52

NB/ I'm using pi=3.1416 (rounded to 4 decimal places). If you prefer, you could use the approximation 22/7. The result should be roughly the same.

For the left hand side of the equation, we need to work out sin(5pi/6)

At A-level, we were expected to memorise sin() and cos() of angles 0, 30, 45, 60, 90, and 180 (degrees). We were also expected to know the formulas for sin() and cos() of sums of angles. For sin(), it works like

Why is this important? Well 150 degrees = 180 - 30 (5pi/6 rads = pi - pi/6)

So

And since 0.5 is pretty close to 0.52 - less than 5% error - we can accept the convenience of that answer and say it's close enough.

So our approximate value of x is 5pi/6 = 2.618

[Incidentally, the identity for sin(2x) is just a special case of the above, with a=b=x; i.e. sin(2x) = sin(x+x) = 2sin(x)cos(x)]


Now we just need to work out l/r = cos(x/2) = cos(5pi/12)

For this one, 5pi/12 rads = 75 degrees = 45 + 30, so we can use

So

And we just have to evaluate that. But we don't have a square root button. Now, I just happen to know that sqrt(3) ~ 1.73 and sqrt(2) ~ 1.41.

But I'm just weird like that. Let's say you don't. How do you work it out?


- Aside: Square Roots

There are several ways of working out square roots with just basic operators. For two easy examples:

The first is 'Trial and Improvement' - pick a number, square it, does that give the right answer? If not, pick another number based on whether the last guess was too big or too small.

For example: sqrt(3)

1.5 -> 2.25 -> too small
1.7 -> 2.89 -> too small
1.8 -> 3.24 -> too big
1.75 -> 3.0625 -> too big
1.73 -> 2.9929 -> too small
1.74 -> 3.0276 -> too big
1.735 -> 3.010225 -> too big
1.7325 -> 3.00155625 -> too big
1.732 -> 2.999824 -> too small
etc.

The second method is the "Babylonian Method". It's more systematic, and can converge to the correct answer quicker than guessing. But it can be irritating if your calculator doesn't have a memory function.

It uses the recurrence relation

Basically, you make a guess xn. Divide the number you want to square root (S) by xn. If xn is lower than the actual square root, then S/xn will be greater than it. That means the actual root will be between xn and S/xn, so we make the next guess xn+1 the average of these two values. Repeat until x is sufficiently accurate.

For example: sqrt(2)

x0 = 1.5 -> 2/1.5 = 1.33
x1 = (1.5 + 1.33)/2 = 1.4166.. -> 2/1.4167 = 1.41176..
x2 = (1.4167 + 1.41176..)/2 = 1.41421.. -> 2/1.41421 = 1.41421..

*    *    *

Whatever way you do it, you repeat the process until you get the degree of accuracy you're happy with.

You should get the answer around l/r = 0.259



Method Two

We go back to the equation sin(x) = x - 2pi/3

We still have to find the solution numerically, we still don't have a calculator with a sin() function, and this time the numbers don't work out nicely.

So, the question is, how do we calculate sin(x)?


- Aside: Taylor Expansion

The Taylor Expansion of a function is a way of fitting a polynomial (sums of powers) to a more complicated function. It works like this

Basically, it gives a way of converting a function we can't calculate into an infinite sum of powers of x, which we can calculate.

It's usually expanded around the origin (x0=0), since the equations work out neater. But you can do it around any point, x0=a. This is useful if the value you are trying to calculate is far from x=0. The closer x is to x0=a, the quicker the sum converges.

Even though the expansion is an infinite sum, it's usually sufficient to just take the first few terms, since each additional term makes a smaller and smaller contribution to the sum.

So the trick is working out how many terms you need to include to get some desired level of accuracy.

*    *    *

In this case, I'm going to use the Taylor Expansion of sin(x) around x0=pi, since the approximate value (2.6) is nearer to pi than 0.

Here's what the expansion looks like

So, how many terms do we need to include?

Here's what the graph looks like for different numbers of terms

plotted with WolframAlpha

For a value around 2.6, it can be shown that including the first two terms is correct to ~3 decimal places; the first three terms is correct to ~5 decimal places; the first four terms to ~7 decimal places, etc.

So I would probably go to the third term (for 5dp), but only take the result to 3dp.

NB/ We shouldn't get too hung up on getting an extremely accurate value for x, since we're already getting rounding errors from the factors of pi in the expansion. Also, since we're calculating x to 5dp, we should use pi=3.14159

That means we want to solve

which can't be solved exactly.

So, for finding the correct value (without WolframAlpha), we can use any root-finding method. For what it's worth, I used Trial and Improvement; the other methods are easier with a computer.

But, note that the function is decreasing

So if the guess gives a value greater than zero, you need to increase the value of x (and vice versa).

If you run through all that (I won't go into detail), it gives a value around x=2.605


Alternatively, you could expand around x0=5pi/6 (if you know/can work-out sin and cos of 150 deg without a calculator).

In this case you'd only need up to the term in x^2 (correct to ~4dp). Using this expansion would mean solving a quadratic equation, which is easy. But using this expansion can introduce more rounding errors from the factors of sqrt(3). It's a matter of preference, I guess. The answer should be about the same.


Finally, we need to calculate cos(x/2)

Again, we use the Taylor Expansion to calculate cos(). In this case, we're doing the expansion around x0=0; the expansion is

In this case, you just keep adding terms until the result remains approximately constant to some desired degree of accuracy (3pd).

This gives a value around l/r = 0.265



So What is the Real Answer?

Once I got to somewhere where I could get at WolframAlpha, I checked the real numbers; here are the results:

The approximation of x from Method One (2.618) is an over estimate by ~0.5%, which is relatively acceptable. The approximation from Method Two (2.605) is correct to 3 decimal places, which is definitely acceptable.

And for the value of l/r

From Method One (0.259), the approximation is an under estimate by 2%, and correct to 2 decimal places, so is probably acceptable. The approximation from Method Two (0.265) is, again, correct to 3 decimal places. So that is also acceptable.

So, if the numbers happen to be convenient and you know some trigonometry, you're probably as well using Method One. If not, or if you just want more accuracy, then go for Method Two.



Applying the Results

The results are actually quite nice, in terms of practical application (dividing up a burger). The ratio of the radius (0.265) being close to one quarter, you find the cuts like this

That is, find the central axis, then find the (imaginary) line halfway between the centre and the edge - make the cut halfway between the centre and this imaginary line (maybe cut an extra hair's breadth towards the edge). Repeat on the other side.

Easy.


So, now you know. Obviously, all this applies to dividing any circular thing evenly between three people. You could probably even adapt the methods for sharing between even more people.

And in theory, You could do all this with just pen and paper (no calculator). Though you probably wouldn't want to. I know I wouldn't..


Oatzy.


[Wow, I really managed to stretch that one out.]

A Problem With Puzzles

Here's a puzzle, tweeted by Aetherling

Have a go at it yourself. Solution below.

You see these sorts of puzzle every now and again. And there are usually common 'tricks' to them.

My first instinct was to add the digits. Nothing. Modulus? Nope. Sum and modulus, multiply digits, square, divide? Nope.

So, what?

For some reason, I decided I was going to try some algebra - ignore the fact that the left-hand sides of the equations are numbers, and treat them as variables with some unknown values. And then, add up whatever those values are to get the numbers on the right of the equations.

i.e. 9313 -> '9' + 2x'3' + '1' = 1; 1111 -> 4x'1' = 0; etc.

So from 1111=2222=3333=5555=7777=0 we get that 1,2,3,5,7 = 0

From 0000=6666=9999=4 we get that 0,6,9 = 1

And from 6855=3, 1+'8'=3 => 8=2

4 is undefined. And that makes the answer to the puzzle 2581=2.

It took me about half an hour to come up with that answer..


"If all you have is a hammer, everything looks like a nail"

That is the right answer. But the puzzle suggests that a preschooler would get the correct answer with ease. And I doubt a preschooler would do so with algebra.

So, what would a preschooler do? And why does it take 'higher educated' people so much longer?

What's the 'correct' answer? Take a look at the below

Basically, it's the number of loops in the digits on the left-hand side. This had to be pointed out to me by Aerliss.

But here's the interesting thing - take a look at the values I assigned to the number.

I got to the same answer, and effectively 'derived' the number of loops in the digits, without realising that that's what I was doing.


Source on the subheading quote - Maslow's Hammer.

It's not a perfect analogy, but the idea is this - the more mathematical training you have, the more techniques you'll be trying to use to solve the problem; possibly causing you to miss the 'obvious' answer. As, indeed, I did.

In this analogy, maths is the hammer.

And, strictly speaking, this puzzle isn't a maths problem - even though it's presented as if it were. And even though it can be solved using maths.


Another Problem

Here's another puzzle, recently posted on Reddit

The problem here is that the correct answer isn't known.

The 'obvious' answer (in as much as the one that most commenters came up with) was to add the four cross numbers, divide by 10, and round to the nearest whole number. In that case, the missing number is (23+20+12+3)/10 = 5.8 ~ 6 (B).

But that doesn't explain the set up - why the crosses? Are the positions of the numbers in the cross significant? And rounding is a little messy.

The most compelling proposed solution, once again, doesn't actually involve any maths:

"As far as I can tell, the answer is C: 7 [...] The formula for the number in the center is the number of unique letters shared by the top and bottom numbers as written in English plus the number of unique letters shared by the right and left numbers.."

Finite Rule Paradox

At any rate, what the comment thread shows is, in the absence of a 'true' answer, any answer is potentially correct with some valid justification. Case in point, I've just presented two different possible answers with two valid justifications.

This is an example of Wittgenstein's Finite Rule Paradox.

Stated explicitly - "This was our paradox: no course of action could be determined by a rule, because any course of action can be made out to accord with the rule"

Basically, what I described above..

There's a clearer explanation here. The topic is also a plot point in the novel (and subsequent film adaptation) The Oxford Murders; recommended if you're into maths-fueled murder mysteries.

The paradox is more apparent in 'find the next term in the sequence' puzzles.

For example, if you're given 2, 4, 8, 16 and asked what the next number is, then the obvious answer is 32 - twice the previous number/powers of two.

However, 31 is an equally valid continuation, as Marcus du Sautoy explains:

"[L]et me explain why 31 can be a perfectly legitimate way to continue the sequence 2, 4, 8, 16 ... Draw three dots on a circle and join the dots with lines. The circle gets divided into four pieces. If you now take four dots on the circle and draw all the lines between the dots then you cut the circle into eight pieces. Five dots leads to 16 pieces. But if you draw all the lines between six dots you will only get 31 pieces rather than the 32 you'd expect."

In fact, you can define a function, f(n), which satisfies the first 4 terms of the above sequence, and will give any number you like for the fifth.


The Easy Path

How is that possible? Lagrange Interpolation.

[Discussed in Professor Stewart's Hoard of Mathematical Treasures]

Lagrange interpolation applies to any (numerical) sequence of any (finite) length; so, there are infinitely many ways to continue any given sequence - and, necessarily, one cannot say with absolute certainty that a given sequence will continue in one particular way, only.

Unless the person who set the puzzle says otherwise. Because if it's their puzzle, they know what answer they're looking for. And if you try to score easy marks on an exam by citing Wittgenstein, you're probably going to fail.

Of course, Lagrange polynomials - although interesting that they exist - are likely to be the least interesting way to continue a sequence. Certainly, the equivalent Lagrange polynomial isn't as meaningful or interesting as the circle division sequence; even though they both give the same first 5 terms.

And a Lagrange polynomial will probably never be the most obvious/aesthetically pleasing solution.

"[H]e conjectured that, though in principle all answers were equally probable, there might be something engraved on the human psyche [...] which guided most people to the same place, to the answer that seemed the simplest, clearest or most satisfying. He was definitely thinking that some kind of aesthetic principle was operating a priori which only let through a few possible answers for the final choice." - The Oxford Murders, Chptr 9

Though, as seen in the Reddit puzzle, the simplest answer isn't necessarily the most correct one.


There Must Be Another Way

The important thing is, the existence of Lagrange polynomials 'proves' the Finite Rule Paradox for numerical sequences.

By the same logic, there must exist some functions, f(a,b,c,d), which satisfy the first 20 equations in the first puzzle, but give some values other than 2 for the last. Or, multiple functions which do give 2, but by different methods to the correct one.

Of course, such functions aren't likely to be easy to find. Especially when there are 20 'initial rules' to satisfy. But the fact that there are finitely many rules means it's possible.

Not that counting loops, or manipulating letters count as mathematical functions. But the point still stands.


At any rate, the important thing to remember is not to get too obsessed with the consequences of the Finite Rule Paradox. Or you may end up trying to lobotomise yourself to prove a theory.


Oatzy.


[What comes next - 3, 3, 5, 4, 4, 3, 5, 5, 4, ?]

Funny Story

So there's four of us at the pub, and we're playing the one word game. And we decide that, since this is the future, we should play a marathon game, via Twitter (complete with hashtag, #OneWordGame).

The One Word Game is where a group of people attempt to collectively tell a story, one word at a time. (Also known as Word at a Time Story).

At this point, we've been playing for about two weeks.


So what's our story? Before that, lets play a game.

Below are two 'stories' - one of them is our word-at-a-time story, the other has been randomly generated (using Markov text generation).

Which is which?

When the wizard was masturbating upon a picture of your face which is ugly he said that a giant octopus with swashbuckling offspring however walrus munched on his wardrobe handles while reciting to Steve the only one who played the harmonica case under his umpalumpa cheese tasted spectacular when dipped in French wine and peanut butter making apples with a slightly tangy bumhole that had smelly teeth and pickled onions with slices of cherry on toast. Suddenly a massive caterpillar spawned from a seed which smells of turnip. When select acorns they exploded penises all turned into a

There was no further sound other than the soft tinkle of water. But in the middle of the surface area were encrusted with hard-caked earth but the girl who was confined them to perpetual darkness. This time there would be a very narrow neck extending about an inch above the rest. Could be worth a try I think he changes his name from time to time. Since it was meant to support an entire career However I

The correct answer is, ours is the first one - probably evident from the vulgar language.

As for the second one; I've discussed Markov generators before. In the simplest case, they work by randomly picking words based on how likely they are to follow the preceding word. This particular example was generated from the first four chapters of Dirk Gently's Holistic Detective Agency (Douglas Adams) using this site.

How does this relate to our game?

Well, the game was spread out over such a period of time that, usually, I'd forgotten the story much beyond the previous few words. So, I was picking my words based on what seemed like a coherent continuation to those few. Not unlike a Markov generator.

And, you have to admit, the two make about as much sense as each other.


At any rate, the game is still on-going..


Oatzy.


[What? I never claim our story was funny..]

Simple Harmonic Sleep

So I started using SleepBot Tracker to track my sleep. This is what it's looking like so far

Basically, I'm averaging about 8 hours, except on those two days near the start where I had to get up early for exams.

Now, being a physics student, the graph reminded me of that for damped simple harmonic motion (starting from 20/01, ignoring the first 3 points). And being a crazy person, I decided to try and model my sleep as such.

So what's simple harmonic motion?

Simple harmonic motion is a type of periodic motion with a restoring force directly proportional to the the system's displacement from equilibrium.

For example, a pendulum is a simple harmonic oscillator - it has periodic motion, its equilibrium is the lowest point of the swing, and the restoring force is gravity.

Now, one could argue that sleep is SHM-like - we have some typical sleep length (equilibrium), and if we get too little sleep, then we'll tend to sleep more in response, and vice versa (restoring force). But it's a dubious analogy at best.

A damped harmonic oscillator is one with damping, which tends to reduce the amplitude of oscillations. So, like air resistance in the case of the pendulum, which eventually causes it to stop swinging.

I'm not sure what the sleep-based analogy for damping would be.


There's a standard equation for defining a (weakly) damped harmonic oscillator. It looks like this:

Where:- A0 is the initial displacement, the e bit is the decaying term, gamma is the damping coefficient (which determines how quickly the oscillations decay), cos() is the oscillating term, omega is the (damped) frequency of oscillation, t is time (in days), phi is the phase shift, and C is the equilibrium amplitude.

So working out the variables from the data, the model equation for my sleep looks something like this

And the graph looks like this

And to prove I'm not entirely crazy, here are the real values and the model values plotted together

Not a bad fit, right? [error 0.19]

In fact, you might notice the real data is still oscillating a little. But the equation outlined above tends to a constant amplitude of 8.3 (no more oscillations).

To account for this, we could add a baseline oscillation term

And fitting the data again, here's what the graph looks like

Arguably, a slightly better fit. [error 0.16]

So yeah. Basically, I'm procrastinating..


Oatzy.


[Just gotta be careful not to hit resonant sleepquency]

With Enough Tries..?

Probability is tricky. It isn't always intuitive. Coincidences aren't necessarily as rare or as unusual as they might seem.

I can't remember how I got to it, but the other day I came across the wiki article on the Law of Truly Large Numbers. An interesting idea to say the least.

Then a couple of days later I was looking through one of my books for blog ideas, and came across an essay with an example strikingly similar to that in the wiki article (in never gave it a name).

Coincidence?


So what is the Law of Truly Large Numbers?

The Wiki page gives this description:

[The law] states that with a sample size large enough, any outrageous thing is likely to happen.

The example given on the page is a little inelegant, so I'll go with the (abridged) similar example from the book,

Suppose that a really memorable, once in a lifetime coincidence is one which has a one in a million chance of happening today, and that during any particular day there are 100 opportunities... [T]he chance that one of these coincidences will happen to you tomorrow is 1 in 10,000. Still very unlikely...

[But] the chance that every one of the next twenty years will have no one-in-a-million coincidences for you is.. 0.48, or a 48 per cent chance.

According to this extremely rough and ready calculation, there is actually more than a fifty-fifty chance that in the next twenty years you will experience a memorable one-in-a-million coincidence. This also means that for every twenty people you know, there is a greater than 50% [chance] that one of them will have an amazing story to tell during the course of a year.

Now this is an interesting thought.

And it raises an interesting question - If you play the lottery enough times, does winning eventually become significantly more likely? Inevitable?

It's an often quoted 'fact' that you're more likely to be stuck by lightening on your way to buy your ticket, than you are to win. But what does 'the law' have to say on the subject?


Preamble

For this we're assuming a good old fashion, six balls from a pool of 49 lottery.

Probability of winning the jackpot (matching all six balls) with one ticket is 1/13983816 or about 7 in 100million

If you play two lotteries, then your odds of winning are (Odd of winning the first) + (odds of winning the second) + (odds of winning both).

OR, and this is easier to work out,

Let 'Odds of not winning', q = 1-p(winning)

'Odds of winning at least once in two games' = 1 - (odds of winning neither) = 1 - (q*q)

This can be generalised to 'Odds of winning jackpot playing n games', p = 1 - (q^n)


Round One: Will I hit the Jackpot in My Lifetime?

First of all, odds of winning the jackpot by playing every week for a year

p = 1 - [1-p(winning)]^52 = 3.7 in 1million

So not great. How about if you play ever week, starting on your 16th birthday and giving up (dying) on your 86th. Or basically, playing for 70 years. Probability of hitting that jackpot?

About 1 in 4,000 chance. So still not great.

Of course, if you buy 40 tickets a week, then that gives you a 1 in 100 chance of winning the jackpot at some point in your life. But by that point you're spending £2,080 a year on lottery tickets. The average jackpot would have to be more than £14.6 million for the expected return (prize*chance of winning) to make it worth playing.


Round Two: What About Immortality?

So we've got the equation p = 1 - (q^n)

The question is, can we find n - i.e. the number of games you'd have to play - such that the probability of winning (p) is 50:50

The trick is logarithms, and the formula is

n = log(1-p)/log(q)

So for p = 0.5, n = 9,692,842 games, or about 186,400 years.

For a 1 in 4 chance of winning? 77,363 years

1 in 100 hundred chance?! 2,703 years

Alternatively, to have a 50:50 chance of winning in your lifetime (70 years) you'd need to buy 2,663 tickets a week. Yeah.

Basically, even by the Law of Truly Large Numbers, and immortality, you'd be waiting a ridiculously long time and you'd still be lucky to win.


Round Three: I'll Take Anything!

Now wait a minute, I hear you say, I could still win something by matching 5 numbers, or even 3. Okay, that's a fair point.

So you need to match 3 or more numbers to win something. Probability of winning anything in any given game? ~6 in 100,000

So once again, chance of winning something if you play every week for 70 years? 195 in 1,000

Now that's interesting. That's just short of a 1 in 5 chance. But to be worth playing, the average prize value would have to be ~£18,666. Worth it? I'll let you decide*.

And finally, how long would you have to play to have a 50:50 chance of winning something? ~223 years. Or 45 years if you buy 5 tickets a week.

Which is going to be a real kick in the balls if that something turns out to be £5.


Or To Put it Another Way

* Imagine a game you only get to play once. You pay me £3,640 to play, then you pick a number between 1 and 5. I then generate a random number between 1 and 5.

If the number that's generated is the number you chose then you will win some randomly chosen prize between £5 and £5million; you're more likely to win a smaller prize than a larger one, and you can't know in advance what the prize will be.

Want to play?

If you play the lottery, but answered no to the above, you should probably reconsider.


tl;dr As has been said many times before, your odds of winning the lottery jackpot are catastrophically minute. Even if you were to play every week of your life.


Oatzy.

Toilet Roll

Do you ever wake up in the morning, go to the bathroom, and wonder "how much smaller would the toilet roll be if it didn't have that hole in the middle?".

Yeah, me too.

As it turns out, it's not that hard to estimate. First of all, we note that the roll is near enough to a regular cylinder that we can simplify the problem to two dimensions. We're then just dealing with areas of circles.

Of course, you could just re-roll an actual toilet roll by hand to find out. But that would be silly.

Here's a diagram

The left one is the roll as it is, the green bit of the right is the roll as it would be if it didn't have the hole in the middle (r2 being the new radius), and dr is the change in radius size - what we want to work out.

The point here is that the areas of matching colour in each diagram are the same size. So we can equate the formulas for the (green) areas and use a bit of algebra to find an equation for dr.

The full derivation is left as an exercise for the reader.

The resulting equation looks like this

And plugging in values measured from an actual toilet roll we get,

So the answer turns out to be a decrease of about half a centimeter, or of ~9.5%. Which isn't that much - about 1/5th the radius of the hole.

So now you know.


Oatzy.


[Before you say anything, read what it says at the top of the blog]