An m*n rectangle is divided into mn unit squares by lines drawn parallel to its sides Let S=[k, k+1, k+2,... mn-1] be a set of mn consecutive integersthe object is to try and to write all the...

An m*n rectangle is divided into mn unit squares by lines drawn parallel to its sides

Let S=[k, k+1, k+2,... mn-1] be a set of mn consecutive integers

the object is to try and to write all the elements of S in the rectangle grid, one element of S per unit square, in such a way that the following two conditions are satisfied simultaneously:

in each row, the elements are congruent mod m;

in each column the elements are congruent mod n;

determine if the placement is possible when k=19 and

(i) m=3 and n=8

(ii) m=4 and n=6

2 Answers

mlehuzzah's profile pic

mlehuzzah | Student, Graduate | (Level 1) Associate Educator

Posted on

So the answer to the first question is yes, and here is an example:

19   22   25   28   31   34   37   40

27   30   33   36   39   42   21   24

35   38   41   20   23   26   29   32

And the answer to the second question is no.

 

Here's why:

k actually doesn't matter

If you had a grid filled in, that worked, you could subtract j from each and every box.  All of the modulo conditions would still match.  But the numbers would be   k-j, k-j+1, ..., k-j +mn -1

So for now, we will just assume k=0 (and then add the appropriate number later, if needed)

 

What matters is the relationship between m and n

If they are "relatively prime", you can fill out the grid.  If not, you can't.  "Relatively prime" means their gcd (greatest common denominator) is 1

 

If they are relatively prime, here is how to fill out the box:

0   m   2m   3m   4m   5m ... (n-1)m

n   n+m  n+2m ...

2n  2n+m ...

Then take all of the numbers modulo nm

 

You don't have any duplicate numbers.

 

In the case of 4 and 6, (and any time they aren't relatively prime), here is what goes wrong:

In some order, the numbers in one of the rows is:

0  4  8  12  16  20

but notice that, for example, 0 and 12 (or 4 and 16, or 8 and 20) are also the same modulo 6

So you need to put 12 in the same column as 0, even though it is already in the same row, and there is no way to fill out the grid.