2
$\begingroup$

There is a 4X4 array each entry of which can be filled with the numbers 1,2,3,4. In how many ways can we fill the array such that the sum of each row and each column is divisible by 4?

$\endgroup$
5
$\begingroup$

The answer should be 4^9. 3 rows and 3 columns have one entry that is chosen to make that row/column divisible by 4. One more cell is chosen so that the calculated rows and columns are divisible by 4. 4 options for the basic cells.

a a a b

a a a b

a a a b

c c c d

Each cell labeled a can be 1,2,3 or 4. Each cell labeled b chosen so that its row is divisible by 4. Each cell labeled c is chosen so that its column is divisible by 4. d can be chosen either way and will be the same.

$\endgroup$
  • $\begingroup$ I was thinking on similar grounds, but will we always be able to make the last column and row divisible by 4? $\endgroup$ – Noel Jan 14 '13 at 15:31
  • $\begingroup$ @Noel it is always possible, and always in a unique way. $\endgroup$ – John Dvorak Jan 14 '13 at 15:32
  • $\begingroup$ Can we prove this? $\endgroup$ – Noel Jan 14 '13 at 15:34
  • $\begingroup$ all of the a's add up to the same value whether you add the columns first or the rows first. I know that isn't a formal proof but that is why both the last row and column will be divisible by 4 if either of them are. $\endgroup$ – kaine Jan 14 '13 at 15:42
  • $\begingroup$ Yes man you are right I came up with a formal proof- we just fill the last column in such a way that every row is divisible by 4 as stated by @JanDvorak above and then the last row such that each column is divisible by 4. Now all we need to prove is that the last row too is divisible by 4, this can be done by considering that each entry of the last row is [-(summation of the above column) (congruent to 4 -congruent class{1,2,3,4})] and when we take the sum of all such entries it will be congruent to 0 (mod 4) its nothing but the sum of the rest of the array. BTW Thank you. $\endgroup$ – Noel Jan 14 '13 at 16:04
1
$\begingroup$

4^9.

More generally:

In how many ways can a $X \times Y$ be filled by values $1 .. N$ such that the sum in each row and column is divisible by $N$?

$N^{(X-1)(Y-1)}$

Choose all values in all cells except the last row and column arbitrarily and independently (giving the figure above).
Choose the values in the last row such that the column sums are correct (one way, always possible).
Choose the values in the last column such that the row sums are correct (one way, always possible).

Since the sum of the row sums is always equal to the sum of the column sums, so the same value in the bottom-right that sets the last row to be divisible by four will also set the last column to be divisible by four

$\endgroup$
  • $\begingroup$ what if we apply this algorithm and end up with the last row/column not being divisible by 4? $\endgroup$ – Noel Jan 14 '13 at 15:41
  • 1
    $\begingroup$ @Noel It will always be. The sum of column sums (divisible by N) is always equal to the sum of row sums (divisible by N) $\endgroup$ – John Dvorak Jan 14 '13 at 15:46
  • $\begingroup$ Yeah man thanks you are right I got it. $\endgroup$ – Noel Jan 14 '13 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.