Magic Squares

Loading...

En provenance du cours de University of California San Diego

Mathematical Thinking in Computer Science

262 notes

University of California San Diego

Mathematical Thinking in Computer Science

262 notes

Cours 1 sur 5 dans 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.

À partir de la leçon

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

Rencontrer les enseignants

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

We have said that one example is enough to prove an existential statement but,

of course, we need to find this example.

And it's kind of difficult think sometimes,

so we will show with some examples and

show some tricks that can be used.

Okay, usually when a teacher doesn't know what to say,

how to solve the problem and there is no advice, teacher suggests be creative.

Try whatever you can and meditate and so on.

So, this is we start with a nice picture, it's engraving of Albrecht Duerer.

It's an old engraving called Melancholia,

maybe now it will be called the mis deadline.

But at that time it was Melancholia.

And here is some part of this picture, you can see in this picture that is here,

that is on the wall that is magic square.

So what is this magic square?

It's just a table with numbers.

And what is magic here is that the sum is the same for

all four rows or four columns and all two diagonals.

You can check with the square.

You can, okay, 13 plus, this is 21.

33 and 34, so the sum is 34 for every line.

And in general, a magic square is just a placement of 16.

Not necessarily 16 but if you have n times n, you need n squared.

But the first initial numbers into a square.

And this is the condition that the same sum in all the columns,

in all the rows and in two diagonals.

This is the definition.

And now the question is, how to find these magic squares?

And we know that Duerer somehow proved that a major square of size 4 exists.

Actually, if you are more careful, you could see that some letters,

some numbers on Duerer's engravings are a bit strange.

And even you can see that he changed some numbers.

So even if it seems that there exist a version of this print

runs which have another number.

But anyway, you can reconstruct this number using the magic square condition.

So Duerer proof is correct.

But if we look for a magic square of size 2 then it doesn't exist for

a very simple reason.

Here is the reason.

Look, if we know that in magic square all the sums should be the same.

So a + b should be equal to a + c.

But then it means that b = c and

we are not allowed to place the same number twice.

So 2 times 2 magic square doesn't exist.

And now, natural question is what about size 3?

Can we make a size 3 matrix square of a 1, 2, 3, 4 up to 9?

So, what do you think?

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play