Semi-Magic Squares

The squares of a 3 × 3 3 \times 3 grid are filled with non-negative integers such that the sum of each row and the sum of each column is 7. 7. How many different ways can the squares be filled?

Details and assumptions

The numbers in each grid square does not need to be distinct.

Rotations and reflections are distinct arrangements.


The answer is 666.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Derek Khu
May 20, 2014

We let the 2 × 2 2 \times 2 grid of squares at the top-left be represented by ( a b c d ) \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} .

These four integers would fully determine the entire 3 × 3 3 \times 3 grid according to the rule that the sum of each row and the sum of each column is 7 7 . Concretely, the entire grid is ( a b 7 a b c d 7 c d 7 a c 7 b d a + b + c + d 7 ) \begin{pmatrix} a & b & 7-a-b \\ c & d & 7-c-d \\ 7-a-c & 7-b-d & a+b+c+d-7 \end{pmatrix} .

We want all the entries to be non-negative integers, so this happens if and only if the following conditions are all fulfilled:

(1) a , b , c , d a, b, c, d are non-negative integers

(2) 7 a b 0 a + b 7 7-a-b \geq 0 \Leftrightarrow a+b \leq 7

(3) 7 c d 0 c + d 7 7-c-d \geq 0 \Leftrightarrow c+d \leq 7

(4) 7 a c 0 a + c 7 7-a-c \geq 0 \Leftrightarrow a+c \leq 7

(5) 7 b d 0 b + d 7 7-b-d \geq 0 \Leftrightarrow b+d \leq 7

(6) a + b + c + d 7 0 a + b + c + d 7 a+b+c+d-7 \geq 0 \Leftrightarrow a+b+c+d \geq 7

We shall first count the number of possible tuples ( a , b , c , d ) (a,b,c,d) which satisfy the first five conditions, and then subtract from that the number of these tuples which violate the last condition.

We let max ( a , d ) = x \max(a,d) = x . Then 0 x 7 0 \leq x \leq 7 . For each x x , there are 2 x + 1 2x+1 ways to choose a a and d d , because we can let either a a or d d be x x and let the other be any value from 0 0 to x x (of course, we must not double-count the case where a = d = x a=d=x ). Subject to conditions (2) and (5), there are then 8 x 8-x ways to choose b b from 0 0 to 7 x 7-x . Similarly, using conditions (3) and (4), there are 8 x 8-x ways to choose c c . Thus, the number of tuples whch satisfy the first five conditions is given by x = 0 7 ( 2 x + 1 ) ( 8 x ) 2 \displaystyle \sum_{x=0}^7 (2x+1)(8-x)^2 . We can manually calculate this to be 876 876 .

We now need to count the number of these 876 876 tuples which violate the last condition. These tuples would satisfy a + b + c + d 6 a+b+c+d \leq 6 , with a , b , c , d a,b,c,d being non-negative integers. The number of these is the same as the number of non-negative integer solutions to a + b + c + d + e = 6 a+b+c+d+e=6 , which is ( 10 4 ) = 210 {10 \choose 4} = 210 .

So the answer we want is 876 210 = 666 876 - 210 = 666 .

This question involved counting the number of solutions to various linear equations. When we have a single equation, we can use the Stars and Bars technique to count these, however when we have multiple equations, the counting becomes more difficult. Choosing appropriate variables makes the calculations easier for this question, and students who did not choose their variables carefully had difficulty counting the correct number of solutions.

Calvin Lin Staff - 7 years ago
Thomas Beuman
May 20, 2014

First note that four entries can be chosen freely:

( a b x ) ( c d x ) ( x x x ) (a \quad b \quad x) \\ (c \quad d \quad x) \\ (x \quad x \quad x)

You can set a a , b b , c c and d d after which all the x x 's are fixed. The condition that all those x x 's are non-negative translates to:

a + b , a + c , d + b , d + c 7 a + b + c + d 7 a+b, a+c, d+b, d+c \leq 7 \qquad a+b+c+d \geq 7

We first count all the solutions that meet the first (four) inequalities, and then subtract all the ones that break the last. Note that if the last condition is not met, then the first (four) are automatically fulfilled.

If a a and d d are given, then the number of values of b b and c c that meet the first four constraints is ( 8 m a x ( a , d ) ) 2 (8-max(a,d))^2 . Summing over all possible values of a a and d d gives 876 876 (calculation omitted).

The number of combinations of a a , b b , c c and d d that add up to 6 or less is ( 10 4 ) = 210 \binom{10}{4} = 210 . The requested number is thus 876 210 = 666 876-210 = 666 .

More generally, if we replace 7 with n n , the total is

1 8 ( n + 1 ) ( n + 2 ) ( n 2 + 3 n + 4 ) \frac18 (n+1)(n+2)(n^2+3n+4)

Douglas Zare
May 20, 2014

There are ( 7 + 3 1 2 ) = 36 {7+3-1 \choose 2} = 36 possible rows of 3 nonnegative numbers which add up to 7:

(7,0,0) (x3, 3 symmetric versions) (6,1,0) (x6) (5,2,0) (x6) (5,1,1) (x3) (4,3,0) (x6) (4,2,1) (x6) (3,3,1) (x3) (3,2,2) (x3)

For each pair of a first row and a second row, there is a unique nonnegative third row which completes the semimagic square so that the column sums are 7. However, this third row may have negative entries if the corrresponding entries of the first and second rows add up to more than 7. So, we want to count pairs of rows so that the sum is at most 7 in each entry. Here are the counts of the compatible ways to arrange the first and second rows by their sorted versions:

(7,0,0): (7,0,0)x2, (6,1,0)x2 (5,2,0)x2 (5,1,1)x0 (4,3,0)x2 (4,2,1)x0 (3,3,1)x0 (3,2,2)x0 Total: 8 x 3 = 24

700 610 520 511 430 421 331 322 total 700 2 2 2 0 2 0 0 0 24 610 1 4 2 2 2 2 1 0 84 520 1 2 4 2 2 4 1 2 108 511 0 4 4 2 2 4 1 2 57 430 1 2 2 1 4 4 3 3 120 421 0 2 4 2 4 4 3 3 132 331 0 2 2 1 6 6 3 3 69 322 0 0 4 2 6 6 3 3 84 \begin{matrix} & 700 & 610 & 520 & 511 & 430 & 421 & 331 & 322 & \text{total}\\ 700 & 2 & 2 & 2 & 0 & 2 & 0 & 0 & 0 & 24 \\ 610 & 1 & 4 & 2 & 2 & 2 & 2 & 1 & 0 & 84 \\ 520 & 1 & 2 & 4 & 2 & 2 & 4 & 1 & 2 & 108 \\ 511 & 0 & 4 & 4 & 2 & 2 & 4 & 1 & 2 & 57 \\ 430 & 1 & 2 & 2 & 1 & 4 & 4 & 3 & 3 & 120 \\ 421 & 0 & 2 & 4 & 2 & 4 & 4 & 3 & 3 & 132 \\ 331 & 0 & 2 & 2 & 1 & 6 & 6 & 3 & 3 & 69 \\ 322 & 0 & 0 & 4 & 2 & 6 & 6 & 3 & 3 & 84 \\ \end{matrix}

The total is 24 + 84 + 108 + 57 + 120 + 132 + 69 + 72 = 666 24+84+108+57+120+132+69+72=666 .

Calvin Lin Staff
May 13, 2014

We will show by induction that the number of ways of filling the 3 × 3 3 \times 3 grid such that the sum of the numbers is n n is a n = ( n + 1 ) ( n + 2 ) ( n 2 + 3 n + 4 ) 8 . a_n = \frac{(n+1)(n+2)(n^2 + 3n + 4)}{8}.

When n = 0 n = 0 we have a n = 1 a_n = 1 and when n = 1 , n = 1, we have a n = 6. a_n = 6. The grid of 0 0 s is the only way to have a sum of 0, and when we have a sum of 1 1 , we have 3 3 choices for which column the 1 1 in the first row is in, 2 2 choices for the second row, and 1 1 for the third row, giving a total of 3 × 2 × 1 = 6 3 \times 2 \times 1 = 6 choices.

For the inductive step, we notice that if a grid has row and column sum k , k, then either we can subtract 1 1 from each entry along the main diagonal to get a grid where the sums are all k 1 , k-1, or at least one entry along the diagonal is 0. 0. When all entries along the diagonal are 0 , 0, we see that the grid must be:

0 a k a k a 0 a a k a 0 \begin{array}{|c|c|c|} \hline 0 & a & k - a\\ \hline k-a & 0 & a\\ \hline a & k-a & 0\\ \hline \end{array}

There are k + 1 k + 1 choices for a , a, since it can be any number from 0 0 to k . k. This gives a total of k + 1 k+1 fillings.

When there are exactly 2 entries along the diagonal, we may assume WLOG that they are the corner entries. Then our grid must look like this:

0 a k a b k a b a k b b 0 \begin{array}{|c|c|c|} \hline 0 & a & k - a\\ \hline b & k - a - b & a\\ \hline k-b & b & 0\\ \hline \end{array}

We must have a 0 , b 0 a \geq 0, b \geq 0 and a + b < k . a + b < k. This last inequality is strict, since the middle entry cannot be 0, as we assumed exactly 2 of the diaonal entries are 0. 0. When a + b = p a + b = p there are p + 1 p+1 possible choices for a a and b , b, and p k 1 , p \leq k-1, so there are 1 + 2 + + k = k ( k + 1 ) / 2 1 + 2 + \cdots + k = k(k+1)/2 fillings that meet this criteria. Since there are 3 symmetric choices for which diagonal entries are 0 0 there are 3 k ( k + 1 ) / 2 3k(k+1)/2 fillings.

If there is a single 0 along the diagonal, then our grid looks like:

0 a k a b k a b + c a c k b b c c \begin{array}{|c|c|c|} \hline 0 & a & k - a\\ \hline b & k - a - b+ c & a - c\\ \hline k-b & b - c& c\\ \hline \end{array}

We must have c 1 , a c , b c c \geq 1, a \geq c, b \geq c and k + c > a + b . k + c > a + b. For a particular value of c , c, say c = q , c = q, we look at the possible values for the sum a + b . a + b. This sum is at least 2 q 2q and at most k + q 1. k + q - 1. Moreover, when the sum is 2 q 1 + r , 2q -1 + r, there are r r choices for a a and b b that will give that sum. This gives a total of 1 + 2 + + k q = ( k q ) ( k q + 1 ) / 2 1 + 2 + \cdots + k - q = (k-q)(k-q+1)/2 choices when c = q . c = q. Summing over all possible values of q q gives q = 1 k 1 ( k q ) ( k q + 1 ) / 2 = k ( k 1 ) ( k + 1 ) / 6 \sum_{q = 1}^{k-1} (k-q)(k-q+1)/2 = k(k-1)(k+1)/6

Since there are 3 choices for which position the 0 0 is in, this gives k ( k 1 ) ( k + 1 ) / 2 k(k-1)(k+1)/2 fillings of the grid.

Thus, we have that the number of fillings for the grid of size k k is

a k 1 + k + 1 + 3 k ( k + 1 ) 2 + k ( k 1 ) ( k + 1 ) 2 = k ( k + 1 ) ( k 2 + k + 2 ) 8 + 8 k + 8 8 + 12 k ( k + 1 ) 8 + 4 k ( k 1 ) ( k + 1 ) 8 = k 4 + 2 k 3 + 3 k 2 + 2 k 8 + 8 k + 8 8 + 12 k 2 + 12 k 8 + 4 k 3 4 k 8 = k 4 + 6 k 3 + 15 k 2 + 18 k + 8 8 = ( k + 1 ) ( k + 2 ) ( k 2 + 3 k + 4 ) 8 = [ k + 1 ] [ ( k + 1 ) + 1 ] [ ( k + 1 ) 2 + ( k + 1 ) + 2 ] 8 = a k . \begin{array}{cl} a_{k-1} + k+1 & + \frac{3k(k+1)}{2} + \frac{k(k-1)(k+1)}{2} \\ & = \frac{k(k+1)(k^2 + k + 2)}{8} + \frac{8k+8}{8} + \frac{12k(k+1)}{8} + \frac{4k(k-1)(k+1)}{8}\\ &= \frac{k^4 + 2k^3 + 3k^2 + 2k}{8}+ \frac{8k+8}{8} + \frac{12k^2+12k}{8} + \frac{4k^3-4k}{8}\\ & = \frac{k^4 + 6k^3 + 15k^2 + 18k + 8}{8}\\ & = \frac{(k+1)(k+2)(k^2 + 3k + 4)}{8}\\ & = \frac{[k+1][(k+1)+1][(k+1)^2 + (k+1) + 2]}{8}\\ &= a_{k}. \end{array}

This proves our induction hypothesis. When n = 7 , n = 7, we get that there are ( m + 1 ) ( m + 2 ) ( m 2 + 3 m + 4 ) 8 = 666 \frac{(m+1)(m+2)(m^2 + 3m + 4)}{8} = 666 tilings of the grid.

Aww man. I though it was zero for 3 by 3's because they had to total 15. D:

Finn Hulse - 7 years ago

Log in to reply

That's true for magic squares, which have the additional constraints:
1) We are using distinct integers from 1 to 9.
2) The diagonals also sum to the same value.

As always, check the conditions of the theorem before applying.

Calvin Lin Staff - 7 years ago
Mihai Nipomici
May 20, 2014

Note the square like a chess board 1,2,3 and a,b,c. Now put 4 numbers (x, y ,z ,t) in the corners 1a, 1c, 3a, 3c. This 4 point define the other 5 because sums are 7.In cells 2a, 1b, 3b, 2c we have numbers (7-x-z), (7-x-y), (7-z-t), (7-y-t).And in square 2b (x+y+z+t-7). And all this 9 numbers are nonegative integer.Solving the system of 9 inequality we have x>=0, y>=0, z>=0, t>=0, (7-x-z)>=0, (7-x-y)>=0, (7-z-t)>=0, (7-y-t)>=0, (x+y+z+t-7)>=0. By brut force i found 666 solutions in nonegative integers of the system. Conntact me on email because i cant upload file of solutions here.

Eric Zelikman
May 20, 2014

If we represent the grid as follows: ( a b c d e f g h i ) \left( \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \right)

It is necessary for a, c, e, and g (Or any three non-adjacent values) to be defined to calculate the rest of the grid. Then, b=7-(a+c), d=7-(a+g), f=7-(d+e), h=7-(b+e), i=7-(g+h) and 7-(c+f) can be redrawn in the grid as, ( a 7 a c c 7 a g e a + g e g a + c e a c g + e + 7 ) \left( \begin{array}{ccc} a & 7-a-c & c \\ 7-a-g & e & a+g-e \\ g & a+c-e & -a-c-g+e+7 \end{array} \right)

All of these must be positive or zero, and none can be greater than 7. So, 7≥(a+c, a+g)≥e and e+7≥a+c+g represents all solutions.

Now, one can easily generalize a given formula like this for any value instead of 7, by utilizing the difference between the values. These differences, by virtue of the fact that it adds a solutional row of the magic square every time, on top of all of the others, must add a new such magic constant based on a new square with a size of n*n where n is the new number. As such, the solution to a certain point would be all of the magic constants up to that point added together. The magic square formula is n(n^2+1)/2. n = 1 n n ( n 2 + 1 ) 2 = n = 1 n n 3 2 + n 2 = n = 1 n n 3 + n = 1 n n 2 \displaystyle\sum_{n=1}^{n} \frac{n*(n^{2}+1)}{2}= \displaystyle\sum_{n=1}^{n} \frac{n^3}{2}+\frac{n}{2}=\frac{\displaystyle\sum_{n=1}^{n} {n^3} + \displaystyle\sum_{n=1}^{n} {n}}{2}

Which is the summation to a number, n(n+1)/2 added to the sum of cubes, which is the previous summation squared, all divided by 2. That is, n ( n + 1 ) 2 + ( n ( n + 1 ) 2 ) 2 2 o r n ( n + 1 ) 4 + ( n ( n + 1 ) ) 2 8 \frac{\frac{n(n+1)}{2}+(\frac{n(n+1)}{2})^2}{2}\hspace{2 mm} or\hspace{2 mm} {\frac{n(n+1)}{4}+\frac{(n(n+1))^2}{8}}

As the summation was created by a sum of differences starting from one, a single iteration is necessary before the calculation, so for x=7, one must evaluate at 8: 8 ( 8 + 1 ) 4 + ( 8 ( 8 + 1 ) ) 2 8 = 666 {\frac{8(8+1)}{4}+\frac{(8(8+1))^2}{8}}=666

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...