Date: Wed, 11 Feb 1998 11:26:21 +0000
From: Joshua Bao
To: Dave Rusin
Subject: Re: Diophantine Equations
Dave Rusin wrote:
> I'm almost certain there is no closed form for the number you seek. This is
> usually called the "postage stamp problem". It may be discussed in
> Guy's "Unsolved Problems in Number Theory";
>
> dave
Thank you for your help. I also have another somewhat related inquiry.
It comes from a problem that I found. I don't know if a solution exists.
Suppose that we have an MxN grid of positive integers which can undergo the
following transformations:
1) Subtract 1 from one element and all of its neighbors.
2) Add 1 to one element and all of its neighbors.
A neighbor is defined as elements directly adjacent to the number (above or
below, left or right, excluding diagonals).
Example, for a plate of the shape:
5 2 1 3 8
6 8 1 2 2
4 6 5 2 9
Using transform 2) in the position (2,3) leads to the board:
5 2 2 3 8
6 9 2 3 2
4 6 6 2 9
and then, using 1) on (1,4) the following board is obtained:
5 2 1 2 7
6 9 2 2 2
4 6 6 2 9
Is it possible to describe a sequence of moves that should lead to a grid where
all the elements have
the same value x ? If so what is the minimum number of moves?
I would really appreciate it if you could help me or referr me to some
references.
--
- Josh Bao
SCAHS(Class of 1998) CTY-93 YSSP-95 RSI-97 SET Member
Home Page -
http://web.mit.edu/jbao/www/
"Always do what you love to do, and justify that love."
==============================================================================
Date: Wed, 11 Feb 1998 11:04:29 -0600 (CST)
From: Dave Rusin
To: xxb1@psu.edu
Subject: Re: Diophantine Equations
What do you allow around the edges? Can I increase just one edge cell (e.g.
the (1,3) cell) on the grounds that this is just the visible effect of
a type-1 move centered at the (0,3) spot? How about moves centered at
positions like (1,x): is it your intention to allow increasing/decreasing
precisely the entries (1,x-1) (1,x) (1,x+1) and (2,x) ?
If it weren't for edge effects, it would be easy to show that NOT all
grids can be reduced to a constant grid. If w is a primitive sube root of
unity and I = sqrt(-1), we can associate to any grid the complex number
S = sum( x[i,j] w^i I^j ); then your allowable moves change S by
adding or subtracting
w^i I^j * ( 1 + w^(-1) + w + I^(-1) + I ) = 0
That is, S is an invariant under the proposed moves. The state to which
you hope to transform the grid has S = 0 if the number of columns is
a multiple of 3, say; so an initial grid filled with zeroes except for
a lone 1 somewhere cannot possibly be transformed to a constant grid.
As I say, the previous paragraph assumes no moves are allowed along the
edges (or more generally that no moves are allowed which alter S).
dave
==============================================================================
Date: Wed, 11 Feb 1998 18:22:18 +0000
From: Joshua Bao
To: Dave Rusin
Subject: Re: Diophantine Equations
Dave Rusin wrote:
> What do you allow around the edges? Can I increase just one edge cell (e.g.
> the (1,3) cell) on the grounds that this is just the visible effect of
> a type-1 move centered at the (0,3) spot?
No. A move has to be centered on a cell that exist on the grid (i.e., the cell
(i,j) with 1<=i<=mand 1<=j<=n).
> How about moves centered at
> positions like (1,x): is it your intention to allow increasing/decreasing
> precisely the entries (1,x-1) (1,x) (1,x+1) and (2,x) ?
Yes. A neighbor is increased or decreased as long as both it and the chosen
center exists on the grid.I would like to know 1) if all grids are transferable
2) if there is a sytematic process of doing so.
I apologize for the imprecision of the statement of the problem. Thank you for
your help.
J. Bao
==============================================================================
Date: Wed, 11 Feb 1998 18:24:02 +0000
From: Joshua Bao
To: Dave Rusin
Subject: Addendum
Naturally we must assume that n,m>=3. Thanks
==============================================================================
Date: Sun, 15 Feb 1998 15:09:12 +0000
From: Joshua Bao
To: Dave Rusin
Subject: Re: Addendum
Dave Rusin wrote:
> > Naturally we must assume that n,m>=3. Thanks
>
> Au contraire, I would argue that there's no reason to disallow m,n = 1, 2.
> Those cases fit just fine into the framework. Let me show you what I came up
> with. In return, let me ask you to tell me how this particular question arose:
> I had a good time playing with some of the data during the day!
Thank you for the extensive analysis !! A special case of the problem comes from a
chinesepuzzles book. I would also like to know a way to find 'move's to transfer
the given matrix to the form of xJ(all elements are same integer) where the x is an
given integer. Clearly, this is much easier - all we need to do is solve a system
of linear integer (diophantine) equations. Is there a systematic method of doing
this (with matrix and integer operations), particularly when G/H is infinite ?
Thanks.
Sincerely,
J. Bao
==============================================================================
Date: Mon, 16 Feb 1998 10:48:39 -0600 (CST)
From: Dave Rusin
To: xxb1@psu.edu
Subject: Re: Addendum
> I would also like to know a way to find 'move's to transfer
> the given matrix to the form of xJ(all elements are same integer)
I don't know if there's anything more elegant than brute force. You are
given an mxn matrix M and m*n matrices M(i,j) of the same size;
you want to solve m*n equations in m*n+1 unknowns
Sum x(i,j) M(i,j) = M + x J
Well, that system of linear equations may be written as a single matrix
equation A X = B where A is an m*n by m*n+1 matrix, and X and B
are columns of the appropriate sizes. You can do row-reduction to determine
the solutions, but since you want to find all _integer_ solutions, you
need to do this without division.
It turns out that you can reduce all integer matrices to a canonical
form this way (I think it's usually called "Smith normal form"). If
you view ordinary row-reduction as writing every matrix A in the
form U Z V with U and V invertible and Z of the special form
[ identity matrix possible zeros ]
[ possible zeros possible zeros ]
then the right statement for integer matrices is that one can do
row-reduction without division and write A = U Z V where U and V are
integral matrices with integral inverses, and Z has the form
[ diagonal matrix possible zeros ]
[ possible zeros possible zeros ]
where the diagonal entries satisfy d1 | d2 | d3 | ... and all d_i > 0.
With those conditions, Z is unique (U and V are not). In this case,
the equation A X = B may be written Z (V X) = U^(-1) B which is then
easy to solve: there is no solution unless the rows of U^(-1)B are zero
whenever the corresponding row of Z is zero (those are the rows at the
bottom of Z), and there is no solution unless the i-th row of U^(-1) B
is a multiple of d_i. Otherwise there are solutions, and it's clear how
to get them: the i-th entry of (VX) must be (i-th entry of U^(-1)B)/(d_i)
and the entries of VX corresponding to the zero rows of Z are arbitrary.
That is, the solutions have the form
(VX) = W_0 + [0, 0, ..., r_1, r_2, ...]^t
(I write []^t for the transpose of a row vector rather than trying to
type out a column vector on my screen!) Here the r_i are arbitrary integers.
Then you have the solution to your original problem:
X = V^(-1) ( W_0 + [0, 0, ..., r_1, r_2, ...]^t )
The entries of this column matrix describe the complete solution for your
unknowns x(i,j).
Since I'm sure I've lost you at this point, let me do an example. Suppose
you wanted to find moves taking M =
[ 1 2 3 ]
[ 4 8 6 ]
to a multiple of the identity. We need to find 7 unknowns which make
sum( x(i,j) M(i,j) ) = M + x J, that is,
x(1,1)[ 1 1 0] + x(1,2)[1 1 1] + x(1,3)[0 1 1] +
[ 1 0 0] [0 1 0] [0 0 1]
x(2,1)[ 1 0 0] + x(2,2)[0 1 0] + x(2,3)[0 0 1] - x [1 1 1] = [1 2 3]
[ 1 1 0] [1 1 1] [0 1 1] [1 1 1] [4 8 6]
So I get 6 equations in the 7 unknowns. I peel off the coefficients of
each unknown in the usual fashion to get a matrix equation A X = B :
[ 1 1 0 1 0 0 -1] [x(1,1)] [ 1 ]
[ 1 1 1 0 1 0 -1] [x(1,2)] [ 2 ]
[ 0 1 1 0 0 1 -1]*[x(1,3)] =[ 3 ]
[ 1 0 0 1 1 0 -1] [x(2,1)] [ 4 ]
[ 0 1 0 1 1 1 -1] [x(2,2)] [ 8 ]
[ 0 0 1 0 1 1 -1] [x(2,3)] [ 6 ]
[ x ]
I can perform all the "U^(-1)" work described above by simply doing row-
reduction using integer transformations in the usual methodical fashion:
[ 1 0 0 0 1 -1 0 | -1 ]
[ 0 1 0 0 -1 0 0 | -3 ]
[ 0 0 1 0 1 1 -1 | 6 ]
[ 0 0 0 1 0 1 -1 | 5 ]
[ 0 0 0 0 2 0 0 | 6 ]
[ 0 0 0 0 0 0 0 | 0 ]
I can further reduce using column operations, although this will alter the
solution set as I'll describe below. But by adding multiples of the first
four columns to the other columns, we can clear achieve the matrix Z =
[ 1 0 0 0 0 0 0 ]
[ 0 1 0 0 0 0 0 ]
[ 0 0 1 0 0 0 0 ]
[ 0 0 0 1 0 0 0 ]
[ 0 0 0 0 2 0 0 ]
[ 0 0 0 0 0 0 0 ]
Here d1=d2=d3=d4=1, d5=2. There is a zero row, but it's opposite a zero
in the right-hand column "U^(-1)B". Likewise, the 5th entry of that
column (=6) is a multiple of d5 (=2). Thus there are integer solutions
to the original problem. All the solutions to Z (VX) = U^(-1)B are
clearly of the form (VX) =
[ -1 ] <- just dividing by d1=1 here
[ -3 ]
[ 6 ]
[ 5 ]
[ 3 ] <- had to divide by d5=2 here
[ r_1] <- any arbitrary integer here
[ r_2] <- ... and here (Z had two columns of zeros)
(That's "W" in the discussion above).
Now, V is the matrix for which A' = ZV, where A' was the result of
doing just the row operations. It's straightforward to see that V^(-1) =
[ 1 0 0 0 -1 1 0 ]
[ 0 1 0 0 1 0 0 ]
[ 0 0 1 0 -1 -1 1 ]
[ 0 0 0 1 0 -1 1 ]
[ 0 0 0 0 1 0 0 ]
[ 0 0 0 0 0 1 0 ]
[ 0 0 0 0 0 0 1 ]
(That is, V^(-1) is built from the same "blocks" as A', with sign changes
off the diagonal.) Thus we recover our solutions X by multiplying
(VX) by this V^(-1) on the left:
[x(1,1)] [-4+r1 ]
[x(1,2)] [0 ]
[x(1,3)] =[3-r1+r2]
[x(2,1)] [5-r1+r2]
[x(2,2)] [3 ]
[x(2,3)] [r1 ]
[ x ] [r2 ]
So now you know just what moves are possible to turn the original M
into xJ: use (-4+r1) of the first, none of the second, etc. Here,
a negative number of moves means to subtract 1's from certain spots
rather than add them, of course. Total number of moves is then
|-4+r1| + |0| + |3-r1+r2| + |5-r1+r2| + |3| + |r1|
= |-4+r1| + |3-r1+r2| + |5-r1+r2| + |r1| + 3.
The minimum value of this expression across the entire r1-r2 plane
is 9, which occurs in a box bounded by r1=0, r1=4, r2-r1=-3, r2-r1=-5.
So for example you could use r1=4 and r2=0, meaning
0, 0, -1, 1, 3, 4
moves of types 1, 2, ..., 6 respectively to go from xJ = r2 J = the zero
matrix to the original matrix M. You can check this directly.
As it turns out, there is enough of a pattern to the M(i,j) that you
can expect the matrix A to have a pattern, too, making it plausible
that the computations can be done more elegantly. But for small m and
n this procedure is fairly efficient as it stands.
dave