Subset without x and 2x

Loading...

From the course by University of California San Diego

What is a Proof?

173 оценки

University of California San Diego

What is a Proof?

173 оценки

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

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

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

Our final optimality puzzle is,

it deals with numbers once again and it is

slightly more complicated than the previous ones.

So in this case we are given numbers from 1 to 50,

integers from 1 to 50 and our goal is to take as many of them as possible

with the constraint that we are not allowed to take x and 2x, simultaneously.

Okay so the question is what is the maximum number of

such integers that we can take to satisfy this constraint?

Okay, let's try to reason about this problem as usual.

So first of all the simplest constraint says that we can

not take 1 and 2 simultaneously so there is a conflict between 1 and 2.

But this is not the only complex that 2 participates in.

The other one is between 2 and 4.

You cannot take 2 and 4 simultaneously and you can actually extend this further.

So we extend this through a so-called chain which consists of 1,

2, 4, 8, 16 and 32, right?

So from this chain we now said we are not

allowed to take any two neighbors in this chain.

So this is just one of the chains.

Another such chain is for example it starts from 3.

So it is 3 then 6 then 12 then 24 and then 48, right?

For this chain we also know that from it we can not take any two neighbors

and in general you can partition all the ground set into such chains.

Each set chain starts with its own odd number.

So it is probably instructive to visualise it like this.

So in this case the first chain starts with the number 1

and we've seen it through 1, 2, 4, 8, 16, 32.

So this is on my first chain.

The next one starts with the next odd number,

3, 6, 12, 24, 58.

So it is already shorter.

The next one starts at 5 then 10 then 20 then 48.

It is already of size 4 and so on.

So when we reach the number 27 all the chains already are of the same,

of the length 1, I'm sorry.

So for all the chains starting with 27, for example 29, 31, 32,

all these chains consist of just a single integer number.

Okay then what it claims here is that the chains are independent.

So what this means so first of all each number appears in exactly one chain.

To actually finds this chain just take a number,

for example, I don't know,

46 and start dividing by 2.

So if you divide 46 by 2 you get 23 which means that this is,

that we know the beginning of your chain.

So each chain has

a unique odd starting number which means that all of them do not intersect.

And what is also important is that there are no conflicts between different chains.

So if you take any number like eight,

and if you take any other number from any other cell,

for example 28, we know for sure that these are not numbers of the form x and 2x.

All numbers of the form x and 2x,

they lie in the same chain.

Okay. This is already great because this means that we reduced

our problem of taking as many numbers from our ground set up,

all the numbers from 1 to 50 to the following problem.

We have chains, they are independent so our goal

is just for each chain to select the possible,

the maximum possible number.

Right. But this problem is much easier.

So if you have a chain,

for example this one and you know that you can not take any two consecutive numbers,

any two neighbors from this chain and you would like to maximize the number of

elements that you take,then of course the optimal strategy is to

start from the very beginning and to take every second number,

for example, this chain is going to be as follows: 1, 4 and 16.

For the next chain it is going to be for this one 3, 12 and 48.

For the next one it is going to be 5 and 20.

Clearly, for the chain starting with 5 so 5,

10, 20 and 40 you can not take more than two elements, right?

So this actually shows us that the optimal strategy of

taking as many numbers as possible is, in any chain to take every second number.

So this gives us this a solution which consists of the following highlighted numbers.

So we first take all the odd numbers,

there are 25 of them,

then we take also these six numbers and these two numbers.

So it is 25 plus 6 plus 2 which is 33.

So first of all it is a solution,

we see that it is indeed a solution so that there are

no two numbers that are of the form x and 2x.

And why it is optimal?

Well, just because we partition the ground set in the independent pieces and for

each such piece we prove that we've taken as many elements from these pieces,

from this particular piece as possible.

So this finally proves that 33 is indeed an optimal solution in this case.

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

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

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

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

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

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