Subset without x and 100-x

Loading...

Из курса от партнера University of California San Diego

Mathematical Thinking in Computer Science

455 оценки

University of California San Diego

Mathematical Thinking in Computer Science

455 оценки

Курс 1 из 5 — 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.

Из урока

How to Find an Example?

How can we be certain that an object with certain requirements exist? One way to show this, is to go through all objects and check whether at least one of them meets the requirements. However, in many cases, the search space is enormous. A computer may help, but some reasoning that narrows the search space is important both for computer search and for "bare hands" work. In this module, we will learn various techniques for showing that an object exists and that an object is optimal among all other objects. As usual, we'll practice solving many interactive puzzles. We'll show also some computer programs that help us to construct an example.

Subset without x and 100-x4:10

Rooks on a Chessboard2:39

Knights on a Chessboard5:09

Bishops on a Chessboard2:42

Subset without x and 2x6:24

Познакомьтесь с преподавателями

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

Our next puzzle is the following.

We're given two-digit numbers that has integers 10,

11, 12 and so on, 99.

And we would like to take

as many of them as possible subject to the following constraint.

We are not allowed to take simultaneously two numbers X and Y,

if X + Y = 100.

But then otherwise, we are not allowed to take simultaneously x and 100 - X.

So the question is what is the maximum possible number of

two-digit integers that we can take under the given constraint?

So let's start solving this problem.

So first of all, if we take the smallest possible number, which is 10,

then it means that we cannot take 90 simultaneously together with 10, right?

And vice versa.

If we take 90 then we cannot take 10.

So in a sense 10 and 90 form a pair

such that from this pair we can take at most one number.

For exactly the same reason,

the numbers 11 and 89 also form the same pair.

From this pair we can take at most one number.

So continuing in the same question,

we discover 40 such pairs starting from 10 and 90 and going to 49 and 51.

Also there are ten like free numbers remaining.

So these are numbers without any pairs.

One of them is 50 because 50 is a pair for itself.

And the other nine numbers are 91,

92 and so on, 99.

For all these numbers there are no two-digit number that can be added to them to get 100.

So this tells us already that we

cannot take more than 50 numbers under the given constraint.

Why is that? Well, because we have

10 free numbers and all the remaining 80 numbers are paired.

And from each pair we can take at most one number.

So in total we call we can take

at most 10 plus 40 numbers which gives us 50 numbers, right?

So this is actually the universal part.

We've just proved that any solution cannot be of size more than 50.

At the same time,

it is not so difficult to contract the solution of size 50.

Just take all the numbers which are at least 50.

There are 50 such numbers and it is clear that it is a solution.

If you take any two numbers from the set,

the sum is going to be greater than 100. Okay?

So it was not very difficult.

But just to follow the same patterns that we discussed in the previous video,

let's wrap it as a formal theorem and let's prove it following the same pattern.

So the statement is the following:

the maximum number of two-digit numbers that one can take subject to

the constraint that there are no two numbers whose sum is equal to 100 is equal to 50.

So the first part is as usual,

universal, we need to show a solution.

And the solution is for example the numbers starting from 50.

It is not difficult to check that it is indeed a solution.

On the other hand, let's show the universal part that any solution has size at most 50.

To show this now that we have 40 pairs and we have 90 numbers in total

and we have among these 90 numbers

there are 40 pairs and from each pair we can pick at most one number.

So in total from each pair we need to exclude at least one number.

So in total we have at most 90 minus 40 which is equal to 50 numbers.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play