More Puzzles

Loading...

Del curso dictado por University of California San Diego

What is a Proof?

176 calificaciones

University of California San Diego

What is a Proof?

176 calificaciones

Curso 1 de 5 en SpecializationIntroduction 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.

De la lección

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.

Magic Squares3:26

Narrowing the Search6:47

Multiplicative Magic Squares5:16

More Puzzles9:21

Integer Linear Combinations5:15

Paths In a Graph4:35

Conoce a los instructores

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

In this part we have several different unrelated puzzles,

each of them rather simple but

they show different sides of this search process.

Our first puzzle is to find a six digit number which

starts by 100 and is divisible by 9,127.

So this is our goal.

We should prove that there exists such a number.

And actually, it's not so many candidates.

So there are three, here we should have something starting from 000 up to 999.

So if you are lazy, you can just write a program, and

then the program will print you the list of all candidates.

So it's programmer's solution.

But if you are a mathematician or if you are lazy in a different way,

you do not want to program, then you can think of it.

Okay, let's try to find a pencil and paper solution.

Let's divide just the minimal possible candidate by this 9,000 something.

And then we get something, which is close, smaller than 11, but close to 11.

And so the most natural thing to try is to try 11.

And then indeed, you get a number, which is of the required for.

And by definition it's divisible by this number,

and the quotient is 11.

And you can see that the next one is too big.

So if you have something divisible by

9,127 the next one be 9,127 apart.

So it will be much bigger, this digit will be a 9.

So actually this problem has only one solution.

If you tried this programming, if you run this code,

you will see the solution, hopefully.

So this is easy.

Next problem is to find a three digit number that

produces a remainder 1 when divided by 2, 3, 4, 5, 6, 7.

In all cases, that should produce remainder 1.

And why we ask for a three digit number?

Of course, if we're just, otherwise, we can just use 1.

It has only one digit but otherwise it's okay,

because if 1 is divided by anything starting from 2, we get remainder 1.

So it doesn't work.

But how can we find this N?

Again, we can try a computer, but let's think of it more.

So N gives a remainder 1 when divided by something.

So what about N-1?

What will have remainder?

Of course, it will be 0, because if we delete this outstanding 1,

then the rest should be divisible by 2, 3, 4, 5 and 6.

And what is divisible by 2, 3, 4, 5, and 6?

It's common multiple, it's called.

And you see that this number works, 2, 3, 4., 5, and 6.

So you can find here all the numbers, and actually, this is the minimal possible.

So in number theory you will see that this is the minimum possible number.

And all others are multiple of this.

And this number is 400.

So now recall that it's N-1 and

so for N we have 421.

And you can check.

Then if you divided by all this, 2, 3, 4, 5, 6, 7, you get remainder 1.

What about others, other three digit numbers.

Yeah, so we have already said that you can take any multiple of this number.

So the next one will be 840.

So if N- 1 is 840, then you get the next one here in this computation.

And the next one is too big.

So that actually took into [INAUDIBLE] for this solution.

But we need only one, if we want to prove that there exists something,

it's one example is enough.

Good, now next, our next puzzle.

We want to find a perfect square, which means that the square of a natural number

that starts with this strange digit.

It's actually first digits of pi, but doesn't matter.

We can take any sequence here.

So we want to find an integer,

which such that n squared starts with a given sequence.

We're going to prove that such a number exists.

How do we prove it?

And then is a very important observation, it's enough to find a decimal fraction.

So if we have some decimal fraction,

and there is a decimal point in something here.

And then if you multiply this fraction by 10 this means

that we move the decimal point one position to the right.

And in the n square, if we multiply x by 10,

then the square is multiplied by 100.

So in the square we have moved two positions to the right.

But, anyway, it's just the position changed and the digits are the same.

So if we move the decimal point we do not change anything in the sequence of digits.

Now, everything is very easy,

we can just calculate the square root using a pocket calculator.

It's useful, but still if you don't have it you can do it by hand.

So you get this.

And then you can try to move this point somewhere and see what happens.

So let's see.

Just we take all these things and

we see that we get almost what we wanted.

But we have something very close to this but just a bit smaller.

So we need to take something bigger.

Let's try something, probably we don't need so many digits.

So here is what we can do.

So 177.243 square is it starts in the right way.

But this is not an integer but we know what to do.

We just move this thing three positions and

this thing moves six positions and we are done.

And here is the answer.

So we have an integer, n and

n squared starts with what we wanted.

Good, here is just the next one.

It's also a key.

But there is more.

Imagine we want to find two perfect squares starting with this

number which are different.

Prove that there is another number n, and n has a different first digit and

still n square also starts with 31415.

So we need to prove another thing, another n.

What can we do?

Actually, we can do the same.

Take the square root but in a different way.

So can you see what to do?

Yeah, here it is.

So let's put decimal point in a different place.

So let's put the decimal point here.

Then the square root is different.

Actually, we divide, more or less, by square root of 10.

But the first digits is now completely different.

But we can use the same trick.

We can try something a bit bigger than this.

So it will be natural to try 5605, but

we see that it's too big because here we have 6 instead of 5.

So we need more digits, actually.

We can try this, replace 2 by 1.

And then, with this, we get what we wanted.

So here is the desired sequence.

And now we have two perfect squares,

two n which start with different digits and still their squares are okay,

and this is from the previous slide and this is what we get now.

Problem solved.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play