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