Quảng trường ma thuật

Free Time Remaining For Today: 4:59

Quảng trường ma thuật

Tổng số người chơi: 84109
Tổng số trận thắng: 61876

Learning Objectives

Introduction

Definition:

A 'Magic Square' is a square of 3×3 numbers where the sums of all numbers in a row, in a column and in both diagonals are all the same.

Typical question:
What number has to replace the question mark to complete the diagram as a Magic Square?
```
	15  *  35
	50  *   ?
	25  *   *
			
```
This is easy to solve. The sum in each line is 15+50+25=90. From the diagonal, it follows that the middle value is 90−25−35=30 and from the 2^nd row: 50+30+?=90 ⇒ ? = 10.

How would you solve a Magic Square with fewer given numbers, like the one below?
```
	?   *   *
	*   *  47
	*  63   *
			
```
What is the standard way of solving this problem? One could introduce variables
```
	P   Q   R
	U   V  47
	X  63   Z
	
```
and formulate all conditions as equations such as
```
	P+Q+R = U+V+47 = X+63+Z = P+U+X = Q+V+63 = R+47+Z = P+V+Z = R+V+X,
	
```
and solve this system of equations by eliminating all unknowns except P to get one equation for P and solve that. These are 7 conditions for 7 unknowns.

In the following we want to solve Magic Square problems without having to solve such systems of equations.

General Relations and Examples

Let us look for simple relations between the numbers in the Magic Square.

Because a square has many symmetry operations (4 rotations + mirroring and their combinations), let us define quantities which do not change under such symmetry operations. For example, if our square is
```
	P  Q  R
	U  M  W
	X  Y  Z
	
```
then these quantities that do not change under rotations and mirrorings are
```
	C = sum of corner values		(= P+R+X+Z)
	E = sum of middle edge values		(= Q+U+W+Y)
	M = middle value		(= M)
	S = sum in each line		(= P+Q+R = P+U+X = X+M+P = ...) .
			
```
What relations can be derived for these quantities?
- It is not difficult to find the following relations between C, E, M, S by eliminating variables P, Q, R, U, W, X, Y, Z from the above equations.
  
  Lemma 1:
```
	2C + E = 4S        (1)
	M + C + E = 3S     (2)
	C + 2M = 2S        (3)
	C − M = S          (4)
	3M = S             (5)
						
```
  Proof.
  
  The above relations result as follows:
  
  (1) from summing the 4 edges
  (2) from summing all numbers
  (3) from summing the 2 diagonals
  (4) from (1) − (2)
  (5) from (3) − (4)
  
  ▢
  
  Verify (1), (2) and (3) by replacing C, E and S by their sums.
  
  How can they help? For example, relation (5) is enough to solve the following examples.
  
  Example:
```
	3  2  7
	*  ?  *
	*  *  *
						
```
  Solution
  
  Since all 3 numbers in the 1^st row are given, we know that S = 3+2+7 = 12. Thus by (5), ? = 12/3 = 4.
  
  Example:
```
	11  *  4
	*   6  *
	*   ?  *
						
```
  Solution
  
  Let Q = the middle value of 1^st row. Then by (5), 11+Q+4 = 3×6 ⇒ Q = 18−4−11 = 3.
  
  Thus, ? = 18−6−3 = 9.
  
  Example:
```
	*  *  5
	*  9  *
	?  *  *
						
```
  Solution
  
  By (5), ?+9+5 = 3×9 = 27 ⇒ ? = 27−9−5 = 13.
  
  Example:
```
	*  *  5
	*  ?  *
	9  *  *
						
```
  Solution
  
  By (5), 5+?+9 = 3×? ⇒ 14 = 2×? ⇒ ? = 14/2 = 7.
  
  Example: The following puzzle contains the numbers 7,...,15. What is the value of P?
```
	P   *   *
	*   *   *
	*   *  14
						
```
  Solution
  
  Without knowing that this Magic Square is filled with the whole numbers from 7 to 15 inclusive, the one given number would not have been enough. But with this information and by (5),
  
  3S = (7+15) + (8+14) + (9+13) + (10+12) + 11 = 4×2 + 11 = 99 ⇒ S = 33 ⇒ M = 11 ⇒ 14 + 11 + P = 33 ⇒ P = 8.
  
  How about the problem below?
```
	?   *   *
	*   *  47
	*  63   *
						
```
  Here we need more relations.

A General Theory

What are the simplest Magic Squares you can think of?
Our strategy will be to start with the simplest possible Magic Square
```
	0 0 0
	0 0 0        (6)
	0 0 0
	
```
and find 'deformations', i.e. methods to change the Magic Square into another Magic Square. The first such deformation is to add the same value 1 to all fields:
```
	1 1 1
	1 1 1        (7)
	1 1 1
				
```
Which is also a Magic Square. What other generalizing deformations are there?
Before looking for more possible deformations, we first use a handy definition.

Definition:
A set of mathematical objects is closed under a certain operation if executing that operation on any objects in the set results in another object from the set. For example:
- The set of integers is closed under addition, i.e. adding any two integers together results in an integer.
- The set of real numbers is not closed under division (but is closed under non-zero division, i.e. division by numbers that are not 0).
Theorem 1:
The set of all Magic Squares is closed under addition and scalar multiplication (scalar multiplication defined as multiplying each entry in a magic square by a real number).

Want to try proving this theorem?
Proof.
1. Because addition is commutative: If 2 Magic Squares
```
	a11 a12 a13
	a21 a22 a23        (8)
	a31 a32 a33
	
```
  and
```
	b11 b12 b13
	b21 b22 b23        (9)
	b31 b32 b33
	
```
  are added together:
```
	a11+b11  a12+b12  a13+b13
	a21+b21  a22+b22  a23+b23        (10)
	a31+b31  a32+b32  a33+b33
	
```
  then this is also a Magic Square because, for example, the first two rows of (10) have equal sums.
```
	a11+b11 + a21+b21 + a31+b31
	= a11+a21+a31 + b11+b21+b31      (commutativity of addition)
	= a12+a22+a32 + b12+b22+b32      (because (8) and (9) are Magic Squares)
	= a12+b12 + a22+b22 + a32+b32    (which we wanted to show)
							
```
  Similarly, one can show the equality of sums of other lines of (10).
2. Because of the distributive law, if (8):
```
	a11 a12 a13
	a21 a22 a23
	a31 a32 a33
	
```
  is a Magic Square then
```
	b×a11  b×a12  b×a13
	b×a21  b×a22  b×a23
	b×a31  b×a32  b×a33
	
```
  is a Magic Square too because, for example, if
```
	a11 +   a12 +   a13  =    a21 +   a22 +   a23  then	b×(a11 +   a12 +   a13) = b×(a21 +   a22 +   a23)  and	b×a11 + b×a12 + b×a13  =  b×a21 + b×a22 + b×a23 .
							
```
  ▢
Corollary 1.1:
Applying this theorem means that subtracting the middle value from all fields of a Magic Square (i.e. subtracting M times Magic Square (7)) gives a Magic Square with middle value 0.

Let us go back to our problem of finding other deformations. The next one should keep the centre value as 0 in order to not interfere with the deformation −M×(7).
Let us change the upper-left to 1 (the smallest possible value):
```
	1  *  *
	*  0  *
	*  *  *
			
```
Because M=0, then S must also be zero, i.e.
```
	1  *  *
	*  0  *
	*  * −1
			
```
The upper-right corner can stay 0 but then all other changes are fixed:
```
	+1  −1   0
	−1   0  +1        (11)
	 0  +1  −1
			
```
This is a Magic Square itself.

We get another deformation of a Magic Square through a symmetry transformation. This means that any mirroring or rotation of a Magic Square also gives a Magic Square. Mirroring on the main diagonal does not give a new Magic Square, but rotation does give a new Magic Square:
```
	 0  −1  +1
	+1   0  −1        (12)
	−1  +1   0
			
```
We now apply theorem 1 three times.
Given a Magic Square, first we subtract the square a22×(7) to make the middle value zero. We then subtract from the new square the square a11×(11) so that the upper-left corner becomes zero. The middle stays zero because a11×(11) has middle value 0. Then a square a13×(12) is subtracted so that the upper-right corner becomes zero. In doing that, the middle value and the upper-left corner stay zero because these fields are zero in a13×(12). So, that means that one can subtract from any Magic Square suitable multiples of squares (7), (11), and (12) to obtain a Magic Square of the form
```
	0 * 0
	* 0 *
	* * *
	
```
with an S value of zero (because the middle value is zero). This easily shows that the whole Magic Square is
```
	0 0 0
	0 0 0
	0 0 0
			
```
But, that means each Magic Square can be written as a sum of multiples of squares M×(7) + A×(11) + B×(12).

Theorem 2:
Each Magic Square can be written in the form
```
	M+A     M−A−B   M  +B
	M−A+B     M     M+A−B        (13)
	M  −B   M+A+B   M−A  .
			
```
Proof

As shown above, each Magic Square can be reduced to the square consisting of only zeros by subtracting multiples of (7), (11) and (12).

▢

In more mathematical language one would say that:
The Magic Squares (7), (11) and (12) are a complete set of generators for all Magic Squares.
Now that we know the essence of all Magic Squares, is this all that useful in solving Magic Square problems? With rule (5): 3M = S we found a simple and useful relation between a single component of the square and S. Here are two more.

Lemma 2:
Each corner value is the average of the 2 values adjacent to the diagonally opposite corner.

Proof

For example, in the upper-left corner in (13), M+A = ((M+A+B)+(M+A−B))/2, and likewise for the other 3 corners.

▢

This simple rule instantly solves the earlier problem
```
	?  *  *
	*  * 47
	* 63  *
	
```
by reducing it to ? = (63+47)/2 = 55. Here is another relation:

Lemma 3:
For each line through the middle of the square, the middle value M is the average of the other two values in the line.

Proof

By inspection of (13).

▢

Corollary 2.1:
If nothing but a single number is given, then no other number can be determined.

Corollary 2.2:
If 2 numbers are given and lemmas 2 or 3 apply, then a 3^rd number is fixed.

Corollary 2.3:
If 3 numbers are given which are not related through lemmas 2 or 3 then these 3 numbers determine the whole Magic Square.

Corollary 2.4:
All Magic Square problems are easily solved by computing M, A, and B from the numbers that are given, and plugging the values for M, A, and B into (13) to find all other numbers.

Is the Hardest Difficulty Level Really That Hard?

When we look at Magic Square (13) we see that there are 3 independent parameters A, B, and M. If only 2 are given (and for the hardest level the centre value = M is never given) then M can be chosen freely and the other 2 given values would determine A and B.

Which value of M makes completing a Magic Square the most easy?
- By choosing M=0 as the centre value, all lines through the centre can be completed simply by switching the sign of the opposite number to get a sum of 0. For the remaining numbers, one only has to do two differences/sums of two numbers.
  
  Example:
```
	*   80    *
	*    *   56
	*    *    *
						
```
  Solution
  First we can apply lemma 2 to get value in the lower-left corner the average (80+56)/2 = 136/2 = 68:
```
	 *   80    *
	 *    *   56
	68    *    *
	
```
  Then, after adding 0 in the middle and mirroring numbers in the middle by switching signs:
```
	  *    80   −68
	−56     0    56
	 68   −80     *
	
```
  Finally since all sums are 0, the upper-left corner must be 68−80 = −12. Therefore, the simplest solution of this example is:
```
	−12    80   −68
	−56     0    56
	 68   −80    12
							
```
Saving time
- If we know all numbers in one line and 2 numbers in a line that crosses it, then we can speed up computation slightly, especially when numbers are larger.
  
  Example:
```
	P  *  *
	U  ?  W
	X  *  *
	
```
  where P, U, X, W are known and we want to find ?.
  We know that P+U+X = U+?+W and thus P+X = ?+W. Therefore, ? = P+X−W.
  What one can do is to check which of P, X are closest to W, say, P and then compute ? = X+(P−W). This is much quicker to compute than S = P+U+X, ? = S−U−W, especially if P−W is small. You could practise this in the Muntjac level.

Summary

We learned a general approach for solving a difficult mathematical problem (here finding the most general Magic Square) which has symmetries (here rotations and mirror symmetries) and a special solution (here the Magic Square (11)) which does not have all these symmetries ((11) is not rotationally symmetric) such that when one applies the symmetry operation, a new special solution is generated (here (11) → rotation → (12)).
Furthermore, we saw how in problems for linear objects the general solution can be obtained by adding multiples of a complete set of special solutions (here each Magic Square can be written as a sum of multiples of (7), (11) and (12)).

Now you can quickly win the Magic Square game... fair and square!

Theo dõi cập nhật sắp tới