Constructing a Conditional TableDate: 04/14/98 at 12:15:00 From: Dave Brown Subject: Magic Squares (sort of) Are you aware of any method to solve the following problem? I have a table that is, for example, 5 columns wide and 7 rows high and contains either a 0 or a 1 in each cell. If I told you that the total number of 1's in the 5 columns is 3,5,1,4,2 and that the total number of 1's in the 7 rows is 2,3,1,4,1,2,2, is there a quick method to determine if such a table can be constructed? The first test is obviously going to be that the sum of the 1's in the columns must equal the sum of the 1's in the rows. Beyond that I'm sort of lost. I could go through all of the possible iterations and make a list of legal constructs, but since I'll ultimately be dealing with tables of over 20 rows and columns, such a process would quickly get out of hand. Any help that you can give me on this problem will be greatly appreciated. Dave Date: 04/20/98 at 10:33:33 From: Doctor Ujjwal Subject: Re: Magic Squares (sort of) Dear Dave, First let me thank you for sending such a stimulating problem. I enjoyed every minute I spent on it. Starting from the given conditions, it could be a long way to the solution, so let's move the solution to meet us halfway. We start by imagining that we already have the solution written out in form of a table. If we reorder the columns, in the descending order of 1's (i.e. 5, 4, 3, 2, 1), it will not change the number of 1's in each row. Next let's reorder the rows in descending order of 1's (i.e. 4, 3, 2, 2, 2, 1, 1). Doing this we have not added or removed any 1's. So our "magic" rectangle is inherently the same. Only we have managed to squeeze out the zero's in the lower right corner. Now create an empty table with descending order of columns and rows. Fill in the correct number of 1's in the rows so that all the 1's are crowded in the top left corner: (5) (4) (3) (2) (1) (4) 1 1 1 1 0 (3) 1 1 1 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (1) 1 0 0 0 0 (1) 1 0 0 0 0 Clearly the columns do not have the correct number of 1's. But we can take care of that next. As you will notice, the first column has a surplus of 1's. So let's shift the 1 in the last row toward the right until it reaches a column that is short a 1: (5) (4) (3) (2) (1) (4) 1 1 1 1 0 (3) 1 1 1 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (1) 1 0 0 0 0 (1) 0------>1 0 0 (1 shifted 2 places toward the right) The first column still has a surplus, so shift the 1 in the sixth row toward the right, until it reaches a deficient column: (5) (4) (3) (2) (1) (4) 1 1 1 1 0 (3) 1 1 1 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (1) 0---------->1 0 (1 shifted 3 places towards right) (1) 0 0 1 0 0 Now we have the first column 'fixed'. Let's do the same for the surplus in the second column: (5) (4) (3) (2) (1) (4) 1 1 1 1 0 (3) 1 1 1 0 0 (2) 1 1 0 0 0 (2) 1 1 0 0 0 (2) 1 0---------->1 (1 shifted 3 places towards right) (1) 0 0 0 1 0 (1) 0 0 1 0 0 And we already have all the rows and columns right! This is where we moved our solution to start with. We only need to reorder the rows and columns back as desired. I believe this approach will work for this class of problems. Do try it out and let us know any cases where it doesn't. Thank you and good luck! -Doctor Ujjwal Rane, The Math Forum Check ou tour web site! http://mathforum.org/dr.math/ Date: 04/20/98 at 19:33:52 From: Dave Brown Subject: Re: Magic Squares (sort of) Dear Dr. Rane, Thanks for your solution. After thinking about it a while, a good night's sleep and a few moments of enlightenment, I came up with a somewhat similar solution, though not as elegant! I will program your solution and try it. Thanks very much for taking the time to consider the problem. Dave |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/