Nobody Can Win All The Time: Nonexisting Examples

Loading...

From the course by University of California San Diego

Mathematical Thinking in Computer Science

197 ratings

University of California San Diego

Mathematical Thinking in Computer Science

197 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

Making Convincing Arguments

Why some arguments are convincing and some are not? What makes an argument convincing? How to establish your argument in such a way that there is no possible room for doubt left? How mathematical thinking can help with this? In this week we will start digging into these questions. We will see how a small remark or a simple observation can turn a seemingly non-trivial question into an obvious one. Through various examples we will observe a parallel between constructing a rigorous argument and mathematical reasoning.

One Example is Enough3:26

Splitting an Octagon1:24

Making Fun in Real Life: Tensegrities10:25

Know Your Rights5:49

Nobody Can Win All The Time: Nonexisting Examples8:27

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

This is a warning,

that if somebody asks you for an example,

maybe such an example doesn't exist.

So you should be prepared for the cases when the search doesn't help.

Let's look at the problem of splitting weights.

So imagine that you and your friend are preparing for a hike,

and you have identical backpacks,

and you want to be completely fair.

You have many items to bring for the hike,

but then you want to split them into groups of exactly the same weight.

For example, if you have three things of weights one,

two, three, then of course you put three in

one side and one into the other side and you are done.

So you can write like this.

And also, it's convenient to represent in another way,

so you can write,

instead of asking to split into two groups,

you can ask, "What kind of signs should be here?

Plus or minuses?"

So the total sum becomes zero.

So plus terms are equal to minus terms.

For our special case,

it's just plus one,

plus two, minus three.

Okay. This is the problem,

and the parameter of this problem is just the set of weights.

Let's try to consider some other more interesting example.

So imagine we have weights one, two, three, four, five,

seven, and we want to split them into two groups of equal weight.

But how do we do this?

The simplest question which you should ask yourself is,

"Just what is this equal weight?"

So we compute the total weight and we see that it's 22.

1, 3, 6, 10,

15, 22. Yeah, that's correct.

And then, if we want to split 22 into two groups,

each group should be 11,

and it's very easy to see a group of 11.

And after you find one group of 11,

the rest of course should be also 11,

and indeed, one plus two plus three is six plus 11.

So, you are done.

You'll find a group of weight 11 and then you know weight and the rest is also 11,

so everything is okay.

But not always, you are so lucky.

There can be cases when the task is impossible.

So imagine the weights are one, two, three,

four, five, six, not seven, but six.

And then, if you think,

"What is the total weight?"

It's 21, and maybe you already see that you cannot split this into

two equal groups for a very simple reason because 21 is not divisible by two.

And if you have two groups,

then they should be,

each group should have some integer weight,

so 21 will be a multiple of 2. So, not possible.

Now, just think of other case.

Imagine we have not one, two, three, four, five,

six, but 2, 4,

6, 8, 10 and 12.

Is it possible or not? Do you see?

Actually it's not possible, but do you see why?

Because it's actually the same problem.

We just take the same weights,

but twice bigger, so essentially we just change the unit,

we make a unit of weight twice more.

But you can also say that the total sum is not 21, but 42 now,

and 42 is divisible by two but the quotient is 21,

and it's odd, and you cannot get it by summing the even numbers.

Okay. Anyway. So this is just the bad news, now of course,

it's the special case there is nothing bad,

just the condition that we asked for something which doesn't exist.

But the bad news are coming,

and the bad news can be illustrated by the next example.

So imagine we have some other case, 1, 2,

3, 4, 5, 17,

not 7, but 17.

And if you count the total weight now,

it's 10 units bigger, so it's 32.

So it now is divisible by two, everything looks okay.

But, of course, if we divide it by two,

we get 16, and we have one piece of 17,

so 17 is too big.

If we put 17 somewhere,

there is not enough weights to put in the other side,

so this is another obstacle.

And the bad news really is that obstacles can be of different types,

and the problem is that there is no complete list of obstacles.

Of course, it would be nice to have some rule.

So if you want to split things into two group of equal weight,

you should check whether the sum is even,

whether there are not two big pieces, blah, blah, blah, blah,

and if some conditions are met,

then it's possible and you know how.

It's not the case.

For this problem, nobody know the complete list of

obstacles and nobody knows the way to check whether this is possible or not.

And maybe you heard the name NP-complete problem.

Actually, in scientific language,

it's translated into normal one as some infeasible problem.

So if you have, say, 10,000 numbers,

which is for computer 10,000 is something rather small.

But for this problem,

if you have 10,000 numbers,

then there is no way to check whether they can be split into two groups or not.

This is even worse.

There is no weights, it's a simplification.

We don't know how to do this.

And unfortunately, we cannot prove that such an algorithm doesn't exist.

You maybe heard about this P and NP problem,

this is exactly this question,

so whether there is an algorithm which solves this splitting weights problem.

So you see that you are now rather close to

the boundary of modern computer science knowledge,

or better to say that the boundary is very close to us,

because actually the problem is that people do know much about NP-complete problems.

They tried it hard,

but no real success.

So what should you understand from this part of our course?

First, the structure of the proof depends on what you want to prove, of course.

Second, that if the statement is existential,

then you need only one example to prove it.

And also, you have no obligation to disclose how you find an example.

So if you cheated and asked the example from your friend,

probably it's morally not okay,

but from the mathematical proof point of view,

it's completely valid proof.

It's just a valid proof obtained by bad tools.

But still it's a proof.

And you should be prepared,

if you look for something,

this something may not exist at all and then you should not

spend the rest of your life looking for a solution.

It may not exist, and even maybe in some cases,

you can prove this,

but in some case,

unfortunately, it's very difficult.

So, maybe you're still in bad shape,

you don't know whether it exists or not,

this is also a possibility.

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