|
Challenge: Create a 3 by 3 grid using the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9 once only, so that each row, each column and each diagonal sums to 15. Such a grid is called a magic square. Here is a failed attempt:
Note that the rows sum to 11, 17 and 17 ... . This square is not magic. Why set the sums to 15? This is because the sum of the integers 1 through 9 is 45, so dividing by 3 (e.g. for the three rows) gives 15. Let's solve this generally. Start with a generic square, letting x1, x2, x3, ... , x9 stand in for the 9 integers.
Thus, the three rows sum to 15:
x4 + x5 + x6 = 15 x7 + x8 + x9 = 15 the three columns sum to 15:
x2 + x5 + x8 = 15 x3 + x6 + x9 = 15 and the two diagonals sum to 15:
x7 + x5 + x3 = 15 We have eight equations in nine variables. This is written as a system where the coefficients are shown as 0 or 1, just to show the overall structure a little more:
0x1 + 0x2 + 0x3 + 1x4 + 1x5 + 1x6 + 0x7 + 0x8 + 0x9 = 15 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 + 1x7 + 1x8 + 1x9 = 15 1x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 15 0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 + 1x8 + 0x9 = 15 0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 1x9 = 15 1x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 1x9 = 15 0x1 + 0x2 + 1x3 + 0x4 + 1x5 + 0x6 + 1x7 + 0x8 + 0x9 = 15 The equivalent system in reduced row echelon format is
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 10 0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 − 1x8 − 1x9 = -5 0x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 + 0x7 − 1x8 − 2x9 = -10 0x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 5 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 + 1x8 + 2x9 = 20 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 + 1x7 + 1x8 + 1x9 = 15 Look carefully: there is one less row in the row-echelon form. This suggests that the eight restrictions are dependent, and that only seven are needed. In other words, once seven of the requirements are met, the eighth will follow automatically. Note that x8 and x9 can be treated as parameter variables. Once values are chosen for x8 and x9, the values for x1 ... x7 are then determined. We have the following equations:
x2 = 10 − x8 x3 = -5 + x8 + x9 x4 = -10 + x8 + 2x9 x5 = 5 x6 = 20 − x8 − 2x9 x7 = 15 − x8 − x9 We create a table that shows all 81 possible pairs of x8 and x9 that could be selected to generate a square of values.
We now shade those possibilities that are not permissible (in the sense that a choice for x8 and x9 would lead to a contradiction). For example, the fifth equation above declares that x5 = 5. Thus, neither x8 nor x9 can be 5. These cells are shaded:
Also, x8 and x9 must be different integers, so x8 ≠ x9. These cells are shaded:
Since x8 and x9 lie in the bottom row, their sum cannot equal 10, since that would force x7 to be 5, which contradicts the fact that only x5 can be 5. Thus, we shade those cells in which x8 + x9 = 10:
Also, x8 and x9 must be chosen so that its sum does not meet nor exceed 15, since that would force x7 to be 0 or a negative quantity. We now shade the cells in which x8 + x9 > 15. Also, the sum of x8 and x9 cannot be less than or equal to 5 since that would force x7 to be 10 or greater. We shade the cells in which x8 + x9 < 5:
The expressions for elements x4 and x6 also provide more restrictions on x8 and x9. Since x4 = -10 + x8 + 2x9, and since x4 > 1, then -10 + x8 + 2x9 > 1, so that x8 + 2x9 > 11. Meanwhile, x6 = 20 − x8 − 2x9, and since x6 > 1, then we have 20 − x8 − 2x9 > 1, or x8 + 2x9 < 19. The cells that violate these restrictions are then shaded:
So far, we have been able to delete 63 possibilities. We can now try some of the remaining possible values for x8 and x9 and see what happens. For example, if x8 = 4 and x9 = 7, then this forces x7 = 4, which violates the rule that all entries must be different. The following is a list of initial values of x8 and x9 that cause a contradiction, causing two of the entries to take on the same value:
x8 = 7, x9 = 4: Causes x7 = 4. x8 = 9, x9 = 3: Causes x7 = 3. x8 = 6, x9 = 3: Causes x7 = 6. x8 = 3, x9 = 6: Causes x7 = 6. x8 = 8, x9 = 3: Causes x3 = 6 and x6 = 6. x8 = 8, x9 = 4: Causes x1 = 6 and x4 = 6. x8 = 1, x9 = 7: Causes x1 = 3 and x3 = 3. x8 = 2, x9 = 6: Causes x1 = 4 and x4 = 4. x8 = 2, x9 = 7: Causes x4 = 6 and x7 = 6. These contradictions are shaded:
This leaves eight possible parameter choices, marked by a 🌝, that generate a magic square. Let's try x8 = 7, x9 = 2. Thus, x1 = 8, x2 = 3, x3 = 4, x4 = 1, x5 = 5, x6 = 9 and x7 = 6. The resulting square is
Each row, column and diagonal sum to 15. Try it. This is a magic square. The fact that there are eight possible magic squares should not be surprising. Once we have found one square, then seven more can be generated by rotating the numbers a quarter-turn clockwise, a half-turn, and a three-quarters turn, or reflecting vertically or horizontally, or reflecting across the two diagonals. Thus, using the above square, the other squares are:
Note that the values of x8 and x9 in the bottom row correspond to an unshaded cell in the table, thus indicating these will form a magic square.
Prepared by Scott Surgent. Report errors or questions to surgent@asu.edu. (Oct 30, 2019, updated Feb 16, 2021)
|