IBM Research | Ponder This | October 2005 solutions

# Ponder This

## October 2005

<<September October November>>

5x5 array with entries {0,1,2}

a(i1,j1)+a(i2,j2) not equal to a(i1,j2)+a(i2,j1) is equivalent to a(i1,j1)-a(i1,j2) not equal to a(i2,j1)-a(i2,j2).  Therefore the row wise differences between any pair of columns j1 and j2 must be distinct.  Similarly the column wise differences between any pair of rows j1 and j2 must be distinct.  With entries from {0,1,2} the possible differences are {-2,-1,0,1,2} so each must appear exactly once between each pair of rows or columns.  Each row contains at least two pairs of equal elements.  So there are least 10 pairs of equal elements considering all 5 rows.  But there are only 10 pairs of columns.  So each row must contain exactly two pairs of equal elements which means no element can appear 3 times.  This means there are at most two 0's and two 2's in each row.  So there are at most 4 differences of +2 or -2 in that row.  So considering all 5 rows there are at most 20 row wise differences of +2 or -2. Now each pair of columns contains one row wise difference of 2 and one of -2 or 20 in all.  So each row must contain two 0's, two 2's and one 1.  Similarly for the columns.  So by permuting rows and columns we can put the array in the following form:

0  0  1  2  2
0  a     c  c
1
2  b
2  b

Now the entry marked a must be 2 in order to obtain a row wise difference of -2 between the first pair of columns.  Also one of entries marked b must be a 0 in order to obtain a difference of 2. Similarly for the entries marked c.  So we now have (permuting if necessary):

0  0  1  2  2
0  2  c  0  d
1  a
2  0
2  b

The entry marked a cannot be 1 as this would mean two row wise differences of 0 in the first pair of columns.  Since we already have two 0's in the second column this means a=2 which implies b=1. Similarly c=2, d=1.  So we now have:

0  0  1  2  2
0  2  2  0  1
1  2  b  d
2  0  c  a
2  1

Since each row and column contains exactly one 1 the entry marked a must be the fifth 1.  The entry marked b must be 0 in order to obtain a row wise difference of 2 between the second and third columns.  Also the entry marked c must be 2 in order to obtain a row wise difference of -2 between the second and third columns.  Similarly
d=2.  This leaves:

0  0  1  2  2
0  2  2  0  1
1  2  0  2
2  0  2  1
2  1

Now since each row and column contains two 0's, one 1 and two 2's it is easy to fill in the remaining elements.

0  0  1  2  2
0  2  2  0  1
1  2  0  2  0
2  0  2  1  0
2  1  0  0  2

This must still be checked which can be done by considering each pair of columns.

7x7, 11x11 and 13x13 arrays

For these larger sizes we look for solutions of a particular type.  Suppose p is a prime and let A be a pxp array with entries a(i,j)=(i-1)*(j-1) mod p.  It is easy to see that A satisfies the property mod p.  Also we may add (mod p) a constant to any row or column of A and A will still satisfy the property mod p.  Clearly A will also satisfy the property over the integers.  So starting with A we search for constants to add to the rows and columns of A to minimize the size of the entries.  For example when p=3 we start with

0  0  0
0  1  2
0  2  1

and by adding 1 to the third row and third column mod p we obtain.

0  0  1
0  1  0
1  0  0

For p=5,7,11,13 we obtain the following arrays.

0  1  0  2  2
0  2  2  0  1
2  0  1  0  2
1  0  2  2  0
2  2  0  1  0

0  2  2  0  3  4  3
0  3  4  3  0  2  2
3  0  2  2  0  3  4
2  0  3  4  3  0  2
4  3  0  2  2  0  3
2  2  0  3  4  3  0
3  4  3  0  2  2  0

0  1  5  1  0  2  7  4  4  7  2
0  2  7  4  4  7  2  0  1  5  1
4  7  2  0  1  5  1  0  2  7  4
1  5  1  0  2  7  4  4  7  2  0
2  7  4  4  7  2  0  1  5  1  0
7  2  0  1  5  1  0  2  7  4  4
5  1  0  2  7  4  4  7  2  0  1
7  4  4  7  2  0  1  5  1  0  2
2  0  1  5  1  0  2  7  4  4  7
1  0  2  7  4  4  7  2  0  1  5
4  4  7  2  0  1  5  1  0  2  7

0  7  3  1  1  3  7  0  8  5  4  5  8
0  8  5  4  5  8  0  7  3  1  1  3  7
7  3  1  1  3  7  0  8  5  4  5  8  0
8  5  4  5  8  0  7  3  1  1  3  7  0
3  1  1  3  7  0  8  5  4  5  8  0  7
5  4  5  8  0  7  3  1  1  3  7  0  8
1  1  3  7  0  8  5  4  5  8  0  7  3
4  5  8  0  7  3  1  1  3  7  0  8  5
1  3  7  0  8  5  4  5  8  0  7  3  1
5  8  0  7  3  1  1  3  7  0  8  5  4
3  7  0  8  5  4  5  8  0  7  3  1  1
8  0  7  3  1  1  3  7  0  8  5  4  5
7  0  8  5  4  5  8  0  7  3  1  1  3

It would be of interest to find good arrays that can not be constructed in this way.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com