can anyone guide me how to do the problem? Thanks! Suppose we have information a

Question

can anyone guide me how to do the problem? Thanks!

Suppose we have information about the height and weight of each person in the class, and we organize this information into a two dimensional table where there are n height intervals, and m weight intervals. In the table, the (i, j) entry indicates how many people fall into height category i and weight category j. Suppose that this table is kept secret, but the number of people falling into each height category is public, as is the number that fall into each weight category. That is, the n row sums and the m column sums of the table are published, but none of the individual cells in the table are published. Problem 1. As above, suppose you are given a table with all cell values deleted, but the n row sums and m column sums are given to you. Call this an empty table. Assume that the sums are non-negative and that the sum of the row sums equals the sum of the column sums. Find and describe an algorithm that fills in the table with non- negative cell values so that each row and each column sums to its required amount. Explain why your algorithm never fails. Establish that an empty table can be filled in correctly (so that the entries in each row and in each column sum to their required amounts) if and only if the sum of given row sums equals the sum of given column sums.

Explanation / Answer

You could certainly use a "trial and error" approach and get a correct
solution to the mXn(in our case let's see for 3x3 ) magic square, but it sounds like it would be luck-based, so let's try a more methodical approach.

I'm taking this assumption that the sum rows and sum coloumns is equal .. then only this method will work.

One way a 3x3 magic square can be constructed is by using a little
simple arithmetic and algebraic reasoning.

One could reason that the numbers 1-9 add up to 45, and since all
these numbers are contained in three ROWS (exclusively), the sum of
each ROW must be 15. I want to make sure you understand this before
proceeding, so look at the little algebraic argument below that
"proves" that each row should sum to 15:


Since we don't know the order of the numbers 1-9 that correctly fill
out the 3x3 magic square, substitute the variables a-i into the
square.

+---+---+---+
| a | b | c |
+---+---+---+
| d | e | f |
+---+---+---+
| g | h | i |
+---+---+---+

We know that

a + b + c + d + e + f + g + h + i = 45

grouping the letters by rows we get

(a + b + c) + (d + e + f) + (g + h + i) = 45

But since the sum of each row should be equal (let's say the sum
equals X), the rows can be rewritten as

(a + b + c) = X
(d + e + f) = X
(g + h + i) = X

and the equation above can then be rewritten as

X + X + X = 45, or

3*X = 45, so

X = 15

This shows that the three rows sum to 15.

It then follows from the definition of a magic square that all the
columns and diagonals will also sum to 15.


OK, now we know that each row, column, and diagonal will sum to 15, so
the challenge is to figure out HOW to arrange the numbers to make that
happen.

This may be done by a brute-force method as follows. Basically,
through trial and error, I found all the ways that I could take three
numbers from 1-9 and get a sum of 15:

1 + 5 + 9 = 15
1 + 6 + 8 = 15
2 + 4 + 9 = 15
2 + 5 + 8 = 15
2 + 6 + 7 = 15
3 + 4 + 8 = 15
3 + 5 + 7 = 15
4 + 5 + 6 = 15

Again, double check me here! Convince yourself that these are the
only ways you can get a sum of 15 from three numbers chosen from 1-9.

Now, from the equations above, note the following connections to the
3x3 magic square:

1, 3, 7, and 9 are each in TWO equations that sum to 15. The middle
cells of each outside row/column are each in TWO equations (One row,
one column).

+---+---+---+
| - | x | - |
+---+---+---+
| | | | |
+---+---+---+
| | | | |
+---+---+---+

(I'm willing to bet that 1, 3, 5, and 7 will each fill one of these
middle cells on the outside rows/columns!)

2, 4, 6, and 8 are each in THREE equations that sum to 15. The corner
cells are each in THREE equations (One row, one column, and one diagonal).

+---+---+---+
| x | - | - |
+---+---+---+
| | | | |
+---+---+---+
| | | | |
+---+---+---+

(From this, I'd be willing to bet that 2, 4, 6, and 8 are going to
fill the corners of the magic square!)

5 is in FOUR equations that sum to 15. The middle cell is in FOUR
equations (one row, one column, and two diagonals).

+---+---+---+
| | | | / |
+---+---+---+
| - | x | - |
+---+---+---+
| / | | | |
+---+---+---+

(From this it seems likely that 5 should go in the middle cell of
the 3x3 magic square!)

---------------------------------

Using the above observations, let's fill out the square!

Looking at a blank 3x3 magic square, one can see that the middle
cell should be in four equations (one row, one column, and two
diagonals), and looking at the equations, one can see that 5 is the
only number in four of the eight equations. Therefore, 5 can be put
into the middle cell.

+---+---+---+
| | | |
+---+---+---+
| | 5 | |
+---+---+---+
| | | |
+---+---+---+

Now there are four corners which when filled, are each used in three
equations. By putting any of the four numbers (2,6,4,8) in the
upper-left corner (2 in this example), only one number can go in the
bottom-right corner (8 in this example) to make the sum of that
diagonal be 15.

+---+---+---+
| 2 | | |
+---+---+---+
| | 5 | |
+---+---+---+
| | | 8 |
+---+---+---+

Now, either of the other numbers (4 or 6 in this example) can go in
the bottom left corner (6 in this example), leaving only one choice
for the top right corner (4 in this example).

+---+---+---+
| 2 | | 4 |
+---+---+---+
| | 5 | |
+---+---+---+
| 6 | | 8 |
+---+---+---+

Last, the remaining four numbers (1, 3, 7, 9) can be placed in only
one way to make the sums be 15.

+---+---+---+
| 2 | 9 | 4 |
+---+---+---+
| 7 | 5 | 3 |
+---+---+---+
| 6 | 1 | 8 |
+---+---+---+

This is one correct solution to the 3x3 magic square.

There are seven other solutions. A 3x3 magic square contains eight
possible solutions total; four rotations and four reflections.


For more information on such questions, you can visit the following
links :

http://mathforum.org/alejandre/magic.square.html
http://mathforum.org/library/drmath/view/67016.html


Hope it helps ... plz rate :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.