Introduction, Lines and Triangles Problem

Loading...

Do curso por University of California San Diego

Mathematical Thinking in Computer Science

455 classificações

University of California San Diego

Mathematical Thinking in Computer Science

455 classificações

Curso 1 de 5 em Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

Na lição

Recursion and Induction

We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to make convincing arguments for arbitrarily large and complex problems by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher's problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.

Introduction, Lines and Triangles Problem10:16

Lines and Triangles: Proof by Induction5:59

Connecting Points12:59

Odd Points: Proof by Induction5:29

Sums of Numbers8:52

Bernoulli's Inequality8:01

Coins Problem9:45

Cutting a Triangle8:40

Flawed Induction Proofs9:28

Alternating Sum9:09

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

[MUSIC]

Hi, I'm Michael Levin and

in this lesson we're going to study mathematical induction.

It is a very powerful proof method.

It is very similar to this example with falling dominos.

You know that if we put many, many dominos on the floor, so

that the second domino is right in front of the first one, and

the third one is right in front of the second one, and so on.

And then we push the first domino, it will fall, and

it will push the second one in front of it.

And that domino will also fall and it will push the third one and so on and

then all the dominos will actually fall.

And we can check that for maybe 1 domino, 2 dominos, maybe 5, 100, or 1,000.

But how to prove that for any number of dominos.

It seems obvious from your practical life experience.

But actually to prove that strictly that even a million dominos will fall,

we will have to think about what happens in the general case.

So we know that if we push the first domino it will fall.

And also what we know is that if some domino on position k falls,

it will push forward the k plus first domino and that one will also fall.

And from that, we can conclude that if we push the first one, then any domino

in the row even one thousands and even the one millionth, all of them will fall.

And mathematical induction is a proof method

which is based on the same principle.

And there are a lot of problems, hard problems, which can be proven only

using these kinds of methods like mathematical induction.

And many computer science algorithms are actually proven using induction.

And we'll start with an example of lines and triangles.

We will consider the following problem.

Several straight lines are drawn on a plane,

and in a sense they cut this infinite plane into pieces.

And you can see an example on the picture.

We have four lines there and we have many,

many pieces between segments of those lines.

Some of those pieces are infinite ,and some of those pieces are finite.

And we'll require that each line intersects with every other line.

So there are no parallel lines.

And also all the intersection points are different so

that no three lines intersect in the same point.

And what we want to prove is that there must be at least one triangle piece.

In this picture, we actually see two triangle pieces.

The one below and the one above.

And we state that, if all the conditions are met, if every two lines intersect and

there are no points where at least three lines intersect,

then there always will be at least one triangle piece.

So how to prove this statement.

Well we have the following idea, as soon as there are three lines,

we know that those three lines cannot intersect in one point.

And from that it immediately follows that if there are exactly three lines,

we'll have a triangular piece formed by those three lines.

And then, if we have more lines,

then we can actually imagine that we have first only three lines.

Some of those lines we have, some three first lines and

we can chose them arbitrarily.

And then we are going to add more lines one by one.

And when we add more lines one by one, every time either

the same triangle piece that already existed before adding that line remains,

if that line doesn't touch this piece and

it remains intact, or a new triangle appears.

And this is the general idea.

So we start with three lines and we immediately get a triangle.

And then when we add more line,

either it doesn't touch this piece and the triangle remains or a new one appears.

Let's see how that happens.

So when we have just three lines, in the general position they form a triangle

because each of them intersects another one, and we have three

points of intersection, and we require that those three points are different.

And so those three points,

together with those lines form a triangle, which is highlighted with orange here.

So, there is a bad case where there is no triangle, but in this case

we have this common point of intersection of three lines which is what we forbid.

So, this cannot actually happen

in our problem statement because we forbid three lines intersecting the same point.

So this can't happen.

And so if we'll have exactly three lines, we will have a triangular piece indeed.

What happens when we add one more line?

So now we have just three lines and we are adding one more, so

it will be the fourth line.

And as we have three lines, we have this highlighted triangle.

Now with for example such fourth line.

And we see that it intersects the triangle.

But let's see how does it intersect the triangle.

So it goes somewhere from the left.

And then it goes and goes and

then at some point it intersects one of the sides of the triangle.

And then it is going inside of the highlighted triangle.

And it goes and goes and then it intersects the triangle again, and

goes out of the triangle.

And then it goes to the right to infinity, and this is what always happens.

Line goes until it intersects some side of the triangle.

And note that it cannot intersect the side exactly in the vertex,

because that would be a vertex where three lines intersect,

the two sides of the triangle and the new line.

So that can happen.

So the new line always intersects some side of triangle

somewhere in the middle and then it goes inside the triangle.

And we know that in the end when it goes

to the right at some point it will be outside of the triangle.

So it has to intersect a triangle twice, not just once but twice.

So if a line intersects a triangle,

it intersects it in two points and it intersects two of the sides.

So if we take these two points and

the vertex where these two sides intersect themselves, those form a triangle.

And this is actually the new triangle that will appear

when we add a new line that intersects the current triangle.

So, every time we add a new line that intersects the current triangle,

a new triangle is formed.

What happens if we add another line, the fifth line?

In this case, this fifth line doesn't touch

the existing triangle which exists after four lines.

So when it doesn't touch,

we can just say that this same triangular piece remains intact?

And so when we're going from four lines to five lines, the same triangle exists.

Now, let's consider the general case.

In the general case there can be many, many lines.

And of course sometimes we can spot the triangle with a naked eye.

But if we had many, many more lines, like thousands of them,

it will be very hard to find a triangle by our naked eye.

And we need to somehow prove for ourselves that for

any possible positions of those lines which satisfy requirements,

there will be actually a triangle.

So in general, we are going to do the following.

We assume that we have already added some number of lines,

maybe 3, maybe 4, maybe 100.

And up to this point, some triangle piece existed.

And we're going to add new lines one by one.

And we can get actually any picture with many lines.

We can get by adding them one by one in some order.

And the order doesn't matter to us.

So we just select some order, we add first three lines, and

then we add one more line at each step.

So we assume that at some point when we were at, for example, 100 lines,

there was some triangle.

And here is this triangle highlighted with orange.

And we are focusing exactly on that triangle.

We forget about everything to the side from this triangle.

Only know that no lines intersect this triangle because this is a whole piece.

And we know that there are a lot of lines going here and there on the plane.

But we don't need them to make our proof.

So there is a triangle, and now we're going to add one more line.

And if that line intersects this triangle, then we already know that it will

intersect two sides of the triangle and a new triangle will be formed like this.

So this happens not only when we have three lines, it happens whenever we

already have a triangle and it may with 3 lines or 100 lines or 1 million lines.

That doesn't matter.

Still, if the new line intersects our current triangle, a new triangle appears.

Otherwise, if we have a triangle and

the new line doesn't touch it, then this triangle just remains.

So in the general case it happens the same way as in the case of just three lines.

[MUSIC]

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play