Associated Topics || Dr. Math Home || Search Dr. Math

### 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
```
Associated Topics:
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search