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:

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

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.

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

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:

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.

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

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.

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:

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.

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.

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**.

Closed path is called **cycle**.

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

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

Connected path without cycle is called the **tree**.

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.

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.

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.

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.

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

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.

**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.

**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:

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:

$ 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:

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.

$ 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$

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.

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

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

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.

From here you just continue the procedure.

**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$.

Now you imagine it rotating around x – axis.

This figure you got 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.

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

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

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.

Second thing you can think about is if you ever find real- life version of 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** 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.

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

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

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?

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

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$.

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(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.

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.

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**.

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.

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?

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}$.

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

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

And that zero to the power of any real number is equal to 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.

Zeno of Elea was a Greek philosopher and mathematician, whom Aristotle called the inventor of dialect. He is especially known for his paradoxes that contributed to the development of logic.

The first paradox we’ll explain goes like this:

A runner wants to run a certain distance, for example 500 meters. But if he wants to reach that distance he must first reach the first 250 meters, and to reach that he must first run 125 meters. Since space is infinitely divisible, we can repeat that forever. Thus, the runner has to reach an infinite number of midpoints in a finite time which is impossible. This leads us to thinking that anyone who wants to move from one point to another must meet these requirements, and so motion is impossible, and what we perceive as motion is an illusion.

One assumption in this paradox is that space is infinitely divisible. Another is that it is impossible to reach infinite number of points in a finite time. But why time couldn’t be infinitely divided to?

$ Distance = speed * time$

$ Time = distance / speed$

If you divide an infinitesimal distance by a finite speed, you get an infinitesimal time.

This means that time can be infinitely divided; that’s why infinitesimal distance can be travelled in an infinitesimal time, and the times add up to a finite time in the same way that the infinite number of distances adds up to a finite distance. This is where this paradox fails.

## Achilles and the tortoise

Let’s say that, for some reason, Achilles and the tortoise are racing. The tortoise, if of course a lot slower that the Achilles and for that reason she has a 100 meters head start.

Achilles sprints 100 meters and catches up to a tortoise. By that time tortoise also moved, but only 10 meters.

Now Achilles sprints another 10 meters to catch up to a tortoise. But now, tortoise moved another meter. And this keeps happening. The paradox is that the Achilles can never catch the tortoise which is nonsense because he obviously has to.

So how can an infinite process end?

If we have the distance of 2 meters and we’re constantly dividing it by two we get:

If we divide whole sum by 2:

This is a well behaved sum. At infinity it is equal to a real number exactly. But when we’re talking about infinity, we know that it doesn’t have the last step. So how can something without a last step be completed? That is the paradox. But even though this is an infinite process, it can be completed. This is the same problem as drawing a length of an irrational number. How can you draw accurately segment whose length has infinitely many decimals? But for example, if you have a right triangle with length of both of its legs 1, its hypotenuse will be $\sqrt{2}$, which is an irrational number.

Back in the 1924, two mathematicians, Stefan Banach and Alfred Tarski stated that it is actually possible to decompose a ball into six pieces which can be reassembled by rigid motions to form two balls of the same size as the original.

Later on, number of pieces was reduced to five by Julia Robinson, which is also the minimal number of pieces required for this theorem.

You may thing we’re talking nonsense and this can’t be true, but according to Banach Tarski theorem it is completely possible.

What if you broke a glass ball? It is clear that you couldn’t just rearrange broken pieces and get two new balls identical to the original one.

Banach Tarski theorem works because it is not a physical sphere we’re talking about, but rather a mathematical sphere- an infinite collection of points.

Now let’s take a look at a set of natural numbers from one to infinity.

$ O = {1, 3, 5, 7…}$

At the first look you might say that there are half as many numbers in sets that contain only even or odd numbers as there are in the original set of natural numbers since we only took every other number, but every even number is made by multiplying every number of N by two, and every odd number is made by multiplying every number of N by two and subtracting 1. Therefore, sets of even and odd numbers are both infinitely large.

Let’s thing about what we just did. We created two infinitely large sets from one. This is why it is possible to break one sphere into two spheres identical to the original.

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.

**The Monty Hall problem** is a probability puzzle based on the American television game show whose host was Monty Hall.

Imagine you’re having a really great day and you’re feeling very lucky so you decide to go on the show. When you get there you see three doors.

These are the rules of the game: Behind two of these three doors are goats and behind the last one 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.

Now the host offers you 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.

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. Now it’s 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.