Constructing a Conditional Table

Date: 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