The Maths Geek

Friday, 27 May 2011

Tutorial: Midpoint rule

In a previous post I spoke about the trapezium rule for integrating functions numerically. The trapezium rule could find the value of an integral with second order accuracy. In this post I will present an alternative method, the midpoint rule. The geometric interpretation of the midpoint rule appears to be more crude than the trapezium rule. Nonetheless, it turns out that the midpoint rule also has second order accuracy.

Like the trapezium rule, we divide our interval $[a; b]$ into $N$ equal sections of width $h = (b - a) / N$ . The area of each section is now approximated by the area of the rectangle of width h and whose height is given by the function value at the centre of the section. The centre of the nth section is given by
$x n + 1 / 2 = a + (n + 1 / 2) h$ .

Here $n = 0,1,..., N - 1$ . As before, we define $f n + 1 / 2 = f (x n + 1 / 2)$ . The area of the $n$ th rectangle is then given by $h f n + 1 / 2$ . And the value of the integral is given by

$\int_a^b f(x)\;dx = h( f_{1/2} + f_{3/2} + \ldots + f_{N-1/2}) = h\sum_{k=0}^{N-1}f_{k + 1/2}$

This is the final form for the midpoint rule. As with the trapezium rule, the accuracy of the integral can be increased by increasing N, i.e. decreasing the step size h. Again we can plot the error of the numerical integral against the number of steps on a logarithmic scale.

In figure the error of the integral

$\int_0^1\sin(\pi x) dx = \frac{2}{\pi}$

when evaluated with the midpoint and the trapezium rule is plotted. Clearly, the midpoint rule has a second order error, as has the trapezium rule. At first sight this is somewhat surprising since the midpoint rule makes no attempt to incorporate the change in the function value over the sections into the approximation.

To understand the accuracy of the approximation, we have to re-interpret the midpoint formula

h f n + 1 / 2

as the area of a trapezoid that intersects the function graph at the midpoint an which has a slope identical to the derivative of the function at that point. It is a simple, but very useful, geometric fact that the area of a trapezoid is the same as the area of a rectangle whose height is the average of the trapezoid's height.

Looking at the error curves a bit more closely, we can observe that the error of the midpoint rule is always slightly smaller than that of the trapezium rule. In fact when we divide the two error curves in the region where they decrease with N^2, we get an almost constant error ratio of about 1/2. This will lead us to improve the two methods. But this will be the subject of another post.

Wednesday, 25 May 2011

Two Ladders Puzzle

This puzzle is an old favourite of mine. It looks quite straightforward but it's not as easy as one might expect.

Two ladders are leaning against opposite walls in an alleyway. The bottom of each ladder is placed on the ground in the opposite corner. One ladder is 4m long, the other is 3m long. The height at which the two ladders meet is 1m.

Question: How far are the walls apart?

Friday, 20 May 2011

Short Thoughts: If a tree falls in the forest...

...does it make a sound. This seems to be a deep philosophical question, but is it really? It just depends on what your definition of sound is. If you define sound as pressure waves in air then the answer is clearly YES. The pressure waves are there, and might influence other objects in the forest.

If, on the other hand, you define sound as through the experience of a human being, then you are linking it to the perception of an individual. In this sense the answer is NO. The tree does not make a sound because there is no one whose brain activity is changed in such a way that she would call it a sound.

I find this definition problematic. What if you had a sound recording device? You could record the sound and play it back later. If no one was present when the device made its recording then where did the sound come from. Did the recording device create the sound from scratch? Or did the tree suddenly make a sound the moment you observe the sound through the recording device? In this way the question resembles the observer problem in quantum mechanics.

But if you go down this route then you have to be consistent and follow this argument through to its end. You should not allow anything to exist unless you are observing it. So the final answer to the question must be:

If a tree falls in the forest and no one is there to hear it then the tree didn't exist in the first place.

Wednesday, 18 May 2011

Non-Vedic Maths: One more here, one more there, do I care?

Multiplying two numbers whose last digits add up to powers of 10

This is my first post in the series of Non-Vedic maths, where I will be explaining speed calculation techniques. These techniques are NOT based on the ancient Indian Vedas but can be derived using elementary maths.

In this first instalment of the series I will be looking at how to multiply two numbers whose last digits add up to powers of 10 and whose leading digits are identical. To explain the method let us first look at two digit numbers. As an example, we multiply 63 with 67. For this method to work the first digit has to be the same for both numbers and the last digits have to add up to 10. Then we can write our to numbers as

10 a + b

and

10 a + c

where

b + c = 10

and

a

is the leading digit. In our example we have

a = 6

b = 3

and

c = 7

. Multiplying the two numbers gives

$\begin{alignat}{1} (10a+b)(10a+c) &= 100a^2 + 10(ab + ac) + bc\\ &= 100a^2 + 10a(b+c) + bc\\ &= 100a^2 + 100a + bc\\ &= 100a(a+1)+bc \end{alignat}$

In the third step we used that b+c=10. The product bc will always be less than 100 so the digits will not interfere with the first term, which is a multiple of 100. In our example we have

63 * 67 = 100 * 6 * 7 + 3 * 7 = 100 * 42 + 21 = 4221

The rule that can be extracted from this is:

Take the first digit and multiply with one more than itself. Multiply the last two digits. The final answer is made up of the two results by joining the results together.

We can represent this graphically in the following way.

The method clearly also works if a is not a single digit number, but it can have any number of digits. If we wanted to multiply 116 with 114 we will get

100 * 11 * 12 + 6 * 4 = 13200 + 24 = 13224

The method can be generalised if the trailing two digits add up to 100 or the trailing three digits add up to 1000 and so on. The maths is similar to the previous case.

$\begin{alignat}{1} (100a+b)(100a+c) &= 100a^2 + 100(ab + ac) + bc\\ &= 10000a^2 + 100a(b+c) + bc\\ &= 10000a^2 + 10000a + bc\\ &= 10000a(a+1)+bc\end{alignat}$

Again,

b c

will always be less than 10000 because each of them is less than 100. To see an example, lLet's multiply the numbers 436 and 464. Here the last two digits add up to 100 and the leading digit is the same in both numbers.

$\begin{alignat}{1} 436 * 464 &= 10000*4*5 + 36*64\\ &= 10000*20 + 2304\\ &= 202304 \end{alignat}$

Of course one has to multiply two digit numbers, which can be a little more complicated. In another post I will present methods that can make this multiplication easier.

Non-Vedic Maths: An Introduction

In the past I have repeatedly been confronted with people who promote Vedic Mathematics. Vedic Maths is a system of mathematical procedures that is supposed to help you master mathematics. The people promoting this system claim that it is based on the old Indian Vedic Sutras which date back over 4000 years. A little study of the subject reveals a slightly different story. Vedic mathematics was first presented by an Indian mathematician called Bharati Krishna Tirthaji Maharaja, in the early part 1900s.

He claimed to have found uncovered the system by intensely studying the old Vedas. However, most scholars, that are not directly involved in promoting the system, agree that the Vedas do not actually contain any of the "Vedic mathematics" sutras. It is, therefore, much more likely that a Tirthaji invented the methods himself, or even copied them from other sources. Another argument against the origin from the Vedas is that the techniques described in Vedic maths heavily rely on the decimal number system. But this system was not invented until much later, after the Vedas were written down.

The Vedic maths system claims to provide calculation strategies which are creative and useful. But they don't really promote a deeper understanding of mathematics. All that these methods really do, is to provide the student with some shortcuts for performing standard calculations in their head. It is interesting to note that the mathematics behind the system is not very sophisticated and was certainly known at the time that a Tirthaji developed these methods.

So, quite clearly, Vedic maths does not date back to Vedic times and cannot be extracted from the Vedas. It is a modern invention that uses the claim of dating back to ancient times in order to promote itself. But all this doesn't answer the crucial question, is the Vedic maths system useful? As I said before, the methods provided do not really promote analytical thinking and, in todays world of computers and pocket calculators, they are not needed in everyday life, and they will not help the student in their future job. To make matters worse, the Vedic mathematics system does not explain why or how the techniques work. So the student is left with learning the methods by heart and repeat blindly. If you believe that education should involve more than pure repetition of facts, and you don't want your children to grow up being parrots, then avoid the Vedic maths system. For two more passionate articles against the system, you can read The Fraud of Vedic Maths or Stop this Fraud on our Children!

Arithmetic shortcuts do have their use however, and that is to impress your friends. If you can find the result of a complex product or sum before your friends can get out their iPhones and start the calculator app, then they will be truly impressed. And if you can still pull this feat after a few pints in the pub, you will be considered the maths genius for the rest of your life. For this reason alone, I will start a series of posts under the heading "Non-Vedic Maths". This series will present mathematical parlour tricks and shortcuts for everyday calculations to impress your friends. I will also go the extra mile and explain why the techniques work. But be warned: learning these methods will not help you in any other way, and you will most certainly be branded a geek by everyone around you.

Read on for the first technique.

Monday, 16 May 2011

Collatz: Bringing some order into the chaos

I recently wrote that I was rekindling my interest in the Collatz problem. I still haven't had the time to read any literature but I came up with an interesting transformation to the problem that seems to unearth some structure which is maybe not directly obvious. For regular readers of this blog, you might see the similarities with this transformation and the formula I posted earlier on calculating the points for interval halving using a closed formula. It really was the Collatz problem that inspired that formula. To the uninitiated, the Collatz problem is based on the sequence
$x_{n+1} = \begin{cases} x_n/2 & x_n \text{ even}\\ 3x_n + 1 & x_n \text{ odd} \end{cases}$

The question is whether, for any positive integer starting value, the sequence will always reach the value 1.

One can reverse the problem in the following way. Define the set C in the following way

$\begin{alignat}{2} &1 \in C\\ &\text{if } x \in C \quad\text{ then }\quad2x \in C\\ &\text{if } x \in C \quad\text{ and }\quad x \text{ mod } 3 = 1 \quad\text{ then }\quad\frac{x-1}{3} \in C \end{alignat}$

The problem then transforms to the question, whether $C$ contains all positive integers, in other words: is $C=\mathbb{N}$ ? In this form the problem can be represented as a tree with 1 at its root, every element $x$ has at most two children. One child is always $2 x$ , the other child is $(x - 1) / 3$ if that number is an integer.

Every odd number $x$ trivially has an infinite number of descendants of the form $2 k x$ . I will call the set of these numbers the tower of $x$ .

Definition: The tower $T x$ of an odd number $x$ is the set $T_x=\{2^k x | k=0,1,2,\ldots\}$ . $x$ is called the base of the tower.

We also define the children of $T$ in the natural way, as a set of towers which are based on those children of the elements of $T$ which are not elements of $T$ themselves.

Definition: The children $C T$ of a tower $T$ is the set

$C_T = \{T_y | y = (x-1)/3 \quad\text{ where }\quad x \in T\quad\text{ and }\quad x \text{ mod } 3 = 1 \}$

It's easy to show that every tower either has no children, if the base is a multiple of 3, or an infinite number of children otherwise.

I would like to find a way to map each tower onto a single number, i.e. every element $x$ of $T x$ should be mapped onto the same value. To do this I take the largest power $k x$ of 2 that is smaller or equal to $x$ : $2^{k_x} \le x < 2^{k_x+1}$ . We now define

$t_x := 2^{-k_x} x - 1$

The values of $t x$ lie between 0 and 1 and are rational numbers of the form

$t_x = \frac{p}{2^k}$ .

It is clear that $k 2 x = k x + 1$ and therefore $t 2 x = t x$ . This means, all the elements of a tower are uniquely mapped onto a single value. We can, therefore, identify these values with the towers they originate from and we will refer to the towers $T$ by their $t_T := t_x, x \in T$ .

The next question that arises is, given an tower $t T$ what do the children of a tower look like. As an example, the children of $t 7 = 3 / 4$ are plotted in the figure on the right. The values of the first few of these children are given in the following table.

Children of t = 3/4
Fraction	Decimal
1 / 8	0.125
5 / 32	0.15625
21 / 128	0.16406
85 / 512	0.16602
341 / 2048	0.16650

It can be seen, and easily proved, that if $p / 2 k$ is a child of any $t$ , then so is $(4 p + 1) / 2 k + 2$ . This results in an geometric series that converges to

$(3p+1)/(3\times 2^k)$

The figure above plots the children of the first 1000 towers against the values of the towers themselves. Interestingly a clear structure emerges. The sequences of the children all seem to converge against two straight line segments. These line segments can be represented by the function

$y = \begin{cases} \frac{1}{3}( 4x + 1) & \quad \text{for } x< \frac{1}{2}\\ \frac{1}{3}( 2x - 1) & \quad \text{for } x> \frac{1}{2} \end{cases}$

When I first plotted this graph and discovered this very simple structure hidden in the Collatz problem, I was utterly amazed. Of course I don't know enough to decide if this structure could hold the key to unravelling the problem but it certainly gives me hope.

Finally, an apology to all those who know more about the problem. These things probably have been discovered already. I have not supplied any references and most likely got the terminology wrong. If so, I will be happy to be corrected.

Wednesday, 11 May 2011

The Three Wise Men Puzzle: Answer

This is the answer to the "Three Wise Men Puzzle" posted earlier.

To understand the reason the men stop laughing we follow the thoughts of one of the philosophers, let's call him A. A sees the other two men, B and C laughing. Assuming that he doesn't have a mark on his forehead, he thinks that B is laughing at C and vice versa. But he must also assume that B is unaware of his own mark on the forehead. If A had no mark, what does B think C is laughing about? In other words, if A's assumption was true, B should quickly realise that C is laughing at B and therefore B should stop laughing. But after enough time has passed, and B hasn't stopped, A must assume that he himself has a spot on his forehead.