[math-fun] Signed area puzzle
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares. What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges? I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares). Jim Propp
I have one that I think is 117. 00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8. 63 + 35 + 15 + 4 = 117. On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com> wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Wow! That was fast! I verified Alan's claim by writing down all the winding numbers: 11111110 12222221 12333221 12344321 12344321 12333321 11222221 11111111 and checking that they add up to 117. Can anyone beat this, or prove that it's optimal? (Of course n=8 is just a special case; it'd be nice to know the answer for general n.) Jim On Wed, Mar 23, 2016 at 12:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have one that I think is 117.
00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8.
63 + 35 + 15 + 4 = 117.
On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com> wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let's see. If we don't require the curve be connected, then you can trivially achieve the maximum with a set of nested rectangles. In order to connect these, we have to sacrifice at least one square (we have to go "around" a square). It seems Allan's solution does exactly this, connecting at the corners. This is always possible (there are four corners but each rectangle only need connect to two others). There are multiple ways to do this. So I'd say Allan's solution is optimal and generally extensible to arbitrary n. What more did you have in mind, Jim? -tom On Wed, Mar 23, 2016 at 9:30 AM, James Propp <jamespropp@gmail.com> wrote:
Wow! That was fast!
I verified Alan's claim by writing down all the winding numbers:
11111110 12222221 12333221 12344321 12344321 12333321 11222221 11111111
and checking that they add up to 117.
Can anyone beat this, or prove that it's optimal?
(Of course n=8 is just a special case; it'd be nice to know the answer for general n.)
Jim
On Wed, Mar 23, 2016 at 12:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have one that I think is 117.
00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8.
63 + 35 + 15 + 4 = 117.
On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com> wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Maybe I'm misunderstanding Tom, but it seems to me that this is only a heuristic argument, not a proof. More specifically, Tom's argument shows that if you start with the nested rectangles configuration, which has four components, and start trying to connect things up so that it has one component instead of four, you need to connect three times, losing one unit of signed area each time, resulting in a grid-path with signed area 117. But I don't see how this shows that no closed grid-path encloses 118 units of signed area. Jim On Wed, Mar 23, 2016 at 12:43 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let's see. If we don't require the curve be connected, then you can trivially achieve the maximum with a set of nested rectangles.
In order to connect these, we have to sacrifice at least one square (we have to go "around" a square). It seems Allan's solution does exactly this, connecting at the corners. This is always possible (there are four corners but each rectangle only need connect to two others). There are multiple ways to do this.
So I'd say Allan's solution is optimal and generally extensible to arbitrary n.
What more did you have in mind, Jim?
-tom
On Wed, Mar 23, 2016 at 9:30 AM, James Propp <jamespropp@gmail.com> wrote:
Wow! That was fast!
I verified Alan's claim by writing down all the winding numbers:
11111110 12222221 12333221 12344321 12344321 12333321 11222221 11111111
and checking that they add up to 117.
Can anyone beat this, or prove that it's optimal?
(Of course n=8 is just a special case; it'd be nice to know the answer for general n.)
Jim
On Wed, Mar 23, 2016 at 12:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have one that I think is 117.
00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8.
63 + 35 + 15 + 4 = 117.
On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com> wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I can lower my upper bound from 120 to 118, almost (but not quite) closing the gap for n=8. Look at the four concentric rings of squares that make up the 8-by-8 square. Call a ring "full" (relative to a closed grid-path) if the path winds around every cell in the ring the maximum possible number of times (1 for grid-squares in the outermost ring, 2 in the next, 3 in the next, and 4 in the center ring). If any two consecutive rings are full, the grid-path splits up into two components (because an edge belongs to the grid-path precisely if the winding numbers of the two adjacent grid-squares are different). So at least two of the four rings are not full, implying a signed area "deficit" of at least two. Can anyone sharpen this argument to close the gap? Jim On Wed, Mar 23, 2016 at 1:10 PM, James Propp <jamespropp@gmail.com> wrote:
Maybe I'm misunderstanding Tom, but it seems to me that this is only a heuristic argument, not a proof. More specifically, Tom's argument shows that if you start with the nested rectangles configuration, which has four components, and start trying to connect things up so that it has one component instead of four, you need to connect three times, losing one unit of signed area each time, resulting in a grid-path with signed area 117. But I don't see how this shows that no closed grid-path encloses 118 units of signed area.
Jim
On Wed, Mar 23, 2016 at 12:43 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let's see. If we don't require the curve be connected, then you can trivially achieve the maximum with a set of nested rectangles.
In order to connect these, we have to sacrifice at least one square (we have to go "around" a square). It seems Allan's solution does exactly this, connecting at the corners. This is always possible (there are four corners but each rectangle only need connect to two others). There are multiple ways to do this.
So I'd say Allan's solution is optimal and generally extensible to arbitrary n.
What more did you have in mind, Jim?
-tom
On Wed, Mar 23, 2016 at 9:30 AM, James Propp <jamespropp@gmail.com> wrote:
Wow! That was fast!
I verified Alan's claim by writing down all the winding numbers:
11111110 12222221 12333221 12344321 12344321 12333321 11222221 11111111
and checking that they add up to 117.
Can anyone beat this, or prove that it's optimal?
(Of course n=8 is just a special case; it'd be nice to know the answer for general n.)
Jim
On Wed, Mar 23, 2016 at 12:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have one that I think is 117.
00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8.
63 + 35 + 15 + 4 = 117.
On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com> wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let me try again, then. Start with the "optimal" configuration; it is unique. Consider each region of like-marked cells. If it contains a hole (considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected). Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole. The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one. 120-3=117. On Wed, Mar 23, 2016 at 11:05 AM, James Propp <jamespropp@gmail.com> wrote:
I can lower my upper bound from 120 to 118, almost (but not quite) closing the gap for n=8.
Look at the four concentric rings of squares that make up the 8-by-8 square. Call a ring "full" (relative to a closed grid-path) if the path winds around every cell in the ring the maximum possible number of times (1 for grid-squares in the outermost ring, 2 in the next, 3 in the next, and 4 in the center ring). If any two consecutive rings are full, the grid-path splits up into two components (because an edge belongs to the grid-path precisely if the winding numbers of the two adjacent grid-squares are different).
So at least two of the four rings are not full, implying a signed area "deficit" of at least two.
Can anyone sharpen this argument to close the gap?
Jim
On Wed, Mar 23, 2016 at 1:10 PM, James Propp <jamespropp@gmail.com> wrote:
Maybe I'm misunderstanding Tom, but it seems to me that this is only a heuristic argument, not a proof. More specifically, Tom's argument shows that if you start with the nested rectangles configuration, which has four components, and start trying to connect things up so that it has one component instead of four, you need to connect three times, losing one unit of signed area each time, resulting in a grid-path with signed area 117. But I don't see how this shows that no closed grid-path encloses 118 units of signed area.
Jim
On Wed, Mar 23, 2016 at 12:43 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let's see. If we don't require the curve be connected, then you can trivially achieve the maximum with a set of nested rectangles.
In order to connect these, we have to sacrifice at least one square (we have to go "around" a square). It seems Allan's solution does exactly this, connecting at the corners. This is always possible (there are four corners but each rectangle only need connect to two others). There are multiple ways to do this.
So I'd say Allan's solution is optimal and generally extensible to arbitrary n.
What more did you have in mind, Jim?
-tom
On Wed, Mar 23, 2016 at 9:30 AM, James Propp <jamespropp@gmail.com> wrote:
Wow! That was fast!
I verified Alan's claim by writing down all the winding numbers:
11111110 12222221 12333221 12344321 12344321 12333321 11222221 11111111
and checking that they add up to 117.
Can anyone beat this, or prove that it's optimal?
(Of course n=8 is just a special case; it'd be nice to know the answer for general n.)
Jim
On Wed, Mar 23, 2016 at 12:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have one that I think is 117.
00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8.
63 + 35 + 15 + 4 = 117.
On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com
wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Tom, Let me try again, then.
Start with the "optimal" configuration; it is unique.
Alan's solution is unique only up to symmetry. Or are you referring to the disconnected "path" consisting of several square loops? (That would explain the scare-quotes.)
Consider each region of like-marked cells.
Sure; there are four of them. If it contains a hole
(considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected).
I don't understand what you mean here.
Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole.
I see four, not three, such regions.
The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one.
I still don't follow this. Does anyone else?
120-3=117.
Okay, *that* I understand. :-) Jim On Wed, Mar 23, 2016 at 11:05 AM, James Propp <jamespropp@gmail.com> wrote:
I can lower my upper bound from 120 to 118, almost (but not quite) closing the gap for n=8.
Look at the four concentric rings of squares that make up the 8-by-8 square. Call a ring "full" (relative to a closed grid-path) if the path winds around every cell in the ring the maximum possible number of times (1 for grid-squares in the outermost ring, 2 in the next, 3 in the next, and 4 in the center ring). If any two consecutive rings are full, the grid-path splits up into two components (because an edge belongs to the grid-path precisely if the winding numbers of the two adjacent grid-squares are different).
So at least two of the four rings are not full, implying a signed area "deficit" of at least two.
Can anyone sharpen this argument to close the gap?
Jim
On Wed, Mar 23, 2016 at 1:10 PM, James Propp <jamespropp@gmail.com> wrote:
Maybe I'm misunderstanding Tom, but it seems to me that this is only a heuristic argument, not a proof. More specifically, Tom's argument shows that if you start with the nested rectangles configuration, which has four components, and start trying to connect things up so that it has one component instead of four, you need to connect three times, losing one unit of signed area each time, resulting in a grid-path with signed area
But I don't see how this shows that no closed grid-path encloses 118 units of signed area.
Jim
On Wed, Mar 23, 2016 at 12:43 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let's see. If we don't require the curve be connected, then you can trivially achieve the maximum with a set of nested rectangles.
In order to connect these, we have to sacrifice at least one square (we have to go "around" a square). It seems Allan's solution does exactly this, connecting at the corners. This is always possible (there are four corners but each rectangle only need connect to two others). There are multiple ways to do this.
So I'd say Allan's solution is optimal and generally extensible to arbitrary n.
What more did you have in mind, Jim?
-tom
On Wed, Mar 23, 2016 at 9:30 AM, James Propp <jamespropp@gmail.com> wrote:
Wow! That was fast!
I verified Alan's claim by writing down all the winding numbers:
11111110 12222221 12333221 12344321 12344321 12333321 11222221 11111111
and checking that they add up to 117.
Can anyone beat this, or prove that it's optimal?
(Of course n=8 is just a special case; it'd be nice to know the answer for general n.)
Jim
On Wed, Mar 23, 2016 at 12:17 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have one that I think is 117.
00 e8 n7 w7 s5 e5 n3 w3 s2 e2 n3 w3 s5 e5 n7 w7 s8.
63 + 35 + 15 + 4 = 117.
On Wed, Mar 23, 2016 at 10:24 AM, James Propp < jamespropp@gmail.com
wrote:
> Every closed path on a square grid has a "signed area" equal to the sum of > the winding numbers around the grid squares. > > What is the maximum possible signed area of a closed grid-path that lives > in [0,8]x[0,8] and doesn't re-use any edges? > > I found one with signed area 114; is this best possible? An easy upper > bound is 120 (the sum of the upper bounds on the individual winding numbers > associated with the 64 grid squares). > > Jim Propp > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It might be best if in continuing our discussion of the 8-by-8 case we switched over to the general 2k-by-2k case. That might clarify some aspects of the discussion. Jim On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Tom,
Let me try again, then.
Start with the "optimal" configuration; it is unique.
Alan's solution is unique only up to symmetry. Or are you referring to the disconnected "path" consisting of several square loops? (That would explain the scare-quotes.)
Consider each region of like-marked cells.
Sure; there are four of them.
If it contains a hole
(considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected).
I don't understand what you mean here.
Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole.
I see four, not three, such regions.
The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one.
I still don't follow this. Does anyone else?
120-3=117.
Okay, *that* I understand. :-)
Jim
Naturally, I wondered about the same problem on an NxN-grid torus. In this case, I can make sense of the winding number of a closed path about a grid square only if it can be shrunk to a point on the torus (i.e., is "null-homotopic"). Or is there a satisfactory definition in other cases? But there are still many null-homotopic closed paths on the torus that would not exist on the square. Is the answer the same, say, in the 8x8 case? —Dan
On Mar 23, 2016, at 2:48 PM, James Propp <jamespropp@gmail.com> wrote:
It might be best if in continuing our discussion of the 8-by-8 case we switched over to the general 2k-by-2k case. That might clarify some aspects of the discussion.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Tom,
Let me try again, then.
Start with the "optimal" configuration; it is unique.
Alan's solution is unique only up to symmetry. Or are you referring to the disconnected "path" consisting of several square loops? (That would explain the scare-quotes.)
Consider each region of like-marked cells.
Sure; there are four of them.
If it contains a hole
(considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected).
I don't understand what you mean here.
Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole.
I see four, not three, such regions.
The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one.
I still don't follow this. Does anyone else?
120-3=117.
Okay, *that* I understand. :-)
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let me try again, then.
Start with the "optimal" configuration; it is unique.
Alan's solution is unique only up to symmetry. Or are you referring to the disconnected "path" consisting of several square loops? (That would explain the scare-quotes.)
I mean optimal configuration that does not require connectedness of the surrounding path; that is, the nested rectangle configuration.
If it contains a hole (considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected).
All the cells with 1 in them form a border around the cells with 2 in them, which form a border around the cells with 3, which form a border around the cells with 4. A chess king cannot get from a cell with 1 to a cell with 3 without stepping on a 2; the 3's (and 4's) live in a hole in the surface of 2's. Thus, the edges included in the solution that are outside the 2's cannot be connected to the edges that are inside the 2's. If the chess king can get from 2 to 4 without stepping on 3, that means that the edges on the inside of the 2's and those on the outside are connected.
Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole.
I see four, not three, such regions.
The regions are those with 1's, 2's, and 3's. The region with 4's does not contain a hole; there are no interior edges that need to be connected to the outside edges.
The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one.
All this confusion is my fault for not defining what I meant by "optimal configuration". -tom
I'm still confused by your argument, but rather than focus on specific passages that I don't follow I'd rather take a global approach. What would you say is the general situation for a 2k-by-2k grid? What is the minimal number of grid-squares that don't achieve maximal winding number? Is it k/2+1, or k-1, or something else? Jim On Wednesday, March 23, 2016, Tom Rokicki <rokicki@gmail.com> wrote:
Let me try again, then.
Start with the "optimal" configuration; it is unique.
Alan's solution is unique only up to symmetry. Or are you referring to
the
disconnected "path" consisting of several square loops? (That would explain the scare-quotes.)
I mean optimal configuration that does not require connectedness of the surrounding path; that is, the nested rectangle configuration.
If it contains a hole (considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected).
All the cells with 1 in them form a border around the cells with 2 in them, which form a border around the cells with 3, which form a border around the cells with 4. A chess king cannot get from a cell with 1 to a cell with 3 without stepping on a 2; the 3's (and 4's) live in a hole in the surface of 2's. Thus, the edges included in the solution that are outside the 2's cannot be connected to the edges that are inside the 2's. If the chess king can get from 2 to 4 without stepping on 3, that means that the edges on the inside of the 2's and those on the outside are connected.
Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole.
I see four, not three, such regions.
The regions are those with 1's, 2's, and 3's. The region with 4's does not contain a hole; there are no interior edges that need to be connected to the outside edges.
The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one.
All this confusion is my fault for not defining what I meant by "optimal configuration".
-tom _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It's k-1. On Wed, Mar 23, 2016 at 4:26 PM, James Propp <jamespropp@gmail.com> wrote:
I'm still confused by your argument, but rather than focus on specific passages that I don't follow I'd rather take a global approach.
What would you say is the general situation for a 2k-by-2k grid? What is the minimal number of grid-squares that don't achieve maximal winding number? Is it k/2+1, or k-1, or something else?
Jim
On Wednesday, March 23, 2016, Tom Rokicki <rokicki@gmail.com> wrote:
Let me try again, then.
Start with the "optimal" configuration; it is unique.
Alan's solution is unique only up to symmetry. Or are you referring to
the
disconnected "path" consisting of several square loops? (That would explain the scare-quotes.)
I mean optimal configuration that does not require connectedness of the surrounding path; that is, the nested rectangle configuration.
If it contains a hole (considering connectivity by N/S/E/W and not by diagonal), then the circuit is not closed (the used edges are not connected).
All the cells with 1 in them form a border around the cells with 2 in them, which form a border around the cells with 3, which form a border around the cells with 4. A chess king cannot get from a cell with 1 to a cell with 3 without stepping on a 2; the 3's (and 4's) live in a hole in the surface of 2's. Thus, the edges included in the solution that are outside the 2's cannot be connected to the edges that are inside the 2's. If the chess king can get from 2 to 4 without stepping on 3, that means that the edges on the inside of the 2's and those on the outside are connected.
Since there are three such regions (with holes), we need to modify at least one cell in each of these three regions to eliminate the hole.
I see four, not three, such regions.
The regions are those with 1's, 2's, and 3's. The region with 4's does not contain a hole; there are no interior edges that need to be connected to the outside edges.
The only modification we can make to the optimal configuration is to *decrease* the winding number of a cell by one.
All this confusion is my fault for not defining what I meant by "optimal configuration".
-tom _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
I should mention that my solution for an 8-by-8 square is a special case of a more general spiral construction that, for n = 1, 2, 3, ..., yields a grid-path in [0,n]x[0,n] with signed area 1, 4, 9, 19, 32, 53, 78, 114, 155, 210, ... This is not itself in OEIS, but it is an alternation between two sequences, both of which are given by third-degree polynomials in n, and one of which does occur in the OEIS, under the name "house numbers" (or is it "House numbers"?). But I do not know whether this spiral construction is optimal. Jim Propp On Wed, Mar 23, 2016 at 10:24 AM, James Propp <jamespropp@gmail.com> wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
I found one with signed area 114; is this best possible? An easy upper bound is 120 (the sum of the upper bounds on the individual winding numbers associated with the 64 grid squares).
Jim Propp
On 23/03/2016 14:24, James Propp wrote:
Every closed path on a square grid has a "signed area" equal to the sum of the winding numbers around the grid squares.
What is the maximum possible signed area of a closed grid-path that lives in [0,8]x[0,8] and doesn't re-use any edges?
The following observation (which may already have been obvious to you, in which case I apologize) may help to clarify arguments like Tom R's: The per-square winding numbers completely determine the lines and directions of the grid path: wherever you have two adjacent squares with equal PSWN there is no path-segment between them; wherever you have two with PSWN differing by 1 there is a path-segment with the higher-PSWN square on its left; there cannot be two with PSWN differing by more than 1. -- g
I wrote:
The following observation (which may already have been obvious to you, in which case I apologize) may help to clarify arguments like Tom R's: The per-square winding numbers completely determine the lines and directions of the grid path: wherever you have two adjacent squares with equal PSWN there is no path-segment between them; wherever you have two with PSWN differing by 1 there is a path-segment with the higher-PSWN square on its left; there cannot be two with PSWN differing by more than 1.
Let me elaborate on this a little and see whether the result is a version of Tom's argument that Jim finds more acceptable. 1. Construct the optimal configuration when a disconnected path is permitted. This is the "obvious" thing with nested rectangles, because there just isn't space to wind more times around any individual square than you get in this configuration. 2. Obviously we cannot simply say "suppose the optimum actually-feasible path is obtained by small modifications to this infeasible optimum" without further justification. 3. But the justification we need is not hard to find. Consider those per-square winding numbers for the actual optimum. They are squarewise <= those for the infeasible optimum. And (see above) the PSWNs determine the path, as well as vice versa. So the question is: among all ways to reduce the PSWNs, what is the smallest reduction that yields a configuration corresponding to an actual path? 4. Whatever that reduction is, we can imagine doing it one square (and one unit of winding for that square) at a time. When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square. 5. For a 2k-by-2k square, we begin with k path components. If the sum of PSWNs is j less than for the infeasible optimum, by #4 we have at least k-j components at the end. So if we end up with just one component, we must have j >= k-1. 6. We can in fact achieve j = k-1, by Tom's construction. This is therefore the actual optimum. (I have contributed no actual mathematics here, I think; just expressed Tom's idea a bit differently. Jim, does it help?) -- g
Thanks for taking the time to clarify, Gareth. 4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array 010 101 010 (four separate loops) and the PSWN array 010 111 010 (a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3. I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-) Jim
I expect that Gareth and Tom will find my remarks about 010 111 010 obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered. Jim On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
Actually, I goofed last night: what I had in mind was a comparison of 101 000 101 ("before") and 101 010 101 ("after"). The intuition behind my example will be clearer if I explain these arrays as (grid-)multipaths. Label the nine vertices as ABCD EFGH JKLM NOPQ (I left out "I" because it's so narrow, since so many of us use non-fixed-width mail-readers). Start with a 4-component multipath consisting of the closed paths AEFBA, JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. We get the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding number around the center square has changed. (I hope I got it right this time!) Anyway, the multipath changes from having four components to having just one component. (Unless Tom and Gareth are using a different definition of components.) Anyway, in addition to wanting to understand better why there must be at least k-1 grid-squares at which single-component pattern doesn't achieve maximal winding number, I'd like to know the constraints on the locations of those grid-squares. In Allan's example, the grid-squares were all on the same diagonal. Is that forced by Tom and Gareth's analysis (which I'm still trying to understand)? Jim On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp@gmail.com> wrote:
I expect that Gareth and Tom will find my remarks about
010 111 010
obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
It's also interesting to look at my example going in the reverse direction, from 101 010 101 to 101 000 101. The central square starts out with winding-number x=1, unlike its four neighbors, which start out with winding-number x-1. When we reduce the winding-number at the middle from x to x-1, we turn a 1-component picture into a 4-component picture. Right? (Actually, maybe Tom and Gareth would call the initial picture a 2-component picture, but either way, the number of components goes UP, and by more than 1.) This makes it hard for me to understand the passage "Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing." Jim On Thu, Mar 24, 2016 at 9:03 AM, James Propp <jamespropp@gmail.com> wrote:
Actually, I goofed last night: what I had in mind was a comparison of
101 000 101
("before") and
101 010 101
("after"). The intuition behind my example will be clearer if I explain these arrays as (grid-)multipaths. Label the nine vertices as
ABCD EFGH JKLM NOPQ
(I left out "I" because it's so narrow, since so many of us use non-fixed-width mail-readers).
Start with a 4-component multipath consisting of the closed paths AEFBA, JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. We get the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding number around the center square has changed. (I hope I got it right this time!) Anyway, the multipath changes from having four components to having just one component. (Unless Tom and Gareth are using a different definition of components.)
Anyway, in addition to wanting to understand better why there must be at least k-1 grid-squares at which single-component pattern doesn't achieve maximal winding number, I'd like to know the constraints on the locations of those grid-squares. In Allan's example, the grid-squares were all on the same diagonal. Is that forced by Tom and Gareth's analysis (which I'm still trying to understand)?
Jim
On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp@gmail.com> wrote:
I expect that Gareth and Tom will find my remarks about
010 111 010
obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
Okay, the proof as I see it has these components: 1. There's an optimal configuration without the connectedness requirement that consists of k nested squares; each square is a closed edge path. 2. There's an existing construction (due to Allan) that makes slight perturbations to this (k-1 changes to link the k edge rings on a 2k x 2k board). This construction also makes the edges connected, with even degree on each point, so there's a Hamiltonian path with strictly clockwise (or counterclockwise) directions. This construction simply decreases the PSWN on k-1 cells from which the edge changes can be derived. 3. In order to link an edge path to another, where the first lies entirely inside the second, we need to change at least one cell that is inside the first edge path and outside the other. If there is one edge path not connected to but entirely inside the another edge path, then there's a set of cells with the same PSWN that separate the two edge paths. 4. Since there are k unconnected nested rectangles to link, we need to make at least k-1 cell changes to link them. By (2) we know how to do this. On Thu, Mar 24, 2016 at 6:12 AM, James Propp <jamespropp@gmail.com> wrote:
It's also interesting to look at my example going in the reverse direction, from
101 010 101
to
101 000 101.
The central square starts out with winding-number x=1, unlike its four neighbors, which start out with winding-number x-1. When we reduce the winding-number at the middle from x to x-1, we turn a 1-component picture into a 4-component picture. Right? (Actually, maybe Tom and Gareth would call the initial picture a 2-component picture, but either way, the number of components goes UP, and by more than 1.)
This makes it hard for me to understand the passage "Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing."
Jim
On Thu, Mar 24, 2016 at 9:03 AM, James Propp <jamespropp@gmail.com> wrote:
Actually, I goofed last night: what I had in mind was a comparison of
101 000 101
("before") and
101 010 101
("after"). The intuition behind my example will be clearer if I explain these arrays as (grid-)multipaths. Label the nine vertices as
ABCD EFGH JKLM NOPQ
(I left out "I" because it's so narrow, since so many of us use non-fixed-width mail-readers).
Start with a 4-component multipath consisting of the closed paths AEFBA, JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. We get the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding number around the center square has changed. (I hope I got it right this time!) Anyway, the multipath changes from having four components to having just one component. (Unless Tom and Gareth are using a different definition of components.)
Anyway, in addition to wanting to understand better why there must be at least k-1 grid-squares at which single-component pattern doesn't achieve maximal winding number, I'd like to know the constraints on the locations of those grid-squares. In Allan's example, the grid-squares were all on the same diagonal. Is that forced by Tom and Gareth's analysis (which I'm still trying to understand)?
Jim
On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp@gmail.com> wrote:
I expect that Gareth and Tom will find my remarks about
010 111 010
obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
I think the proof sketch by Tom can probably be rigorized, but at this moment I think I see a tacit assumption that is not justified by the stated argument. It is that *any optimal single-path solution can be derived by "cell demotion" from the optimal multiple-path solution*. The sketch as currently presented ignores the philosophical possibility that there is a magical single-path solution that is *not* connected by cell-demotion with the nested-square configuration. I find it very hard, intuitively, to believe that such magical solutions exist, but I don't immediately see a demonstration that they don't. On Thu, Mar 24, 2016 at 2:03 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Okay, the proof as I see it has these components:
1. There's an optimal configuration without the connectedness requirement that consists of k nested squares; each square is a closed edge path.
2. There's an existing construction (due to Allan) that makes slight perturbations to this (k-1 changes to link the k edge rings on a 2k x 2k board). This construction also makes the edges connected, with even degree on each point, so there's a Hamiltonian path with strictly clockwise (or counterclockwise) directions. This construction simply decreases the PSWN on k-1 cells from which the edge changes can be derived.
3. In order to link an edge path to another, where the first lies entirely inside the second, we need to change at least one cell that is inside the first edge path and outside the other. If there is one edge path not connected to but entirely inside the another edge path, then there's a set of cells with the same PSWN that separate the two edge paths.
4. Since there are k unconnected nested rectangles to link, we need to make at least k-1 cell changes to link them. By (2) we know how to do this.
On Thu, Mar 24, 2016 at 6:12 AM, James Propp <jamespropp@gmail.com> wrote:
It's also interesting to look at my example going in the reverse direction, from
101 010 101
to
101 000 101.
The central square starts out with winding-number x=1, unlike its four neighbors, which start out with winding-number x-1. When we reduce the winding-number at the middle from x to x-1, we turn a 1-component picture into a 4-component picture. Right? (Actually, maybe Tom and Gareth would call the initial picture a 2-component picture, but either way, the number of components goes UP, and by more than 1.)
This makes it hard for me to understand the passage "Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing."
Jim
On Thu, Mar 24, 2016 at 9:03 AM, James Propp <jamespropp@gmail.com> wrote:
Actually, I goofed last night: what I had in mind was a comparison of
101 000 101
("before") and
101 010 101
("after"). The intuition behind my example will be clearer if I explain these arrays as (grid-)multipaths. Label the nine vertices as
ABCD EFGH JKLM NOPQ
(I left out "I" because it's so narrow, since so many of us use non-fixed-width mail-readers).
Start with a 4-component multipath consisting of the closed paths AEFBA, JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. We get the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding number around the center square has changed. (I hope I got it right this time!) Anyway, the multipath changes from having four components to having just one component. (Unless Tom and Gareth are using a different definition of components.)
Anyway, in addition to wanting to understand better why there must be at least k-1 grid-squares at which single-component pattern doesn't achieve maximal winding number, I'd like to know the constraints on the locations of those grid-squares. In Allan's example, the grid-squares were all on the same diagonal. Is that forced by Tom and Gareth's analysis (which I'm still trying to understand)?
Jim
On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp@gmail.com> wrote:
I expect that Gareth and Tom will find my remarks about
010 111 010
obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it
one square (and one unit of winding for that square) at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think I can fill the gap that Allan refers to in the last part of his message. The key insight is that an array of numbers corresponds to a multipath if it only if numbers in adjacent cells differ by at most 1. (BTW, it's probably best to imagine a ring of zeros at the frontier of the array; it follows that all the numbers in the next ring must be 1s and 0s.) This means that we can demote cells in numerical order, from largest to smallest (subject to the constraint that we stop demoting a cell when it achieves its target value), without ever violating the "Lipschitz constraint". More details upon request for anyone who wants them. What I still don't get is why each demotion decreases the number of components by at most 1. Come to think of it, I'm not even sure what the right definition of number-of-components should be in order to make such a claim true. Jim On Thursday, March 24, 2016, Allan Wechsler <acwacw@gmail.com> wrote:
I think the proof sketch by Tom can probably be rigorized, but at this moment I think I see a tacit assumption that is not justified by the stated argument. It is that *any optimal single-path solution can be derived by "cell demotion" from the optimal multiple-path solution*. The sketch as currently presented ignores the philosophical possibility that there is a magical single-path solution that is *not* connected by cell-demotion with the nested-square configuration. I find it very hard, intuitively, to believe that such magical solutions exist, but I don't immediately see a demonstration that they don't.
On Thu, Mar 24, 2016 at 2:03 PM, Tom Rokicki <rokicki@gmail.com <javascript:;>> wrote:
Okay, the proof as I see it has these components:
1. There's an optimal configuration without the connectedness requirement that consists of k nested squares; each square is a closed edge path.
2. There's an existing construction (due to Allan) that makes slight perturbations to this (k-1 changes to link the k edge rings on a 2k x 2k board). This construction also makes the edges connected, with even degree on each point, so there's a Hamiltonian path with strictly clockwise (or counterclockwise) directions. This construction simply decreases the PSWN on k-1 cells from which the edge changes can be derived.
3. In order to link an edge path to another, where the first lies entirely inside the second, we need to change at least one cell that is inside the first edge path and outside the other. If there is one edge path not connected to but entirely inside the another edge path, then there's a set of cells with the same PSWN that separate the two edge paths.
4. Since there are k unconnected nested rectangles to link, we need to make at least k-1 cell changes to link them. By (2) we know how to do this.
On Thu, Mar 24, 2016 at 6:12 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
It's also interesting to look at my example going in the reverse direction, from
101 010 101
to
101 000 101.
The central square starts out with winding-number x=1, unlike its four neighbors, which start out with winding-number x-1. When we reduce the winding-number at the middle from x to x-1, we turn a 1-component picture into a 4-component picture. Right? (Actually, maybe Tom and Gareth would call the initial picture a 2-component picture, but either way, the number of components goes UP, and by more than 1.)
This makes it hard for me to understand the passage "Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing."
Jim
On Thu, Mar 24, 2016 at 9:03 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Actually, I goofed last night: what I had in mind was a comparison of
101 000 101
("before") and
101 010 101
("after"). The intuition behind my example will be clearer if I explain these arrays as (grid-)multipaths. Label the nine vertices as
ABCD EFGH JKLM NOPQ
(I left out "I" because it's so narrow, since so many of us use non-fixed-width mail-readers).
Start with a 4-component multipath consisting of the closed paths AEFBA, JNOKJ, LPQML, and CGHDC. Now add the four edges FK, KL, LG, and GF. We get the 1-component path AEFKJNOKLPQMLGHDCGFBA, and only the winding number around the center square has changed. (I hope I got it right this time!) Anyway, the multipath changes from having four components to having just one component. (Unless Tom and Gareth are using a different definition of components.)
Anyway, in addition to wanting to understand better why there must be at least k-1 grid-squares at which single-component pattern doesn't achieve maximal winding number, I'd like to know the constraints on the locations of those grid-squares. In Allan's example, the grid-squares were all on the same diagonal. Is that forced by Tom and Gareth's analysis (which I'm still trying to understand)?
Jim
On Thu, Mar 24, 2016 at 7:03 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
I expect that Gareth and Tom will find my remarks about
010 111 010
obtuse and irrelevant, since local configurations like that won't occur as one successively mutates the array (starting from the maximal array and lowering k-1 entries one at a time). But how do we KNOW they won't? Clearly Tom and Gareth have some additional intuitions about what's going on here that aren't captured by the analyses they've offered.
Jim
On Wednesday, March 23, 2016, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Thanks for taking the time to clarify, Gareth.
4. Whatever that reduction is, we can imagine doing it > one square (and one unit of winding for that square) > at a time.
This is not obvious to me, but I can prove it. (You have to decrement the larger numbers first.)
> When we reduce one PSWN by 1, the number > of path components cannot reduce by more than one -- > for we cannot have components of more than two > disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
I'll mention Allan Wechsler here, for no reason other than the fact that I seem to keep misspelling his first name and could use some practice spelling it right. Allan, Allan, Allan. There! Let's see if that helps. :-)
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's an almost complete proof, using ingredients from Tom's proof (but discarding #4). First argue that there must be a way to turn the initial "nested squares" multipath configuration into a maximal single-path configuration via successive demotions (see my previous email). Then, claim that at least one cell in each of the k-1 outermost rings must be demoted in the process. For, if not, then we'd get a non-simply-connected band of cells of constant winding-number at the end of the process, which would disconnect the multipath into two parts (one "outer" and one "inner"). The only gap I see here is, why couldn't the outer part or the inner part of the maximal single-path configuration be empty? The answer must be, This woud contradict maximality! I think I see a way to fill the gap (two cases: one for the outer part and one for the inner part). The first I'm 90% sure of; the second I'm less sure of. My approach is kind of fiddly. Can anyone find a more conceptual way of wrapping up the proof? Jim
On 24/03/2016 03:41, James Propp wrote:
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
It looks to me as if your first array has two loops, one clockwise and one anticlockwise. So I don't think this is a counterexample. But it does suggest a way to make one, because if we have a pattern like this 2 0 1 0 2 it implies four disconnected paths around the central square. They are pairwise *touching*, but fail to connect, which of course is the possibility my "proof" fails to consider. I wondered briefly whether there might be some impossibility about actually fitting this into a complete configuration, but it's pretty easy; e.g., with these PSWNs: 1 1 1 1 1 1 1 2 1 1 1 0 1 0 1 1 1 2 1 1 1 1 1 1 1 corresponding to a single anticlockwise loop on the outside, and two loops in each direction inside. Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing. And it *is* true that a single square of PSWN x can be adjacent to at most two other squares with PSWN x-1. (Because if two such squares meet at a corner then their path components are not in fact disconnected.) -- g
participants (5)
-
Allan Wechsler -
Dan Asimov -
Gareth McCaughan -
James Propp -
Tom Rokicki