Re: [math-fun] Jumping square points
That's a very beautiful problem. I've appended a short solution to the end of this e-mail.
----- Original Message ----- From: Eric Angelini Sent: 01/29/14 10:30 AM To: math-fun Subject: [math-fun] Jumping square points
Hello Math-Fun, Four points shape a square of size "s". Every minute a point randomly jumps over another point and lands symmetrically behind it. Is it possible that, at some stage, the 4 points shape a new square having size "t" > "s"? Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
***** spoiler alert ***** . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . No. Operate in the ring Z[i] of Gaussian integers, and let {a,b,c,d} be the Gaussian integers corresponding to the vertices of the square. When you apply the process to obtain {a,2a-b,c,d}, the greatest common divisor (again a Gaussian integer, up to multiplication by the ring units) remains invariant (similar to Euclid's algorithm). Hence, if they form a square at any time, it must be the same size and orientation as the original square. Sincerely, Adam P. Goucher
I think you can do effectively the same thing as Adam without needing ideas like Gaussian integer GCD. Eric's problem asked about forming a new square with size "t" > "s", and that's because it's obvious you can never make a square that's *smaller* than the unit square you started with, as all points you ever get are part of the square lattice with the original square as its unit. But since the point-replacing process is invertible, if it can't give you a smaller square, it can't give you a larger one either. --Michael On Wed, Jan 29, 2014 at 9:46 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
That's a very beautiful problem. I've appended a short solution to the end of this e-mail.
----- Original Message ----- From: Eric Angelini Sent: 01/29/14 10:30 AM To: math-fun Subject: [math-fun] Jumping square points
Hello Math-Fun, Four points shape a square of size "s". Every minute a point randomly jumps over another point and lands symmetrically behind it. Is it possible that, at some stage, the 4 points shape a new square having size "t" > "s"? Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
***** spoiler alert ***** . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
No. Operate in the ring Z[i] of Gaussian integers, and let {a,b,c,d} be the Gaussian integers corresponding to the vertices of the square. When you apply the process to obtain {a,2a-b,c,d}, the greatest common divisor (again a Gaussian integer, up to multiplication by the ring units) remains invariant (similar to Euclid's algorithm).
Hence, if they form a square at any time, it must be the same size and orientation as the original square.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
That's a pretty solution! Another argument is that if I keep track of a quadrilateral formed by the 4 points, where I think of jumping one point over another as sliding both of them, then the area of this quadrilateral is preserved. Cris On Jan 29, 2014, at 7:56 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
I think you can do effectively the same thing as Adam without needing ideas like Gaussian integer GCD. Eric's problem asked about forming a new square with size "t" > "s", and that's because it's obvious you can never make a square that's *smaller* than the unit square you started with, as all points you ever get are part of the square lattice with the original square as its unit. But since the point-replacing process is invertible, if it can't give you a smaller square, it can't give you a larger one either.
--Michael
On Wed, Jan 29, 2014 at 9:46 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
That's a very beautiful problem. I've appended a short solution to the end of this e-mail.
----- Original Message ----- From: Eric Angelini Sent: 01/29/14 10:30 AM To: math-fun Subject: [math-fun] Jumping square points
Hello Math-Fun, Four points shape a square of size "s". Every minute a point randomly jumps over another point and lands symmetrically behind it. Is it possible that, at some stage, the 4 points shape a new square having size "t" > "s"? Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
***** spoiler alert ***** . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
No. Operate in the ring Z[i] of Gaussian integers, and let {a,b,c,d} be the Gaussian integers corresponding to the vertices of the square. When you apply the process to obtain {a,2a-b,c,d}, the greatest common divisor (again a Gaussian integer, up to multiplication by the ring units) remains invariant (similar to Euclid's algorithm).
Hence, if they form a square at any time, it must be the same size and orientation as the original square.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
Very nice! And this is why I'm willing to put up with any amount of commentary on microwave ovens. On Jan 29, 2014, at 9:56 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
I think you can do effectively the same thing as Adam without needing ideas like Gaussian integer GCD. Eric's problem asked about forming a new square with size "t" > "s", and that's because it's obvious you can never make a square that's *smaller* than the unit square you started with, as all points you ever get are part of the square lattice with the original square as its unit. But since the point-replacing process is invertible, if it can't give you a smaller square, it can't give you a larger one either.
--Michael
I wrote
Another argument is that if I keep track of a quadrilateral formed by the 4 points, where I think of jumping one point over another as sliding both of them, then the area of this quadrilateral is preserved.
As Bill Cordwell and Veit Elser pointed out to me, this isn't true: we can do two diagonal jumps and make a trapezoid. In some cases the area stays the same if we think of the quadrilateral as folded over, with a hinge between two triangles, but then the argument gets more complicated. Cris On Jan 29, 2014, at 7:56 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
I think you can do effectively the same thing as Adam without needing ideas like Gaussian integer GCD. Eric's problem asked about forming a new square with size "t" > "s", and that's because it's obvious you can never make a square that's *smaller* than the unit square you started with, as all points you ever get are part of the square lattice with the original square as its unit. But since the point-replacing process is invertible, if it can't give you a smaller square, it can't give you a larger one either.
--Michael
On Wed, Jan 29, 2014 at 9:46 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
That's a very beautiful problem. I've appended a short solution to the end of this e-mail.
----- Original Message ----- From: Eric Angelini Sent: 01/29/14 10:30 AM To: math-fun Subject: [math-fun] Jumping square points
Hello Math-Fun, Four points shape a square of size "s". Every minute a point randomly jumps over another point and lands symmetrically behind it. Is it possible that, at some stage, the 4 points shape a new square having size "t" > "s"? Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
***** spoiler alert ***** . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
No. Operate in the ring Z[i] of Gaussian integers, and let {a,b,c,d} be the Gaussian integers corresponding to the vertices of the square. When you apply the process to obtain {a,2a-b,c,d}, the greatest common divisor (again a Gaussian integer, up to multiplication by the ring units) remains invariant (similar to Euclid's algorithm).
Hence, if they form a square at any time, it must be the same size and orientation as the original square.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
Was there a rule that the jump had to be over a nearest point? Brent On 1/29/2014 6:56 AM, Michael Kleber wrote:
I think you can do effectively the same thing as Adam without needing ideas like Gaussian integer GCD. Eric's problem asked about forming a new square with size "t" > "s", and that's because it's obvious you can never make a square that's *smaller* than the unit square you started with, as all points you ever get are part of the square lattice with the original square as its unit. But since the point-replacing process is invertible, if it can't give you a smaller square, it can't give you a larger one either.
--Michael
On Wed, Jan 29, 2014 at 9:46 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
That's a very beautiful problem. I've appended a short solution to the end of this e-mail.
----- Original Message ----- From: Eric Angelini Sent: 01/29/14 10:30 AM To: math-fun Subject: [math-fun] Jumping square points
Hello Math-Fun, Four points shape a square of size "s". Every minute a point randomly jumps over another point and lands symmetrically behind it. Is it possible that, at some stage, the 4 points shape a new square having size "t" > "s"? Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
***** spoiler alert ***** . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
No. Operate in the ring Z[i] of Gaussian integers, and let {a,b,c,d} be the Gaussian integers corresponding to the vertices of the square. When you apply the process to obtain {a,2a-b,c,d}, the greatest common divisor (again a Gaussian integer, up to multiplication by the ring units) remains invariant (similar to Euclid's algorithm).
Hence, if they form a square at any time, it must be the same size and orientation as the original square.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
So I would guess that, starting with four corners of the unit square, you can jump them to precisely the 4-point subsets of Z^2 which are not a subset of a strict sublattice of Z^2?
participants (6)
-
Adam P. Goucher -
Cris Moore -
David Wilson -
meekerdb -
Michael Kleber -
Veit Elser