The Sierpinski walk
Moderators: jestingrabbit, Moderators General, Prelates
The Sierpinski walk
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
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
Last edited by HalfThere on Mon Jun 08, 2009 2:07 am UTC, edited 1 time in total.
Re: The Sierpinski walk
Blatm wrote:Spoiler:
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:
Last edited by jaap on Tue Jun 09, 2009 8:23 am UTC, edited 2 times in total.
Re: The Sierpinski walk
It can't be the Manhattan distance for an even more obvious reason:
Edit: should we be making a solution thread?
Spoiler:
Spoiler:
Edit: should we be making a solution thread?
Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
Qaanol wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: The Sierpinski walk
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
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
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.
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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: The Sierpinski walk
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 topleft corner of the largest square), there is a clearer notion of points "on" the carpet. Is that what is meant? Am I totally offtrack here?
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 topleft corner of the largest square), there is a clearer notion of points "on" the carpet. Is that what is meant? Am I totally offtrack here?
Re: The Sierpinski walk
afarnen wrote: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 topleft corner of the largest square), there is a clearer notion of points "on" the carpet. Is that what is meant? Am I totally offtrack 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 2dimensional 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).
Re: The Sierpinski walk
jaap wrote:afarnen wrote: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.
Re: The Sierpinski walk
afarnen wrote: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.

 Posts: 13
 Joined: Sun May 31, 2009 9:27 pm UTC
Re: The Sierpinski walk
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?
Is there a way to mathematically prove that 1/4 will always stay on the carpet?
 phlip
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
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 bottomleft corner, (1,1) as the topright). So if we map it to the coordinates of that square (so (1,1) is now the topright 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.
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 bottomleft corner, (1,1) as the topright). So if we map it to the coordinates of that square (so (1,1) is now the topright 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.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
EricSeverson wrote: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
[math]x = \sum_{n=1}^{\infty} \frac{x_n}{3^n}[/math]
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 [imath]\left( \frac{j}{2\cdot 3^n}, \frac{k}{2\cdot 3^n}\right)[/imath] but its not clear what points to pick yet.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: The Sierpinski walk
I guess there's probably a higherlevel 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 cartesianstyle 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 firstiteration sierpinski square with sides of 3dx, then the distance from one corner to the opposite corner is [imath]a=2\sqrt{5}dx[/imath]. The distance from halfway along a line to either of the opposite corners is [imath]b=\frac{3\sqrt{5}}{2}dx[/imath]. If we now consider an iteration above that (i.e. a 2nditeration 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.
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 cartesianstyle 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 firstiteration sierpinski square with sides of 3dx, then the distance from one corner to the opposite corner is [imath]a=2\sqrt{5}dx[/imath]. The distance from halfway along a line to either of the opposite corners is [imath]b=\frac{3\sqrt{5}}{2}dx[/imath]. If we now consider an iteration above that (i.e. a 2nditeration 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.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.
Re: The Sierpinski walk
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.

 Posts: 13
 Joined: Sun May 31, 2009 9:27 pm UTC
Re: The Sierpinski walk
So i was thinking about the diagonal lines that are on the carpet that jaap was talking about. Basically they forms a 8pointed 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?
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?
Re: The Sierpinski walk
EricSeverson wrote: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.
EricSeverson wrote: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
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
(1/8,3/8) is on the carpet, but isn't on any horizontal or vertical line segment... that's [imath](0.\overline{01}_3, 0.\overline{10}_3)[/imath]. I'm not sure about diagonal line segments, though... I don't really have a good grasp of what they look like.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: The Sierpinski walk
phlip wrote:(1/8,3/8) is on the carpet, but isn't on any horizontal or vertical line segment... that's [imath](0.\overline{01}_3, 0.\overline{10}_3)[/imath]. 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
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
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..._{3} = 1/8 + 1/3^{n} (for some odd n)
0.1010...1010101010..._{3} = 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^{n} (for some even n) to 3/8.
For any gradient=2 line:
0.0101...01011101..._{3} = 1/8 + 1/3^{n}
0.1010...10110010..._{3} = 3/8 + 2/3^{n} (odd n)
Gradient = 1/2 is similar, adding 2/3^{n} to 1/8 and 1/3^{n} to 3/8, with even n.
For Gradient = 2... this was a little trickier, but I found one:
0.0101...0101111111..._{3} = 1/8 + 1/8 * 1/3^{n}
0.1010...1002121212..._{3} = 3/8  2/8 * 1/3^{n} (odd n)
Gradient = 1/2 is similar, subtracting 2/8*1/3^{n} from 1/8 and adding 1/8*1/3^{n} 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?
For any horizontal open interval containing (1/8,3/8), there is a point:
0.0101...0101110101..._{3} = 1/8 + 1/3^{n} (for some odd n)
0.1010...1010101010..._{3} = 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^{n} (for some even n) to 3/8.
For any gradient=2 line:
0.0101...01011101..._{3} = 1/8 + 1/3^{n}
0.1010...10110010..._{3} = 3/8 + 2/3^{n} (odd n)
Gradient = 1/2 is similar, adding 2/3^{n} to 1/8 and 1/3^{n} to 3/8, with even n.
For Gradient = 2... this was a little trickier, but I found one:
0.0101...0101111111..._{3} = 1/8 + 1/8 * 1/3^{n}
0.1010...1002121212..._{3} = 3/8  2/8 * 1/3^{n} (odd n)
Gradient = 1/2 is similar, subtracting 2/8*1/3^{n} from 1/8 and adding 1/8*1/3^{n} 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?
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: The Sierpinski walk
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.
But if there are no others then, surprise surprise, this puzzle is solved.
 phlip
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
Did I turn two pages at once here? Certainly possible... I've only skimread 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 piecewisestraight path ending at (or going through) (1/8,3/8)... but who says the path has to be piecewisestraight?
Besides, searching on Google shows that the carpet is pathconnected^{[1]}, so it's not going to be that easy.
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 piecewisestraight path ending at (or going through) (1/8,3/8)... but who says the path has to be piecewisestraight?
Besides, searching on Google shows that the carpet is pathconnected^{[1]}, so it's not going to be that easy.
Last edited by phlip on Fri Jun 12, 2009 5:35 am UTC, edited 1 time in total.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
phlip wrote: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).
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: The Sierpinski walk
quintopia wrote: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
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
Actually, it's not too hard to construct a pair of coordinates which doesn't have lines on any of those gradients...[math]\begin{align}x =& 0.\overline{01000200}_3 \\ y =& 0.\overline{10022000}_3\end{align}[/math]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.
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.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: The Sierpinski walk
jestingrabbit wrote: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
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
quintopia wrote: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, [imath]\{r\mathrm{e}^{i\theta}  r \le \theta \le 2r \}[/imath]... there's no line segment through 0, but it's still pathconnected 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.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: The Sierpinski walk
Ah, good point. How does one prove that it's connected, though?
 phlip
 Restorer of Worlds
 Posts: 7519
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: The Sierpinski walk
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...
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
phlip wrote: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:
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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: The Sierpinski walk
jestingrabbit wrote: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
 closedminded spiritualist
 Posts: 6139
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: The Sierpinski walk
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 subsubcarpet 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 subsubcarpet.
(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.
(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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: The Sierpinski walk
Given a point's singlenumber representation, what is the shortest distance from it to the lower left corner?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
quintopia wrote:jestingrabbit wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 skeptical scientist
 closedminded spiritualist
 Posts: 6139
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: The Sierpinski walk
Can anyone make anything of my above proof that the carpet is pathconnected? 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...
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: The Sierpinski walk
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?
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The Sierpinski walk
skeptical scientist wrote:Can anyone make anything of my above proof that the carpet is pathconnected? 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.
quintopia wrote:Given a point's singlenumber 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 [imath](x,y)\in S\cap [0,1/3]\times [0,1/3][/imath] then
 [imath]f(x,y) = \frac{f(3(x,y))}{3}[/imath]
 [imath]f((x+1/3, y+2/3)) = \frac{\sqrt{5}}{3} + f((x,y))[/imath]
 if x<y, [imath]f((x+ 2/3, y+ 2/3)) = \frac{\sqrt{5}}{3} + f((x+ 1/3, y)).[/imath]
dedalus wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Who is online
Users browsing this forum: Google [Bot] and 9 guests