The Sierpinski walk

[HalfThere]

Given two points on a Sierpinski carpet (http://en.wikipedia.org/wiki/Sierpinski_carpet), what is the minimum distance that must be traveled to get from one to the other.

edit: yes, you must stay within the closed set of the carpet - no skipping over holes, or you will be swallowed by the abyss.

I have no hints for you - you must rely on your own ingenuity.

Solution thread

[Blatm]

Spoiler:

Given two points on the Sierpinski carpet at (a,b) and (c,d), the distance between them is \sqrt{(a-c)^2 + (b-d)^2}.

[jaap]

Spoiler:

Given two points on the Sierpinski carpet at (a,b) and (c,d), the distance between them is \sqrt{(a-c)^2 + (b-d)^2}.

I think the OP omitted to say that the path you travel must stay within the carpet. The direct line generally will go over holes.

At first I though it would be the manhattan distance between the points, but it is not because

Spoiler:

there are other straight lines that lie fully on the carpet (if it is a closed set - if not you can get arbitrarily close to the straight line). Those lines I found have slope 2, -2, 1/2, or -1/2.

[notzeb]

It can't be the Manhattan distance for an even more obvious reason:

Spoiler:

Consider two points at the middle of the left and right sides of the middle square of the Carpet!

Whatever the distance is, it's probably an extremely nonlinear function. It probably has to do with the base three representations of the coordinates, I'd suggest working out exactly what the function is for just a square with one middle square removed is first (then expressing that as a computation on the base three representation, and inducting).

Spoiler:

Hmmm. Thinking about this, I first thought to wonder what the distance between the upper left and bottom right corner is. Based on the previous poster, I just realized it's 2/3sqrt(5). We can use this to get an argument for the distance from the upper left to any point in the carpet, I think: draw the line connecting the upper left to our point, find the biggest square intersecting that line, choose a corner of that square, and first travel directly to that corner and then work out a path from that corner to your destination?

Edit: should we be making a solution thread?

[Poohblah]

Spoiler:

Since the fractal continues infinitely, it seems to me that it's only possible to move horizontally and vertically, not diagonally. So it would seem that the distance would be twice the length of one side. Then again, I hardly know anything about the Sierpinski carpet.

[Qaanol]

Spoiler:

Whatever the distance is, it's probably an extremely nonlinear function. It probably has to do with the base three representations of the coordinates, I'd suggest working out exactly what the function is for just a square with one middle square removed is first (then expressing that as a computation on the base three representation, and inducting).

Spoiler:

The Sierpinski Carpet is the set of points (x, y) such that in base 3, for each integer k, the k'th digit of x and the k'th digit of y are not both 1.

[jestingrabbit]

The Sierpinski Carpet is the set of points (x, y) such that in base 3, for each integer k, the k'th digit of x and the k'th digit of y are not both 1.

Not quite, for instance, the point (1/3, 1/3) is on the carpet, but the first digit of both those numbers is 1. You need either that the kth digit of x and y are never both 1, or that they are both one and one of them then has every digit subsequent digit be 0.

Also, only spoiler stuff that is actualy solutiony type stuff. Its not necessary to put commonly known facts that assist in explaining the problem in spoilers.

[Cosmologicon]

And I thought the whole point of having a separate solution thread was so that we wouldn't have to spoiler anything at all.

[jestingrabbit]

Yes indeed. The whole point of the solution thread is so that when someone wants to write a whole or partial solution, they can post it there unspoilered, whereas here in the problem thread we can discuss the basics of the problem, mention lines of inquiry that we are attempting, and clarify the problem.

So, no spoiler tags, so no having to click spoiler buttons. But the cost for this having to go back and forth between this thread and the solution thread, depending on what you want to post.

I figure that even partial solutions to this one aren't going to be two or three lines, more likely two or three pages.

[afarnen]

I'm confused as to how you can define a point on the Sierpinski carpet, when there are actually no points on it. What I mean is with enough iterations of the fractal, any chosen point can be proven to be not on the Sierpinski carpet, so if you're considering the fractal iterated ad infinitum, there are actually no points on it.

EDIT: Although I guess since, some points would require an infinite amount of iterations to be proven not on the carpet, such as (1/3, 1/3) (the top-left corner of the largest square), there is a clearer notion of points "on" the carpet. Is that what is meant? Am I totally off-track here?

[jaap]

EDIT: Although I guess since, some points would require an infinite amount of iterations to be proven not on the carpet, such as (1/3, 1/3) (the top-left corner of the largest square), there is a clearer notion of points "on" the carpet. Is that what is meant? Am I totally off-track here?

There is no iteration where (1/3,1/3) is removed, therefore the carpet (the limit of those iterations, or really the intersection of all those iterations) will still contain that point.

Take a look at the Cantor Set. The Sierpinski carpet is like a 2-dimensional version of that. If x and y are two points on a Cantor set, then the Sierpinski carpet will certainly contain (x,y). For example the not so obvious (1/4, 1/4). The carpet actually contains other points too, for example (1/2,1/3).

[afarnen]

There is no iteration where (1/3,1/3) is removed, therefore the carpet (the limit of those iterations, or really the intersection of all those iterations) will still contain that point.

So that mean only points which are on the edges of square holes are actually on the carpet? Otherwise it can be removed in a definite amount of iterations.

[jaap]

So that mean only points which are on the edges of square holes are actually on the carpet? Otherwise it can be removed in a definite amount of iterations.

(1/4,1/4) is not on the edge of a square of any iteration, but it is in the set.

[EricSeverson]

Is there any way of identifying the points (such as 1/4) that stay in the carpet even though they are not on an edge?
Is there a way to mathematically prove that 1/4 will always stay on the carpet?

[phlip]

Yes, and yes. The aforementioned Wikipedia page for the Cantor set is a good starting point, since that's a similar fractal in one dimension...

But here's the reasoning being (1/4,1/4) being in the set:

In the first iteration, we remove the centre ninth of the square... obviously, that doesn't include (1/4,1/4).

Next iteration, (1/4,1/4) is in the bottom left square (I'm using (0,0) as the bottom-left corner, (1,1) as the top-right). So if we map it to the coordinates of that square (so (1,1) is now the top-right corner of that square), we're looking at (3/4,3/4).

So next iteration, it's in the top right square... jump to the coordinates within that square, and our point is at (1/4,1/4) again, and back in the bottom left square again. And the cycle continues with each iteration.

So every iteration it's either in the bottom left or top right square, never the middle one... so it's never removed. So it's in the final set.

[edit] Rearranged post a bit to remove the spoiler tags... I misread earlier and thought we were still spoilering stuff about the properties of the carpet. One of the few bad things about Lynx: it doesn't make it as obvious what's a spoiler and what isn't.

[jestingrabbit]

Is there any way of identifying the points (such as 1/4) that stay in the carpet even though they are not on an edge?
Is there a way to mathematically prove that 1/4 will always stay on the carpet?

Sure, just think about the description that I gave earlier.

You need either that the kth digit of x and y are never both 1, or that they are both one and one of them then has every digit subsequent digit be 0.

To expand on that, start by writing elements of the carpet as ordered pairs (x,y) and represent each point with its ternary expansion ie write

x = \sum_{n=1}^{\infty} \frac{x_n}{3^n}

where each of the x_n's are 0, 1 or 2 and we disallow the sequence terminating with recurring 2's (in much the same way that we rule out recurring 9's in decimal).

Now notice that the carpet can be formed by a sequence of deletions from the unit square. Note that, for instance, we first delete the middle square, but not the border of that square. More precisely, we delete those points (x,y) which are such that the ternary expansions of x and y both begin with a 1 and which are such that neither the x nor y are 0.1 (in ternary).

We keep making these deletions, deleting those points (x,y) which are such that the ternary expansions of x and y both have a 1 in the kth position, and which are such that neither the ternary expansion of x nor y terminates at the kth trit (like a bit or digit, but in ternary).

Now consider what the point (1/4, 1/4) looks like when we write it in ternary. 1/4 = 0.0202020202... . Its trits are never 1, so it is never deleted. Likewise, any point in the plane whose trits are never both 1 are never deleted.

Furthermore, you can see that if a point is on the border of a square, then the ternary expansion of one of its coordinates must terminate. Its a little more complicated than that, because, for instance, the point (1/3, 1/4) is not on a border, and nor is it deleted. But the actual condition is pretty tedious.

--

re the actual problem. The shortest length path between two points will consist of a possibly bi infinite collection of intervals between points of the form \left( \frac{j}{2\cdot 3^n}, \frac{k}{2\cdot 3^n}\right) but its not clear what points to pick yet.

[dedalus]

I guess there's probably a higher-level maths way of doing this, but I'm only first year uni so this will have to go to a geometric solution from me...
The first point I'd have to make is that there really is no correlation between the distance of the two points in the cartesian plane and the distance in the sierpinski plane. In fact, I'm not even sure if you can adapt cartesian-style distance methods to this at all because it's just that different, but anyway.

The two ways that strike me as reasonable to find a solution is to form one top down or bottom up. Either way requires looking at the first iteration of a sierpinski square:

Bottom up: If we consider a first-iteration sierpinski square with sides of 3dx, then the distance from one corner to the opposite corner is a=2\sqrt{5}dx. The distance from halfway along a line to either of the opposite corners is b=\frac{3\sqrt{5}}{2}dx. If we now consider an iteration above that (i.e. a 2nd-iteration sierpinski square with sides of 9dx), then the distance from corner to corner is 4b, and the distance from halfway along a line to the opposing corner is 3b. I'm not that sure how to go about iterating this infinitely as x->0 though. And, it would have to be adapted so as to work from every point rather then just between the set corners of a square.

Top down works much the same, except if you consider that the unit square has the dimensions of 4b from one corner to the other, and then work down from there.

Anyway, I hope that helps someone.

[quintopia]

What if we limit ourselves to points that are the corner of some square? Then, a recursive solution might work. However, it will still be messy.

[EricSeverson]

So i was thinking about the diagonal lines that are on the carpet that jaap was talking about. Basically they forms a 8-pointed star that hits every corner and midpoint.

Then of course this same design would be repeated in each of the 8 subsets, and each of those subset's subset's and so on...

But are there any other diagonal lines contained on the carpet that have slopes other than +/- 1/2 or 2 ?

Also, are there any points contained on the carpet that are not contained on a line through the carpet?

[quintopia]

But are there any other diagonal lines contained on the carpet that have slopes other than +/- 1/2 or 2 ?

Yes. Vertical and horizontal line segments.

Also, are there any points contained on the carpet that are not contained on a line through the carpet?

If you can find a point where either incrementing or decrementing either the x or y value would move outside the set, then the answer is yes. I have a hunch that the answer is no.

[phlip]

(1/8,3/8) is on the carpet, but isn't on any horizontal or vertical line segment... that's (0.\overline{01}_3, 0.\overline{10}_3). I'm not sure about diagonal line segments, though... I don't really have a good grasp of what they look like.

[quintopia]

(1/8,3/8) is on the carpet, but isn't on any horizontal or vertical line segment... that's (0.\overline{01}_3, 0.\overline{10}_3). I'm not sure about diagonal line segments, though... I don't really have a good grasp of what they look like.

It's the same issue, you just need to take any point that satisfies that property (the point you found) and check whether incrementing or decrementing one by one amount and the other by twice that amount always moves outside the set.

[phlip]

Ok then, (1/8,3/8) isn't on any line segments with gradient 2 or 1/2 either...

For any horizontal open interval containing (1/8,3/8), there is a point:
0.0101...0101110101...₃ = 1/8 + 1/3ⁿ (for some odd n)
0.1010...1010101010...₃ = 3/8
(Where the first ... represents "sufficiently many" finite repetitions... more repetitions the higher n is... with a higher n for a shorter interval, any interval will contain this point for a sufficiently high n; the second ... represents infinite repetitions)
That'll be in the interval, and isn't in the set. Vertical is similar, adding an 1/3ⁿ (for some even n) to 3/8.

For any gradient=2 line:
0.0101...01011101...₃ = 1/8 + 1/3ⁿ
0.1010...10110010...₃ = 3/8 + 2/3ⁿ (odd n)
Gradient = 1/2 is similar, adding 2/3ⁿ to 1/8 and 1/3ⁿ to 3/8, with even n.

For Gradient = -2... this was a little trickier, but I found one:
0.0101...0101111111...₃ = 1/8 + 1/8 * 1/3ⁿ
0.1010...1002121212...₃ = 3/8 - 2/8 * 1/3ⁿ (odd n)
Gradient = -1/2 is similar, subtracting 2/8*1/3ⁿ from 1/8 and adding 1/8*1/3ⁿ to 3/8, with even n.

Do we know these are the only gradients we need to concern ourselves with? Or is there still the possibility of others?

[quintopia]

I highly doubt there are others, almost as much as I doubt I could prove it. I think the reason 1/2 works is because it is what the sum of powers of 1/3 converge to.

But if there are no others then, surprise surprise, this puzzle is solved.

[phlip]

Did I turn two pages at once here? Certainly possible... I've only skim-read some of the posts...

Sure, if those are the only gradients [edit] (which, thanks to jr's post below, we know they aren't) [/edit] we've shown that there's no piecewise-straight path ending at (or going through) (1/8,3/8)... but who says the path has to be piecewise-straight?

Besides, searching on Google shows that the carpet is path-connected^[1], so it's not going to be that easy.

[jestingrabbit]

Do we know these are the only gradients we need to concern ourselves with? Or is there still the possibility of others?

Gradient 1 or -1 starting from the midpoints are also good. I believe that these, with the gradient 2 and 1/2 (and their negatives) from midpoints to corners, are the only ones that are "live". Fun fact: (1/8, 3/8) is on the line of gradient -1 from (1/2, 0) to (0, 1/2).

[HalfThere]

I highly doubt there are others, almost as much as I doubt I could prove it. I think the reason 1/2 works is because it is what the sum of powers of 1/3 converge to.

But if there are no others then, surprise surprise, this puzzle is solved.

Eh? Could you explain how that's so - I certainly see that a lot of progress has been made, and I'm very impressed, but I'm hot sure it's a solution.

I suppose I could see what you're saying if you mean that now that all possible paths are known, you just need some sort of recursive solution, the mechanics of which are too tedious to describe, thus you've got something akin to what was asked for.

I certainly may be missing something. People have done a far better job of analyzing this problem than I could have.

Edit: My mind is kind of blown.

[phlip]

Actually, it's not too hard to construct a pair of coordinates which doesn't have lines on any of those gradients...

\begin{align}x =& 0.\overline{01000200}_3 \\ y =& 0.\overline{10022000}_3\end{align}

At each digit position there, you can, in order: add 1 to x; add 1 to y; add 1 to both; add 1 to x, subtract 1 from y; x+=1,y+=2; x+=2,y+=1; x+=1,y-=2; x-=2,y+=1... and get a spot with a 1 digit in both. And they're recurring, so you can do the same thing at any spot down the line to get points arbitrarily close to that point, on all those gradients, which isn't in the carpet.

I'm pretty sure (haven't proved, but it seems reasonable) that you could construct such a number for any rational gradient... so if there is, in fact, a finite set of gradients such that every point has a line interval through it on at least one of those gradients... I think there has to be some irrational ones in there. Either that, or it has to be an infinite set of gradients, or there's some points that can only be approached by a curve.

[quintopia]

Gradient 1 or -1 starting from the midpoints are also good.

Good find. I was looking for exactly that and still didn't see it.

But I don't understand how if a point does not fall on any connected line segment, there could still be a path between any two points in the set. Perhaps there are some other gradients we missed. I'm curious to see phlip's example, if he would fix it.

[phlip]

But I don't understand how if a point does not fall on any connected line segment, there could still be a path between any two points in the set. Perhaps there are some other gradients we missed.

Take, say, \{r\mathrm{e}^{i\theta} | r \le \theta \le 2r \}... there's no line segment through 0, but it's still path-connected to the set.

Obviously, that's a dense set, but the principle's the same.

And anyway, we haven't found a point that doesn't fall on any connected line segment... just specifically the few gradients we've tried.

[quintopia]

Ah, good point. How does one prove that it's connected, though?

[phlip]

I dunno... I've found a few places via Google that state it (like that textbook I linked to earlier), but none that prove it...

[jestingrabbit]

And anyway, we haven't found a point that doesn't fall on any connected line segment... just specifically the few gradients we've tried.

So clearly you want a proof that these are the only gradients that are feasible.

Spoiler:

To begin with, we need a way to think about an arbitrary line and how it interacts with the carpet. Notice that the carpet is based on a grid and consider the way that a line of arbitrary gradient lies on a grid. Now break it up into the infinite collection of segments that begin and end on the grid lines, such that no segment contains an intersection with a grid line, except at its endpoints. Now take all those segments and draw them in one square of the grid. So, you have an infinite number of line segments inside a square, each segment parallel to every other and each with its endpoints on the boundary of the square. Call this the "wrap around" of a line.

Now notice that if the gradient was irrational then the lines are dense in the square. How do you notice that? Well, no line segment ever lies on any other: if it did then the gradient was rational. For the density of the lines notice that they have to be "evenly spaced". By that I mean that if there are two points (x,y) and (x+a, y+b) on the segments, then (x+2a, y+2b) is also on the union of the segments, as the original line could be parametrised by a curve f:R->R², and if the first point was at f(t) and the second was at f(t+s), then the third is at f(t+2s) (more or less blah we're on a torus blah). From there, I could make a precise argument, but that is as precise as it needs to be imo (let me know if you think otherwise). Therefore, any segment with an irrational gradient will pass through the middle ninth of some square of some grid with mesh 1/3ⁿ for some large n.

Now we need to think about rational gradients. Firstly, after a finite number of segments are drawn we start repeating the segments already drawn: if we didn't the gradient was irrational. Assume the gradient is positive for convenience, and represent the gradient with a reduced fraction p/q, and assume wlog that p>=q. Through any horizontal line there will be p points that are on the segments, and by the "evenly spaced" fact (which works here too), they'll be spaced at 1/p intervals along the horizontal. From this, and a little thought, you can see that p<3 and q<3.

So that gets us what gradients are conceivably good. Furthermore, if they are really good then there must be lines with that gradient that fit on the carpet, even after we "wrap around", as otherwise they'll cross deleted ninths as they travel over the carpet. Its tedious, but doable, to check that we have the only lines that do the trick.

In general, I expect that we have to have an infinite number of straight segments connecting any two points, with a big straight bit in the middle, followed by smaller and smaller straight bits, getting closer and closer to the points in question. When you take the closure of the union of the segments, the end points will be where they should be.

btw, nice example of a point on no lines. I was going to go for a tedious measure theoretic argument that almost all points are off the lines, but yours works much better.

[quintopia]

In general, I expect that we have to have an infinite number of straight segments connecting any two points, with a big straight bit in the middle, followed by smaller and smaller straight bits, getting closer and closer to the points in question.

Just like road trips in the real world. . .

However, it's almost deceiving when you put it this way, since for some points the straight bits will get infinitely short. And at this point, we aren't really looking at a straight bit at all, but rather a curve of some sort. I suspect it will be a smooth curve whose tangent approaches one of the gradients that works, and at the precise moment it reaches that gradient, it will have arrived at some point that's on a line of that gradient and so we straighten out and follow a piecewise linear function like you said for some time, and then optionally we follow a curve again at the end.

[skeptical scientist]

It's easy to prove that it is (path-)connected. It suffices to show that every point is connected to the lower left corner. We can identify each point with an infinite sequence of digits between 1 and 8. Think of the carpet as being composed of 8 subcarpets; then the first digit tells us which subcarpet it's in, the second digit tells us which sub-sub-carpet it's in, and so forth. (We see that every point in the carpet gives rise to such a sequence. To see that every such sequence defines a point in the carpet, recall that a nested sequence of compact sets has nonempty intersection.) For each digit, think of a path in the carpet from the lower left point of the carpet to the lower left point of the appropriate subcarpet (for one subcarpet this is trivial, for four of them a line segment suffices, and the other three require a pair of line segments - the easiest to picture are the ones composed of at most one horizontal segment and at most one vertical segment). Now, given a point in the carpet, write out the corresponding sequence of digits between 1 and 8, and construct a path by following the corresponding path to each digit from the lower left point of the current subcarpet to the lower left point of the next sub-subcarpet.

(This would be a lot easier to explain with pictures.)

Note that the path constructed by this proof is exactly the like Jestingrabbit described - it's composed of infinitely many straight segments, all of which are either horizontal or vertical.

[quintopia]

Given a point's single-number representation, what is the shortest distance from it to the lower left corner?

[jestingrabbit]

In general, I expect that we have to have an infinite number of straight segments connecting any two points, with a big straight bit in the middle, followed by smaller and smaller straight bits, getting closer and closer to the points in question.

Just like road trips in the real world. . .

However, it's almost deceiving when you put it this way, since for some points the straight bits will get infinitely short. And at this point, we aren't really looking at a straight bit at all, but rather a curve of some sort. I suspect it will be a smooth curve whose tangent approaches one of the gradients that works, and at the precise moment it reaches that gradient, it will have arrived at some point that's on a line of that gradient and so we straighten out and follow a piecewise linear function like you said for some time, and then optionally we follow a curve again at the end.

Look, this "infinitely short" jive just doesn't cut anything. However, the question of whether there are smooth curves in the carpet is worth considering. I'm pretty sure though that there aren't, that at any point a curve's gradient must be within epsilon of the legal gradients, for any positive epsilon. From there its clear.

[skeptical scientist]

Can anyone make anything of my above proof that the carpet is path-connected? Should I try explaining it better? I'm worried that it's completely incomprehensible. Would that I had you all in a room with me and a blackboard...

[dedalus]

Skeptical_scientist, If that path you made was consisting of straight lines, surely the shortest path would be along the diagonal of each of the rectangles that the path goes through. Seeing as for most of these rectangles the width would come very close to zero for the full carpet, wouldn't it be fairly accurate to say that the shortest path IS that path?

[jestingrabbit]

Can anyone make anything of my above proof that the carpet is path-connected? Should I try explaining it better? I'm worried that it's completely incomprehensible. Would that I had you all in a room with me and a blackboard...

Makes perfect sense to me, but I knew the result already.

Given a point's single-number representation, what is the shortest distance from it to the lower left corner?

Whether we give it the single number representation or not, we can at least say some things that are true.

Lets call the function that returns the distance from a point to the origin f: S -> R⁺, where S is the carpet. Firstly, note that f((x,y)) = f((y,x)). Furthermore, if (x,y)\in S\cap [0,1/3]\times [0,1/3] then

• f(x,y) = \frac{f(3(x,y))}{3}
• f((x+1/3, y+2/3)) = \frac{\sqrt{5}}{3} + f((x,y))
• if x<y, f((x+ 2/3, y+ 2/3)) = \frac{\sqrt{5}}{3} + f((x+ 1/3, y)).

So, to a certain extent, that describes f on half the carpet. But what is it on the remainder? I'm thinking but its nontrivial.

Seeing as for most of these rectangles the width would come very close to zero for the full carpet, wouldn't it be fairly accurate to say that the shortest path IS that path?

We can say that if we want but I, for one, want proof.