Cutting a Triangle

Loading...

From the course by University of California San Diego

Mathematical Thinking in Computer Science

283 ratings

University of California San Diego

Mathematical Thinking in Computer Science

283 ratings

Course 1 of 5 in the 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.

From the lesson

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

Meet the Instructors

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

[SOUND] Hi, in this video we're going to consider a problem

about cutting a triangle into smaller triangles.

But first, some definitions.

An obtuse triangle is depicted on the image above,

and ABC is an obtuse triangle.

And it is defined as a triangle which has at least one angle which is

bigger than 90 degrees.

And acute triangle is depicted on the picture below.

And it is defined as a triangle where there are no

angles which are 90 degrees or bigger.

So all the angles are below 90 degrees.

And the problem we are going to solve is,

is it possible to cut an obtuse triangle into several acute triangles?

So, we're going to try to prove this theorem.

That if an obtuse triangle is cut into several triangular pieces,

then at least one of the pieces is obtuse.

So basically,

we'll say that this is impossible to cut an obtuse triangle into acute triangles.

And this theorem actually sounds very similar to the first problem where solving

with mathematical induction about cutting a plane by lines.

And let us try to prove this in a similar way using Mathematical Induction.

So something in the lines that if we get just one piece, then it is obtuse, and

if we cut into more pieces, then at least one more of them will be also obtuse.

And so an obtuse triangle will always stay, the same way as it was with

a triangular piece, among the pieces into each lines, cut the plane.

So let's prove this theorem by induction.

And the induction base is very simple, n = 1.

So the initial triangle is obtuse and we cut it into only one piece,

so this piece has to coincide with this initial triangle.

And so it is also obtuse piece, so it is true that if

we cut a obtuse triangle into one piece, then there is an obtuse piece.

Now, we need to prove the induction step from n to n + 1.

And by assumption of induction, if there are n pieces,

there is an obtuse piece among them.

And now, if we cut this piece into two triangles,

at least one of them stays obtuse.

And to see that, you should look at the pictures below.

So to cut a triangle in two,

we need to connect its vertex with some points on the opposite side.

And depending on which node we connect,

we get either the left picture when we draw the line

from the angle C which is obtuse, to some point D on the opposite side.

Then the triangle CBD is also obtuse, and actually one of the triangles CDA and

CDB always will be obtuse because some of the angles CDA and CDB is 180 degrees,

and so at least one of the triangles won't be acute or obtuse.

And actually, the same happens on the right picture with obtuse triangle EFG.

When we draw a line from note E,

which is acute angle to point H on the opposite side.

Actually, nothing really changes because some of angles EHG and

EHF is 180 degrees and so at least one of them is not acute.

So we see that when we cut an obtuse triangle in two,

one of the parts is also obtuse.

And so when we move from n pieces to n + 1, obtuse piece has to stay.

Because either we don't even touch the obtuse piece that we have among n pieces,

or if we cut this particular piece to try and make it not obtuse and

then try to cut it into acute triangles,

we see that at least one of the bars will be again obtuse.

So it seems it's not be possible to avoid this obtuse piece.

And we have fully induction based.

And we have proven the induction steps, so we have proven the theorem that it is not

possible to cut an obtuse triangle into acute triangles.

And now, I actually have to come out and tell you that I lied to you.

This proof is actually wrong.

Can you spot what was wrong in this proof?

Well first, let's see this example.

So, we have initially this big triangle, which is an obtuse triangle.

And you see that it is cut into seven pieces, and those pieces are triangles.

And actually, all of the pieces are acute.

So we have just proven the theorem that states that this is impossible,

that we cannot cut a triangle into acute pieces if the initial triangle is obtuse.

But on the other hand, we have this example, which proves that it is

possible to cut this particular obtuse triangle into acute pieces.

So what was wrong?

The example is obviously correct, so

probably something was wrong with the proof, and it is often the case.

We have to be very careful when making the proofs to

not make some incorrect logic in our proof.

So let's look at what was wrong.

Actually, the induction step assumed that if we cut a triangle into several

triangular pieces, we can do it by several steps of cutting a triangular

piece into more triangular pieces, and actually into two triangles.

So we proved by induction that if we cut our initial obtuse

triangle in a particular way, when every time we take a piece and

cut it by a line into two triangular pieces,

then it is impossible to cut the obtuse triangle into acute triangles.

But this is not the only was to cut the triangle.

We don't have to always cut the triangle into exactly two pieces which

are triangles, we can cut it into more pieces.

And in this previous example that I've shown you, you see that there is

no such thing that we cut our initial obtuse triangle into two pieces.

We cut it into seven pieces at once.

And so this is the case that our proof didn't consider.

And this is where we're wrong.

So the induction step itself is correct and the induction base itself is correct.

But the assumption is incorrect, that the only way we can

cut an obtuse triangle into triangles is to cut one by one.

This was true when we're cutting the plane with lines,

that we can add lines one by one and we can get the same picture on that.

And it was also true for segments connecting the points that we can

add segments one by one, and then we will get the final picture.

But it is not true that, for any way of cutting a triangle into pieces,

into triangular pieces, we can simulate this by cutting first a triangle

into two pieces and one of those two pieces into two, and so on, and so on.

This is just not true because there are different ways to cut the triangle.

And so this is an example where mathematical induction actually fails.

Well, actually this is not the fault of any induction, it is faultless.

It is our fault that we applied it in a wrong way.

And this shows that you have to be very careful.

This is a very powerful method that you have to handle it with care,

not to make a mistake.

And in the next video, I will show you even more flawed

induction proofs which will show you what not to do.

And it is equally important when you have a powerful method in your hands,

not only to understand how to apply it, but

also how to not apply it when it is not applicable.

[SOUND]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play