Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени и сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

Multiplicative Magic Squares

Loading...

Mathematical Thinking in Computer Science

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

4.4 (оценок: 515) | Зарегистрировано учащихся: 28K

Курс 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

Рецензии

4.4 (оценок: 515)

5 stars
334 ratings
4 stars
112 ratings
3 stars
44 ratings
2 stars
12 ratings
1 star
13 ratings

KL

Nov 29, 2018

The course is excellent and most stuff is being taught in a nicely presented way. The main disappointment is 15-puzzle, because it's too difficult to understand without proper material.

DG

Jun 30, 2018

Love the quality of thought that goes into each lesson. The professors speak with acute clarity and really demonstrate and empathy for the student to truly understand the topics!

Из урока

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

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

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 делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

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

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

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

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы