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 | Add Yours

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.

 

 

We’ve answered 318,925 questions. We can answer yours, too.

Ask a question