Twitter response:

Category: Interesting math

Interesting math

The Monty Hall Problem

The Monty Hall problem is a probability puzzle based on the American television game show whose host was Monty Hall. The popular show was called Let’s Make a Deal.

Imagine you’re having a really great day, and you’re feeling very lucky so you decide to go on the show. Monty Hall picks you for one of the games. You see three doors.

monty-hall

These are the rules of the game: Behind two of these three doors are goats, and behind one door is a brand new car. (Let’s say you’re trying to get a car and not a goat.)

Let’s say you already chose one of them, for example the red one. The host now, who knows what’s behind the doors, opens the green doors which have a goat.

goat behind doors

Now the host offers you the chance to change your decision. What do you do? Do you stick with the door you chose or do you change? It may seem odd, but the odds are not $ 50 – 50$. You should switch the door – by doing that you’ll have almost $ 67%$ chance of winning.

goats and car behind doors

Why exactly should you change your decision?

First you have three choices. The chance of winning is $ 1 : 3$. If you stick with the door you chose your chance will remain $ 1 : 3$. This means that there must be $\frac{2}{3}$ chance the car is somewhere else. If we know that the car is not in the last door, this means that there is $\frac{2}{3}$ chance the car is behind the yellow door. It is not certain that the car will be behind the yellow doors, but there is twice as much chance he is behind the yellow door than it is behind the red door.

Now let’s imagine having 100 doors. Now you got yourself in a kind of a bad situation. You have only $\frac{1}{100}$ chance to get it right. Now what if the host opens 98 doors with all goats behind them? Now you are left with only 2 doors. This becomes a bit clearer. The chance you got it right remained $\frac{1}{100}$, but the chance that the right door is somewhere among the other 99 door is now concentrated on the door you didn’t pick.

The Magic Square
The Magic Square

Learn about the magic square. During the 14th century, Europe was devastated by the plague. Since medicine in the Middle Ages was extremely basic, they had no power over this terrible disease. People were terrified because they believed that Black Death was punishment from God.

plague

Image credit: Wikimedia Commons user Nicolas Poussin

They resorted to less verified sources and massively became superstitious. Here came the idea that mathematics can help prevent diseases and keep the devil at bay.

Some mathematicians created so-called magic square – a square table of order n containing numbers from 1 to n2 so that the sum of numbers in each row, column and both diagonals is the same. Soon enough, magic squares were everywhere.

square before

Image credit to Eve Andersson

How do you calculate a magic square?

We will show you how to calculate a magic square.

How to construct the magic squares of any order?

Order of the magic square represents the number of its rows or columns.

Construction of magic squares is divided into two different procedures:

  • One where its order is odd
  • One where it’s even

First, we’ll show the construction of magic squares with odd order.

Start with an empty square and draw a grid in it. For example, we’ll make a magic square whose order is 5.

square with order 5

Divide every side on 5 parts and draw parallels to make a grid with 25 squares.

Now on every side of this square we’ll construct a “triangle” of 4 squares. You will see these in green.

constructing triangle with 4 squares
Now, starting from the top left diagonal, draw numbers from 1 to 25 in every other diagonal (including the added “triangles”).

numbers in drawn triangle

If the order is $ n$, your last diagonal should end with n2. Now we should simply fill in the gaps. You take the numbers from those triangles and translate them vertically or horizontally to the furthest free place. If the number is placed on the top triangle, you’ll move it down. If it’s on the left, you’ll move it right and so on.

translating numbers in triangle squares

And the final result is:

the final result

Now we’ll show construction of magic squares of even order.

It is impossible to construct a magic square whose order is equal to 2. We’ll show how to construct a magic square whose order is equal to 4.

Draw a grid 4 x 4 and color them like this:

constructing magic square with order 4

Starting from the bottom right corner, write numbers from 1 to $ n_2$.

magic square with numbers inside

The numbers in the white cells are here to stay. But the numbers in the pink cells must be rearranged.

Now erase the number in the pink cells and start the counting again from the top right number corner.

magic square 3

Now, the numbers in the white cells will remain as they were, and pink cells will take the numbers from the counting. This is the final result:

constructing magic square 4

Of course, you can test it out. The sum of all rows should be equal to the sum of all columns and the sum of diagonal numbers.

History of pi
History of pi

The number Pi has been known for almost 4000 years. Pi is one of the most fascinating numbers.

Imagine: if you write down an alphabet and you give each letter a certain number, in some part of pi your whole future can be written. This is because pi is infinite and there is no sequence of numbers that is repeating. Pi is ratio of the circumference of a circle and its diameter. The ancient Babylonians gave very rough approximation to pi- they estimated it to 3. The first real calculations were done by Archimedes of Syracuse.

number pi

Image credit: Wikimedia Commons user John Reid

Pi is ratio of the circumference of a circle and its diameter. The ancient Babylonians gave very rough approximation to pi- they estimated it to 3. The first real calculations were done by Archimedes of Syracuse. He showed that pi is one number between $ 3 \frac{1}{4}$ and $3 \frac{10}{71}$. He approximated the area of a circle based on the area of a regular polygon inscribed within the circle and the area of a regular polygon within which the circle was circumscribed.

graph of pi

Through all history, people found pi interesting. They wanted to know pi to more decimals, but couldn’t. Then the great Indian mathematical genius – Srinivasa Ramanujan started observing pi. He discovered remarkable formula for computing pi:

formula for calculation of pi

But it still all remained as estimation.

Later on, using the computer Alexander J. Yee and Shiger Kondo claimed to have calculated number pi to 5 trillion places. The main computation took 90 days.

first 500 digits of pi

Now we use the standard approximation to $\pi – 3.14$. But what if we want to remember pi to more than two decimals? We’d want to write it down as a fraction. For this we’ll use continued fraction.

Remember that the continued fractions come in form:

continued fractions form

Let’s first take that $\pi = 3.14159$.

First number will be the floor of the starting number:

$ \mid a_0 \mid = \mid 3.14159 \mid = 3$

Now we have to calculate the first help variable $b_1$:

$ 3.14159 = a_0 + \frac{1}{b_1} \rightarrow b1 = 7.0625$

Using the help variable we can calculate $a_1$:

$ a_1 = \mid b_1 \mid = \mid 7.0625 \mid = 7 \rightarrow a_1 = 7$

Now you simply continue the process.

$ b_1 = a_1 + \frac{1}{b_2} \rightarrow b_2 = 15.96424$

$ a_2 = \mid b_2 \mid = \mid 15.9642 \mid = 15\rightarrow a_2 = 15$

$ b_2 = a_2 + \frac{1}{b_3} \rightarrow b_3 = 1.037$

$ a_3 = \mid b3 \mid = \mid 1.037 \mid = 1\rightarrow a_3 = 1$

This calculation leads us to our fraction approximation of pi:

$\pi \approx [3, 7, 15, 1] = \frac{3 + 1}{7 + \frac{1}{15 + \frac{1}{2}}}$

Now you’ll simplify this fraction and get that:

$\pi \approx \frac{335}{113} = 3.141592$

Also, don’t forget to celebrate March 14 (3/14), the international Pi Day!

The bridges of Konigsberg
The bridges of Konigsberg

Have you heard the true story of seven bridges of Konigsberg? The famous mathematician from the 18th century solved the enigma of crossing all bridges in one route. But, let’s start from scratch so we can get the bigger picture.

Konigsberg (now Kaliningrad) was a name of a city in Prussia, Germany back in 18-th century, until 1946. (In World War 2 it was occupied by Soviet Union and changed a name in Kaliningrad). It is located in on the coast of Baltic Sea. Though the whole city flows a river Pregel. This river flows in such way that in the middle of it lies an island and after passing the island, the river divides into two parts.

People build seven bridges so they could easily and quickly move around the city. Since people walked through there daily, they started to wonder if they can walk around the whole town, cross all the bridges only once and still walk over every bridge. People were quite intrigued by this question. Bridge looks like this:

 

river Pregel

The different areas are connected by seven bridges. We’ll mark them with a, b, c, d, e, f and g.

seven bridges

Let’s say there are four friends A, B, C and D living in different areas. They all wanted to know can they walk through the whole town, visit all areas and cross every bridge exactly one time and come back to their home.

konigsberg areas

This problem was solved by famous Swiss mathematician Leonhard Euler. He was very respected mathematician so people trusted him with this problem.

leonhard euler

Image credit: Wikimedia Commons by Jakob Emanuel Handmann

He approached this problems by imagining areas of land separated by the river into points connected with bridges or curved lines. This is how he represented this problem:

connect areas with bridges

Now that he drew this he saw that the walking through every bridge is equivalent to our drawing with a pencil without lifting it of of the paper.
From this exact problem the foundation of graph theory was developed. Euler also set few new definitions:
A network is a kind of diagram where we have one or more vertices connected with non-intersecting curves.
Vertex is called off if it has an odd number of arcs leading to it. If it has even number of arcs, it is called even.
An Euler path is a continuous path that uses every edge of a graph once and only once.

If a network has more than two odd vertices, it does not have an Euler path.

This is how Euler solved this problem. Since every vertex here has an odd number of edges, it does not have an Euler path.

Let’s try an example with some simpler stuff you know from the beginning you can draw in just one stroke.

simple examples

In these examples, you can start from any point you want, you could still finish this path.

more difficult shapes

The more complicated our shapes are, the more difficult for us is to see can we draw it without lifting the pencil of of the paper.

If a character can be drawn in one stroke, we say that it has an Euler path.

euler path

Image credit: Kjell Magne Fauske / edited by Martin Thoma

Now let’s think just like Euler thought. We should see what kind of a relationship do the vertices and edges have with the ability to draw Euler path. We’ll sort out vertices according to the number of edges that go through that vertex.

We can see, that in these, simple diagrams that we determined they have Euler path, all the vertices are even.

In general, all diagrams whose vertices are even has Euler path.

Let’s start with adding some odd vertices. Here we can see that we have four even vertices and two odd. Try to draw Euler path in this diagram:

odd vertices graph

We can also draw Euler path on every diagram that has exactly two odd vertices.

Let’s add even more odd vertices. Try to find Euler path yourself on the following diagrams.

different diagrams

From this we get to the following conclusion.

A network or a graph has an Euler path if the number of odd vertices is either zero or two.

This is how Euler solved this problem. Since four vertices here has an odd number of edges, it does not have an Euler path.

From this exact problem the foundation of graph theory was developed.

 

Introduction to Graphs

Every graph consists of the set of vertices and set of edges – connectors of vertices. If said otherwise, graph is final which means that we can count how many vertices and edges a certain graph has.

vertices edges and loop

We say that a graph is simple if every two vertices are connected only by one edge and there are no loops. Loops are edges that connect vertex with itself.

A graph that looks like a broken line that connects points in a line is called path.

definition of path

Closed path is called cycle.

definition of cycle

Complete graph is a graph in which every two vertices are connected by one edge.

complete graph

Graph is connected if every two vertices are connected by some path.

Connected path without cycle is called the tree.

the tree

Prime numbers
Prime numbers

What are prime numbers exactly? Prime numbers are numbers that can be divided, without a remainder, only by itself and by 1. For example, first odd number is number 2. 2 can only be divided by 1 and 2. Second number is 3, third 5 and so on… How can you determine whether the number is prime or not? First you divide it by 2 and see if you have a remainder, if you don’t, your number is not a prime. If there is a remainder that means that that number is not divisible by 2, and then you try it with 3 and continue until you get to a number you get when you divide your starting number by two.

For example number 7 is a prime number, because it can be divided only by one and 7, but 4 is not a prime number because, other than 1 and 4, can also be divided by 2.

Zero and one are not considered prime numbers. This is because, by the definition, prime numbers have exactly two divisors.

Sieve of Eratosthenes

What if you want to write down as many primes as you want? For the small primes, the most efficient way is the Sieve of Eratosthenes.

sieve of eratosthenes

Image credit: Wikimedia Commons user Ricordisamoa

For example, if you’d like to find all the primes less than or equal to 30, first list the numbers from 2 to 30.

numbers less or equal to 30

The first number is 2. 2 is a prime number. This means that we’ll leave them, and mark him blue. Cross out all of the multiples of the number 2, we’ll paint them gray.

first prime number on number line

Second one is number 3. This number is also a prime number, so we’ll again mark 3 with blue color, and cross out its multiples.

first two numbers

You continue this procedure. And in the end you’re left with:

up to 30

That means that the prime numbers from 1 to 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

By the Fundamental Theorem of Arithmetic every positive integer greater than one can be written uniquely as a product of primes, with the prime factors in the product written in order of decreasing size. Knowing this theorem, we know the most important use of primes. We can learn a lot about certain integer if we know its prime divisors. It’s just like when you have a big problem that you’d like to solve – it is in your best interest to divide it into smaller problems.

Euclidean algorithm
Euclidean algorithm

Euclid of Alexandria was a Greek mathematician. He was called the “Father of Geometry”. He wrote one of the most influential works in the history of mathematics – Elements.

Although Elements are mostly about geometry, Elements also include number theory. In this lesson we’ll give a little insight of this great mathematicians mind and his influence in the number theory.

euclid of alexandria

Image credit: Wikimedia Commons

The Euclidean Algorithm is a method for finding the greatest common divisor of two integers. Before showing the exact algorithm first we should set few rules and notations.

If a|b and a|c, we say that a is the common divisor of numbers b and c.

If at least one of numbers b and c is different from zero, then there exist only finitely many common divisors of b and c. The greatest of them is called the greatest common divisor of b and c. GCD is denoted as (b, c).

If we have two numbers whose greatest common divisor is one, we say that those two numbers are relatively prime. For example 40 and 13 are relatively prime. We denote this as:

$ (40, 13) = 1 \rightarrow 40$ and $ 13$ are relatively prime numbers
 

You also don’t necessarily have to observe only two numbers. More than two numbers can also be relatively prime. If we have numbers $ b_1, b_2, b_3, … ,bn$ whose only common divisor is 1, we say that those numbers are relatively prime. Also if every pair of those numbers is relatively prime we say that there are pairwise relatively prime.

Lemma 1. If $ b = aq + r$, $ 0 \le r < a$, $ a > 0$, then $(a, b) = (a, r)$.

Put in words, this lemma tells us that if we have a number b, that is divisible with number a with remainder r, then the greatest common divisor from a and b will be the same as the greatest common divisor of $ a$ and $ r$.

As an example we can take 6 and 4. We know that $ 6 = 4 * 1 + 2$. We can see now that $ (6, 4) = (6, 2) = 2$

Proof. Let’s say that $ (a, b) = d_1$, $ (a, r) = d_2$.

$ b = aq + r \rightarrow r = b – aq \rightarrow d_1$ | $ r$ .This means that d1 is the common divisor of a and r.

Since we got that $ d_1 | a$ and that $ d_2 | b$ we can conclude that $ d_1 \le d_2$.

$ b = aq + r \rightarrow d_2 | b$. This means that $ d_2$ is the common divisor of $ a$ and $ b$.

From here we got that $ d_2 | a$ and that $ d_2 | b$ which means that $ d_2 \le d_1$.

We now got that $ d_1 \le d_2$ and that $ d_2 \le d_1$ which can only mean that $ d_1 = d_2$.

 

Algorithm

Let’s assume that with repeated application of the remainder theorem we got the following string of equalities:

$ b = aq_1 + r_1$, $ 0 \le r_1 < a$
$ a = r_1q_2 + r_2$, $ 0 \le r_2 \le r1$

$ r1 = r_2q_3 + r_1$, $ 0 < r_3 < r_2$

$ r(n – 2) = r(n – 1)qn + rn$, $ 0 < rn < r(n – 1)$

$ r(n – 1) = rnqn + 0$

The procedure ends when we get remainder equal to zero. The procedure has to end in finally many steps.

Lemma 1 implies that the greatest common divisor of a and b is equal to rn because:

$ (a, b) = (a, r_1) = (r_1, r_2) = … = (r(n – 1), rn) = rn$

This means that $ (a, b)$ is equal to the last non trivial remainder in the upper procedure.

This process for finding GCD is called the Euclidean algorithm.

Let’s see how this algorithm works in practice.

Example Find GCD of $ 53357$ and $ 547$.

First we’ll divide $ 53358$ with $ 548$ and write it down as a sum of a product and remainder.

$ 53348 = 97 * 548 + 192$
$ 548 = 2 * 192 + 164$

$ 192 = 1 * 164 + 28$

$ 164 = 5 * 28 + 24$

$ 28 = 1 * 24 + 4$

$ 24 = 6 * 4 + 0$

Since 4 is the last non trivial remainder this means that $(53358, 548) = 4$

Koch snowflake
Koch snowflake

The Koch Snowflake was created by the Swedish mathematician Niels Fabian Helge von Koch. In one of his paper he used the Koch Snowflake to show that is possible to have figures that are continues everywhere but differentiable nowhere. Koch snowflake, curve or island is one of the earliest fractal curves that have been described.

koch snowflake

How can you generate Koch snowflake yourself? First draw an isosceles triangle. And divide its sides on three equal parts.

isosceles triangle with divided length

Now, construct isosceles triangles whose one side is one middle third.

construct isosceles triangle dots

Take a look at the character we got. Now you can easily locate six new triangles. Again, you divide its sides on three equal parts and construct new isosceles triangles.

many isosceles triangle continue

From here you just continue the procedure.

 

isosceles triangles creation neverend

snowflakes

koch cube

Gabriel’s horn
Gabriel’s horn

Gabriel’s horn or Torricelli’s trumpet is the surface of revolution of the function $ f(x) = \frac{1}{x}$ about the x – axis for $ x \ge 1$. What is this exactly? First draw your axes and draw function $\frac{1}{x}$ for $ x \ge 1$.

gabriel's horn graph

Now you imagine it rotating around x – axis.

rotating graph around x-axis

gabriels horn

Image credit to Fouriest Series

This figure has finite volume but infinite surface area.

How is this possible?

Well let’s try to find out what’s going on by calculation. This requires simple integral calculations. If we cut this horn into tiny regular slices we’ll always get circles with radius $\frac{1}{x}$ which means that volume of one little slice is equal to $\frac{1}{x^2} \pi$. And now that we know that we can find the volume of whole horn. Since the upper border of integral is infinity we have to use limit to get what we want.

volume formula

This means that the volume of this trumpet is equal to π cubic units.

To calculate surface we’ll use surface integrals of second kind.

surface formula

animation gabriel horn

What confused people for a long time is a paradox that using this knowledge of its surface and volume you could fill it with a bucket of paint but the same volume of paint would not be enough to paint its surface.

This paradox is resolved because the surface we generated has no thickness and you can’t find any real-life objects with no thickness which you could paint. Paint itself has finite thickness bounded by the radius of an atom.

Gabriel’s horn

Another thing you can think about is if you ever find real- life version of Gabriel’s horn or Gabriel’s trumpet could you play it?

Well no, since this trumpet is infinitely long, it will take you infinitely many years to come to its end, and even if you’re feeling especially adventurous and reach its end, it would be infinitely small so you couldn’t blow in it.

The Mandelbrot set
The Mandelbrot set

The Mandelbrot set is named after Benoit Mandelbrot. He is a Polish – born, French and American mathematician.

He is largely responsible for the present interest in fractal geometry.

From his dedicated study of fractals came the great Mandelbrot set.

Fractals are never – ending, infinitely complex repeating patterns. The Mandelbrot set is a collection of numbers that are different from the real numbers you see in your every day life. These all patterns are happening in the set of complex numbers.

benoit mandelbrot

Image credit: Wikimedia Commons user Rama

 

Every complex number has two parts- the real part and the imaginary part. Every complex number can be written as

$ z = a + \imath b$

Where the number i is the imaginary unit and $\imath_2 = – 1$.

imaginary unit i

This notation is very convenient because from this form we can easily find this numbers place in a complex plane.

So, how do we get to Mandelbrot set from here?

 

mandelbrot illustration

Let’s take some complex number b and let’s associate with it the following function.

$ f_b(z) = z^2 + b$

We are interested in the behavior of our function in zero and then in that result and then in the next result and so on.

Now we’re observing how this function will behave if we take $ b = 1$.

$f_1(0) = 0^2 + 1 = 1$

The function value in zero is equal to 1, so we’ll observe how it acts in 1 and continue the process with the following results.

$ f_1(1) = 1^2 + 1 = 2$
$ f_1(2) = 2^2 + 1 = 5$

$ f_1(5) = 5^2 + 1 = 26$

The Mandelbrot set observes what happens to the size of these numbers. This size is the distance of the given number in a complex plane and the origin.

size of number in mandelbrot set

Image credit: Wikimedia Commons user Wolfgangbeyer

There are two options. The first option is that the distance from zero of the sequence gets very, very large which means it blows up – the size of the number goes to the infinity. The second option is that the distance is bounded- never gets larger than two.

Let’s observe the process we did. We got numbers $ 1, 2, 5, 26$ which means they are getting larger and larger and will continue to do so. This means that we’re talking about the first option.

Now let’s take a look what happens when $ b = -1$. We’ll always be getting numbers zero or $ -1$. This means that this is the second case.

Mandelbrot set is the set of complex numbers in which case two occur.

So how can you draw all these patterns? You just start iterating zero under $ z_2 + c$, if it takes a long time to get bit, you give it one color, and if it gets big very quickly you give it other color. This is interesting because you can’t predict how your function will act if you move change c just a little bit.

mandelbrot set rainbow

Image credit: Wikimedia Commons user Geek3

If we take fixed value of c, and continue observing this polynomial as we observed ones in Mandelbrot set we’ll get something called the Filled Julia set.

Image credit: math.bu.edu

Image credit: math.bu.edu

This means that the Filled Julia set is the set of complex numbers z so that under iteration by fc the values don’t blow up.

Image credit: Wikimedia Commons user Adam Majewski

Image credit: Wikimedia Commons user Adam Majewski

The history of number zero
The history of number zero

People through history never really paid much attention to the number zero. They did understand the concept of nothing but they thought that zero had no special relevance in mathematics. As mathematics developed, so did its notation. People started seeing the relevance of zero only in notation; it was a number they used to easily see the difference between 1, 10, 100… Zero began being regarded as a real number in 9th century in India.

Zero we now know is probably the most complicated number we know of.

Why is this number giving us so many problems?

There are few things you absolutely cannot do; that are dividing with zero and have zero to the power zero. You probably heard this many times but have you ever wondered why is that true?

zero

What is the logic that people use when they say that something divided by zero is infinity?

Well, when you divide two real numbers, let’s say 16 divided by 4, you’d continuously subtract 4 from 16 until you get to zero.

1. $ 16 – 4 = 12$
2. $ 12 – 4 = 8$
3. $ 8 – 4 = 4$
4. $ 4 – 4 = 0$

We got to zero in 4 steps which means that $ 16 : 4 = 4$.

What if you want to divide 16 by zero? This means that you should repeatedly subtract zero from 16.

1. $ 16 – 0 = 16$
2. $ 16 – 0 = 16$
3. $ 16 – 0 = 16$
4. ….

This means that no matter how many steps we take, we’d never finish our division.

This leads us to thinking that $ 20 : 0 = \infty$. Why can’t we simply conclude this? If we observe dividing any other number with 0 we should, by the same process, conclude that the coefficient of any real number and zero is equal to $\infty$.

Now we have: $\frac{1}{0} = \infty = \frac{2}{0}$. From here 1 is equal to two which is obviously not true.

Let’s take a look at a graph of a function $ f(x) = \frac{1}{x}$.

graph 1/x

Now let’s get to $ 0^0$.

You already know that any number to the power of zero is equal to one.

$ a^0 = 1$ for every real number $ a$, except zero

And that zero to the power of any real number is equal to zero.

$ 0^a = 0$ for every real number $ a$, except zero

What happens if we observe these two statements together?

Let’s take a look at a graph of a function $ f(x) = x^x$. If we observe limits that go from the right and from the left to the zero, we get the same value – 1.

$\lim_{x \to 0} + x^x = 1 \lim_{x \to 0} – x^x = 1$

Does this mean that we can conclude that $ x^x = 1$? This is true only on the surface. There is a lot more than a simple real number line. But you also have complex numbers, so you have to include imaginary axis. Now there are a lot of different ways of approaching the origin. This is where the statement fails, because there are many different limits in complex plane. A generalization of this theorem is that any two bodies in R3 that do not extend to infinity and each containing a ball of arbitrary size can be dissected into each other.