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