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
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.
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.
for *mn-1* t needs to be k+mn-1
We’ve answered 319,195 questions. We can answer yours, too.Ask a question