Good Arrays

Probability Level 5

Consider a $7 \times 7$ array, each of whose cells is filled up by an integer between $1$ and $49$ (inclusive). Every cell has exactly one number written on it, and every number between $1$ and $49$ appears exactly once.

An operation on the array is defined as follows:

Select a row / column of the array.
Either add $1$ to all numbers in that row / column or subtract $1$ from all numbers in that row / column.

An array is said to be good if there exists a finite sequence of operations after which all cells have the same number written on them. Find the last three digits of the number of good arrays.

Details and assumptions

A row / column can be operated on as many times as wanted.
You might use the fact that $7$ is a prime.
This problem is not original.

The answer is 200.

1 solution

Ww Margera
Sep 12, 2014

Suppose the array is a[i][j]. The condition on the array is that we can find two arrays b[] and c[] such that a[i][j] - b[i] - c[j] is independent of i and j. Clearly we can choose b[] and c[] such that this value is 0. In other words, a[i][j] = b[i] + c[j]. Now, we can permute the rows and columns of a such that b and c are both sorted in ascending order. In other words, b[1] + c[1] = 1 while b[7] + c[7] = 49. Moreover, b[i] + c[j] != b[k] + c[l] for i!=k, j!=l. In other words, b[i] - b[k] != c[l] - c[i]. Therefore, the set of differences between elements of b is disjoint from the set of differences between elements of c. We can see that this along with the conditions of b[1]+c[1]=1 and b[7]+c[7]=49 imply that one of b and c is [1,2,3,4,5,6,7] and the other is [0,7,14,21,28,35,42]. In each of these cases, we can take an array so formed and permute the rows and columns in any order to get a valid array for the initial question. So the number of good arrays = 2 * 7! * 7! = 50803200.

Good Arrays

The answer is 200.

1 solution

0 pending reports