узнаете>
Компьютерные науки>
Алгоритмы>
Mathematical Thinking in Computer Science.>
Multiplicative Magic Squares

Loading...

Multiplicative Magic Squares

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.

Mathematical Thinking in Computer Science

Калифорнийский университет в Сан-Диего

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

Просмотреть программу курса

Получаемые навыки

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Преподаватели

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

Текст видео

Our next trick is that we can

transform the known solution into solutions for new problems.

And this will be illustrated by a multiplicative magic squares.

I will explain what it is.

Just instead of sums we have products.

So in magic square we have sums for rows, columns, and diagonals the same.

And now we want products to be the same.

And, of course, now we cannot hope to use all the sequential numbers,

because can you see why it's impossible?

It's easy.

So for example, look at seven.

Seven is somewhere in the square.

I don't know where.

And then it appears in some products.

But in some other products, it doesn't appear.

So we have no other numbers can give seven in combination.

So these two products will be different and no hope.

We forget about this requirement, we just require to have different integers.

But they can be arbitrary.

So, now the question, is there a multiplicative magic square?

What do you think?

Which looks rather strange, it's just as your brief formula 2 in

the power of x + y is 2 to the power x times 2 to the power of y.

And mathematician will say that exponentiation transforms addition into

multiplication.

It's a homomorphism of an additive group into a multiplicative group, but

anyway we have this simple formula.

Can you see what are the connections, how it can be used to transform the editive

square into a multiplicative square?

So this is the general slogan.

And here is the trick.

So instead of each number is replaced by two power of this number.

So if we multiply for example this three, then according to this rule,

we need to just add the exponents.

And the sum of the exponent is here and so all the products are here.

The sum of 15 and so here the product is 2 to the 15.

And we get a multiplicative magic square.

Good.

But the numbers are rather big, the maximal one is 512.

And can you find smaller one?

There is very simple observation.

If you want a number less than 300, what can you do?

Actually, you see that the minimal one is 2.

So we don't have zero here, so

we have all this number start here from 2, 4, 8 and so on.

And so we can just divide all the numbers by two and

instead of 2 to the 9th, we have 2 to the 8th, which is only 256.

So this is the trick.

But it's not the best thing we can do, let me show you how we can do better.

So, we can even get them less than 40 and

this is again used for exponentiation but in a more clever way.

So let's start with a very strange magic square.

It's major in terms of the sum of all these three, but of course,

the same numbers that appear many times, so it's not major.

But still we can transform it into a multiplicative magic square but

again, not major but the sum of the products.

So why does it help?

Let's do the same thing for a bit different square, we're just rotate it.

And here we have the base 2 and here we have base 3.

So we get 2 bad

multiplicative magic squares, but the numbers are not different.

So what do we do?

We can multiply them.

So actually, if we just have 2 times 1 is 2,

or 4 times 9 is 36.

So in each cell we place the product of the numbers in the corresponding cell.

So why is bites good?

Because if we now take the product for

example here, actually, this is product of things here and here.

And so here, we have always 27, here we also have 8.

So in every line we have 27 times 8.

And so it's just a number, so

we have the same number in all the lines, that's what we wanted.

And additionally, you see that all the numbers are different.

So it's multiplicative of magic square and all its number are less than 40.

That's what we promised and we achieved this in this final way.

Рекомендуемые видео

О Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

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

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

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

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