Chaos calculation

[bonanova]

BMAD's gave an algorithm for recursively placing points,

ad infinitum, within the interior of a triangle. The beautifully surprising

result was the appearance of well-defined areas, within which points

could not be placed. Call these areas white space.

The puzzle inspired Pickett to page-2#entry334664, and the page-3#entry334674 that generates

them, of several other shapes. The most interesting seemed to be

BMAD's original triangle, and the page-2#entry334665, reproduced below.

My puzzle is a simple calculation:

What fraction of the triangle is white space?

What fraction of the trapezoid is white space?

Edit: Creativity will be rewarded: Got a different approach? Get another star.

Edited July 29, 2013 by bonanova
Creativity rewarded

[gavinksong]

I posted this in the original thread, but I think it belongs here now.

What fraction of the area is white (prohibited)

1. For the triangle? (straightforward)
2. For the trapezoid? (more thought-provoking)

Well, for a triangle, if we add up the white space, it is just the infinite sum of a geometric series with a factor of 3/4 (the big empty triangle in the middle is one-fourth of the total area, the three smaller triangles are one-fourth of the remaining area, and so forth). Strangely, it converges at the total area of the triangle. It we calculate the black space, it is three-fourths raised to the infinite power, which is zero. So apparently, the entire triangle is supposed to be prohibited space.

I think here bonanova's musings becomes relevant:

But I'm not clear what happens if your initial point were inside.

Instead of looking backwards, as we did to solve the problem initially, we should look forwards from the initial point. This is all intuition, but you will notice, that if the initial point is in the big empty triangle in the middle, then in the next step, it will always move to one of the three smaller white triangles. And from there, it will always move into one of its three smaller "shadows" (I think that is an appropriate term, and hopefully you understand what I mean), and so on. The important point here is that we always move into smaller and smaller "shadows".

When the initial point is thrown into the triangle at random, the probability that it lies into a white triangle is 100%. However, as the simulation progresses, the points are eventually forced into smaller and smaller white triangles. In other words, the amount of "prohibited space" is not actually an absolute value, but simply increases with step number (in a sense). As in, there is no prohibited space when you throw in the first point, but the second point cannot be in the large white triangle, the third point cannot be in the large white triangle or any of its shadows, the fourth cannot be in the large white triangle or its shadows or any of its shadows' shadows, and so on.

So to us, it seems as though there is some sort of absolute law because we see the larger empty white triangles, but in reality, it is only because we do not see the infinitesimally small white triangles with the dots in them. The entire process is just endless error-correction, moving toward an impossible figure, trailing behind an interesting asymptotic pattern in the process.

[BMAD]

3^0*1/4+3^1*(1/4^2)+3^2*(1/4^3)+3^3*(1/4^4)+...

Edited July 29, 2013 by BMAD

[BMAD]

so.... i have 1/2

[BMAD]

AS a result i believe that the trapezoid is equal to 1/4. If you invert the interior of the trapezoids "center triangle" making an isosceles triangle, once can see that it is much like the other triangle. Showing that the only difference between the two pieces is the large center white space meaning that its white space is 1/4 smaller than the triangle.

[DeGe]

By brute force, 3/4 of the space is white
Now, I need to get the creativity points

[DeGe]

By brute force, 3/4 of the space is white

Now, I need to get the creativity points

The white area is 100%!

I think this result is mainly because we are considering area (in black) covered by points; which by definition have an area of 0.

Edited July 29, 2013 by DeGe

[BMAD]

clearly i am better at writing questions than answering them

[bonanova]

I posted this in the original thread, but I think it belongs here now.

What fraction of the area is white (prohibited)

• For the triangle? (straightforward)
• For the trapezoid? (more thought-provoking)

Well, for a triangle, if we add up the white space, it is just the infinite sum of a geometric series with a factor of 3/4 (the big empty triangle in the middle is one-fourth of the total area, the three smaller triangles are one-fourth of the remaining area, and so forth). Strangely, it converges at the total area of the triangle. It we calculate the black space, it is three-fourths raised to the infinite power, which is zero. So apparently, the entire triangle is supposed to be prohibited space.

I think here bonanova's musings becomes relevant:

But I'm not clear what happens if your initial point were inside.

Instead of looking backwards, as we did to solve the problem initially, we should look forwards from the initial point. This is all intuition, but you will notice, that if the initial point is in the big empty triangle in the middle, then in the next step, it will always move to one of the three smaller white triangles. And from there, it will always move into one of its three smaller "shadows" (I think that is an appropriate term, and hopefully you understand what I mean), and so on. The important point here is that we always move into smaller and smaller "shadows".

When the initial point is thrown into the triangle at random, the probability that it lies into a white triangle is 100%. However, as the simulation progresses, the points are eventually forced into smaller and smaller white triangles. In other words, the amount of "prohibited space" is not actually an absolute value, but simply increases with step number (in a sense). As in, there is no prohibited space when you throw in the first point, but the second point cannot be in the large white triangle, the third point cannot be in the large white triangle or any of its shadows, the fourth cannot be in the large white triangle or its shadows or any of its shadows' shadows, and so on.

So to us, it seems as though there is some sort of absolute law because we see the larger empty white triangles, but in reality, it is only because we do not see the infinitesimally small white triangles with the dots in them. The entire process is just endless error-correction, moving toward an impossible figure, trailing behind an interesting asymptotic pattern in the process.

gavinksong has the answer.

His method was the infinite sum of triangular areas, and he gives an intuitive description of the point generation process and its implications. Kudos for explaining my wonderings about placement of the initial point. It's an amazing mental image to visualize an initial point at the center try to search for a "black area" to land on, but instead finding at each step it simply lands on a smaller white area. Every point travels a path of white areas; or putting it another way, there simply are no black areas!

[As an aside, therefore, my puzzle is a bit of a ruse. The figures clearly show black areas. A moment's reflection tells us why. I constructed the figures using dots that have non-zero area. Eventually they touch and overlap each other. It's OK that the construction used black dots: it's just that to avoid being misleading they should have had zero area. If I had done that, it is perfectly clear that the entire triangle would remain white forever, or until the computer reboots, whichever comes first.]

My first crack at calculating the white space used a geometrical approach, the answer to which surprised me enough to do the math. When that agreed, a third argument suggested itself to explain what seems an impossible result. Two more Gold Stars are available for proofs that don't require infinite sums.

As for the trapezoid, I think we can safely modify whatever is proved for the triangle, without considering it a different problem.

[bonanova]

By brute force, 3/4 of the space is white

Now, I need to get the creativity points

The white area is 100%!

I think this result is mainly because we are considering area (in black) covered by points; which by definition have an area of 0.

DeGe has an insightfully creative solution.

Without loss of generality the triangle can be scaled by a rational number times the inverse of the coordinates of the vertices and first random point. Or we could say without loss of generality the vertices and initial point can be assigned rational coordinates. Either way, all the computed points will have rational coordinates, and as such, although infinite in number, have the cardinality of the rational numbers, Aleph Null. Their Lebesgue measure is zero. Another way to say it, as DeGe points out, they are points. But so is the interior of the triangle. The distinction is that the rationals are not dense - they are isolated points.

The entire set of points inside the triangle has the cardinality of the continuum. Those points have real coordinates and are dense; thus, their Lebesgue measure equals the area of the triangle. The computed points can be removed without changing that measure. Therefore the area of the white space is the area of the triangle.

One Gold star remains to be achieved. A geometrical proof that does not use the word infinity or its implications.

[gavinksong]

A geometrical proof?

This is probably pretty much the same as the sum of an infinite geometric series, but here it goes.

Let's say that the area of white space is A and the total area of the triangle is 1.

The triangle is essentially composed of four equal parts: one fully white triangle and three smaller versions of itself.

So A = (1 + 3A) / 4.

If we solve for A, we get...

4A = 1 + 3A

A = 1

[gavinksong]

By brute force, 3/4 of the space is white

Now, I need to get the creativity points

The white area is 100%!

I think this result is mainly because we are considering area (in black) covered by points; which by definition have an area of 0.

DeGe has an insightfully creative solution. bona_gold_star.gif

Without loss of generality the triangle can be scaled by a rational number times the inverse of the coordinates of the vertices and first random point. Or we could say without loss of generality the vertices and initial point can be assigned rational coordinates. Either way, all the computed points will have rational coordinates, and as such, although infinite in number, have the cardinality of the rational numbers, Aleph Null. Their Lebesgue measure is zero. Another way to say it, as DeGe points out, they are points. But so is the interior of the triangle. The distinction is that the rationals are not dense - they are isolated points.

The entire set of points inside the triangle has the cardinality of the continuum. Those points have real coordinates and are dense; thus, their Lebesgue measure equals the area of the triangle. The computed points can be removed without changing that measure. Therefore the area of the white space is the area of the triangle.

One Gold star remains to be achieved. A geometrical proof that does not use the word infinity or its implications.

Ok. I feel a little scared to be saying this (especially since I barely understood any of that) but...

I disagree.. with the explanation mentioning the fact that points have zero area.

It's not that I disagree with the fact itself. Points do indeed have zero area. It's just that I don't feel like it is relevant.

The question wasn't to add up the area that the points occupy. It was to calculate the area of the "white space" that the points could never occupy, which is also different from the area that the points do not occupy. Just because points do not have area does not mean that "black spaces" (or "not white spaces") also do not have area. It just so happens that in this case, the entire triangle is white space - though even that is not accurate, because points do occupy the triangle, and that would go against my definition of "white space". To be accurate, it would have to be said that the true white space grows with step number and eventually its area converges on that of the entire triangle but never actually attains it. If we were asked to determine the white space of a certain step, that could easily be done, and the answer would not be equal to the area of the triangle. You can easily see that in this version of the problem, it is irrelevant that points have zero area... as it also is in the original problem.

[DeGe]

Thanx Bonanova for the star!

The question wasn't to add up the area that the points occupy.

Could we then not consider it as 0^{infinity ?}

[bonanova]

A geometrical proof?

This is probably pretty much the same as the sum of an infinite geometric series, but here it goes.

Let's say that the area of white space is A and the total area of the triangle is 1.

The triangle is essentially composed of four equal parts: one fully white triangle and three smaller versions of itself.

So A = (1 + 3A) / 4.

If we solve for A, we get...

4A = 1 + 3A

A = 1

Yes. This is exactly what I found.

Three fourths of the triangle are self-similar copies and the rest is white.

The fractional whiteness of the four parts must be equal.

That's the simplest and most elegant of the three proofs.

If you like, try dissecting the trapezoid and do the same proof.

It has twelve triangles of three varieties and takes two equations to solve.

[bonanova]

The question wasn't to add up the area that the points occupy. It was to calculate the area of the "white space" that the points could never occupy, which is also different from the area that the points do not occupy. Just because points do not have area does not mean that "black spaces" (or "not white spaces") also do not have area. It just so happens that in this case, the entire triangle is white space - though even that is not accurate, because points do occupy the triangle, and that would go against my definition of "white space". To be accurate, it would have to be said that the true white space grows with step number and eventually its area converges on that of the entire triangle but never actually attains it. If we were asked to determine the white space of a certain step, that could easily be done, and the answer would not be equal to the area of the triangle. You can easily see that in this version of the problem, it is irrelevant that points have zero area... as it also is in the original problem.

We traveled a kind of intuitive path in doing this analysis. So to be clear of the result, we have to make statements that are a little more precise. In fact, the statement of the puzzle uses the intuitive term "white space." This leads to the idea that the triangle is partitioned somehow into disjoint regions that are intrinsically white or black. Or, as you say "the 'white space' that the points could never occupy." -- regions where points are not allowed to land.

Such regions do not exist. Not even a single point is off limits: it could be the initial point.

This beautiful puzzle forces us to view the triangle not as two sets of tiny triangles, some white and some black, (more precisely some that have No Trespassing signs, others that do not) but as two sets of points: one set that is rationally related to the arbitrarily selected first point, and all the others.

Consider a one-dimensional analog. Color the interval [0, 1] of the x-axis white. Now paint the point x=.5 black. Now move half-way to 0 or 1, randomly chosen, and paint that point black. Repeat ad infinitum. The rational numbers will be painted black The non-rational numbers like 1/pi and 1/e remain white. What fraction of the interval is white? What you will find is there is no interval of infinitesimally small length that is free of black points, yet we can say that the "measure" of the interval that is white is 1.

Or, define f(x) to be 1 if x is rational and 0 otherwise. What is the integral of f(x) on the interval?

Our normal measuring device for lengths and areas is the ordinary Riemann integral. But it only works for functions that are reasonably continuous. When you get down to point-size regions, Mr. Riemann throws up his hands and says, don't bother me, I have no idea. Go talk with Mr. Lebesgue over there. And Mr. Lebesgue says, don't talk to me about length and area, I don't know what they are. I do know about measure, however.

The measure of the rationals on [0, 1] is zero. The measure of the reals on [0,1] is 1. The measure of non-rational reals on [0, 1] is 1 - 0 = 1.

On the triangle, the measure of the points with rational coordinates is 0. The rest of the points have measure equal to the area of the triangle - 0. In the Lebesgue sense, (and no other "sense" applies to this question,) the "area" of the triangle that is white is the area of the triangle minus something that has the value zero.

What I really liked about your analysis was talking about the decomposition into triangles of ever decreasing size. Call the sequence of areas A1, A2, A3, ..., each value 1/4 of the preceding. That decomposition does not depend on the initial point. What you said, and I think you are correct in this, that wherever the initial point is placed, say it's in a triangle of area A13, none of the following points will land in triangles with area A1, A2, ... A12, or the other regions with area A13. The following points will be in triangular regions respectively with area A14, A15 ..., and so on.

That analysis shows that once the initial point is placed, there ARE point-free regions. There are regions that will never (for that initial point placement) have a point in them. But those regions (A1, A2, ... A12) are not intrinsically "white areas". The initial point could land in a triangle of area A7. Then the A1, A2, ... A6 regions, and the other A7 regions will be point-free. And the initial point (my musings...) could land in A1. The probability of that happening is 0.25, but it is not 0.

One final observation. my one-dimensional case in blue above behaves differently from the triangle, and makes the triangle at once more beautiful and intriguing to analyze. In one dimension, the point can return to any region arbitrarily close to the initial point. If we simulated this case, the whole interval would eventually look black because we use dots of non-zero size. Yet the interval remains white in the Lebesgue sense.

In the triangle that is not possible; the point cannot back-track. It never moves directly away from a vertex, so it can never move back in the same direction. That is why the A1 region looks white every time the simulation is run. And the A2 regions do, also, and the A3 regions. Each of all the triangles with a given area contain at most one black dot.

Perhaps this is why the square shape showed no structure.

[gavinksong]

The question wasn't to add up the area that the points occupy. It was to calculate the area of the "white space" that the points could never occupy, which is also different from the area that the points do not occupy. Just because points do not have area does not mean that "black spaces" (or "not white spaces") also do not have area. It just so happens that in this case, the entire triangle is white space - though even that is not accurate, because points do occupy the triangle, and that would go against my definition of "white space". To be accurate, it would have to be said that the true white space grows with step number and eventually its area converges on that of the entire triangle but never actually attains it. If we were asked to determine the white space of a certain step, that could easily be done, and the answer would not be equal to the area of the triangle. You can easily see that in this version of the problem, it is irrelevant that points have zero area... as it also is in the original problem.

We traveled a kind of intuitive path in doing this analysis. So to be clear of the result, we have to make statements that are a little more precise. In fact, the statement of the puzzle uses the intuitive term "white space." This leads to the idea that the triangle is partitioned somehow into disjoint regions that are intrinsically white or black. Or, as you say "the 'white space' that the points could never occupy." -- regions where points are not allowed to land.

Such regions do not exist. Not even a single point is off limits: it could be the initial point.

This beautiful puzzle forces us to view the triangle not as two sets of tiny triangles, some white and some black, (more precisely some that have No Trespassing signs, others that do not) but as two sets of points: one set that is rationally related to the arbitrarily selected first point, and all the others.

Consider a one-dimensional analog. Color the interval [0, 1] of the x-axis white. Now paint the point x=.5 black. Now move half-way to 0 or 1, randomly chosen, and paint that point black. Repeat ad infinitum. The rational numbers will be painted black The non-rational numbers like 1/pi and 1/e remain white. What fraction of the interval is white? What you will find is there is no interval of infinitesimally small length that is free of black points, yet we can say that the "measure" of the interval that is white is 1.

Or, define f(x) to be 1 if x is rational and 0 otherwise. What is the integral of f(x) on the interval?

Our normal measuring device for lengths and areas is the ordinary Riemann integral. But it only works for functions that are reasonably continuous. When you get down to point-size regions, Mr. Riemann throws up his hands and says, don't bother me, I have no idea. Go talk with Mr. Lebesgue over there. And Mr. Lebesgue says, don't talk to me about length and area, I don't know what they are. I do know about measure, however.

The measure of the rationals on [0, 1] is zero. The measure of the reals on [0,1] is 1. The measure of non-rational reals on [0, 1] is 1 - 0 = 1.

On the triangle, the measure of the points with rational coordinates is 0. The rest of the points have measure equal to the area of the triangle - 0. In the Lebesgue sense, (and no other "sense" applies to this question,) the "area" of the triangle that is white is the area of the triangle minus something that has the value zero.

What I really liked about your analysis was talking about the decomposition into triangles of ever decreasing size. Call the sequence of areas A1, A2, A3, ..., each value 1/4 of the preceding. That decomposition does not depend on the initial point. What you said, and I think you are correct in this, that wherever the initial point is placed, say it's in a triangle of area A13, none of the following points will land in triangles with area A1, A2, ... A12, or the other regions with area A13. The following points will be in triangular regions respectively with area A14, A15 ..., and so on.

That analysis shows that once the initial point is placed, there ARE point-free regions. There are regions that will never (for that initial point placement) have a point in them. But those regions (A1, A2, ... A12) are not intrinsically "white areas". The initial point could land in a triangle of area A7. Then the A1, A2, ... A6 regions, and the other A7 regions will be point-free. And the initial point (my musings...) could land in A1. The probability of that happening is 0.25, but it is not 0.

One final observation. my one-dimensional case in blue above behaves differently from the triangle, and makes the triangle at once more beautiful and intriguing to analyze. In one dimension, the point can return to any region arbitrarily close to the initial point. If we simulated this case, the whole interval would eventually look black because we use dots of non-zero size. Yet the interval remains white in the Lebesgue sense.

In the triangle that is not possible; the point cannot back-track. It never moves directly away from a vertex, so it can never move back in the same direction. That is why the A1 region looks white every time the simulation is run. And the A2 regions do, also, and the A3 regions. Each of all the triangles with a given area contain at most one black dot.

Perhaps this is why the square shape showed no structure.

I see. Let me see if I get this.

You are saying that after the initial point is selected, all of the points that could be selected afterwards (or the "black space") are rationally related to the first (regardless of whether the first point was rational or irrational). And since the set of these points are discontinuous point-regions (a bit of an oxymoron), the sum of the total area of these regions should be zero.

It seems that we have different definitions of "black" and "white" space.

We have already calculated that the "white area" is the total area of the triangle, but as you and I said, this is not completely accurate. The terms defined as they are in the OP ("The beautifully surprising result was the appearance of well-defined areas, within which points could not be placed. Call these areas white space."), the question is asking for something that does not exist, as the initial step renders the entire triangle "black". The only reason we could only "calculate" the white space (which does not exist) using infinite geometrical sums was that we made a very big assumption, which was that the "white" and "black" space could be perfectly modeled by a sort of fractal or recursive structure. But this was in fact wrong, and after looking at the result of our calculations, it was clear that our definitions needed to be updated and shed of assumptions. When I first posted my answer, it was to the original thread, and my goal was not exactly to answer your question of "what is the total area of white space" but to point out that it was flawed (or at least the definitions were not good).

I understood "white space" to be regions that points would never be allowed to land on in any simulation (I later redefined it to be something that can only be calculated for the nth point. eg. the area of white space for the third point is 7/16). On the other hand, your defined"black space" to be regions which would eventually become continuously filled with points if one simulation ran for an infinitely long time. Both of our definitions are valid, I think, but addresses rather different problems.

It is actually a pretty interesting observation that there are no continuous regions. One way to explain this phenomenon using the image of dots always traveling down a path of white triangles of decreasing size would be to note that once a dot is placed in a white triangle, that triangle effectively becomes "white space" according to my definition (or another way to put it is that it stops "decomposing"). Thus, every dot will have a triangular area around it that future dots can never land.

Edited July 31, 2013 by gavinksong

[gavinksong]

A geometrical proof?

This is probably pretty much the same as the sum of an infinite geometric series, but here it goes.

Let's say that the area of white space is A and the total area of the triangle is 1.

The triangle is essentially composed of four equal parts: one fully white triangle and three smaller versions of itself.

So A = (1 + 3A) / 4.

If we solve for A, we get...

4A = 1 + 3A

A = 1

Yes. This is exactly what I found. bona_gold_star.gif

Three fourths of the triangle are self-similar copies and the rest is white.

The fractional whiteness of the four parts must be equal.

That's the simplest and most elegant of the three proofs.

If you like, try dissecting the trapezoid and do the same proof.

It has twelve triangles of three varieties and takes two equations to solve.

I divided the trapezoid largely into three triangles:

two triangles on the sides and one upside down triangle in the middle.

The two on the sides are identical. Call it A. Call the upside down triangle B.

Calculating the black space:

A = (3A+B)/4

A = B

B = (A+2B)/4

A = (3A)/4

A = B = 0

[bonanova]

A geometrical proof?

This is probably pretty much the same as the sum of an infinite geometric series, but here it goes.

Let's say that the area of white space is A and the total area of the triangle is 1.

The triangle is essentially composed of four equal parts: one fully white triangle and three smaller versions of itself.

So A = (1 + 3A) / 4.

If we solve for A, we get...

4A = 1 + 3A

A = 1

Yes. This is exactly what I found. bona_gold_star.gif

Three fourths of the triangle are self-similar copies and the rest is white.

The fractional whiteness of the four parts must be equal.

That's the simplest and most elegant of the three proofs.

If you like, try dissecting the trapezoid and do the same proof.

It has twelve triangles of three varieties and takes two equations to solve.

I divided the trapezoid largely into three triangles:

two triangles on the sides and one upside down triangle in the middle.

The two on the sides are identical. Call it A. Call the upside down triangle B.

Calculating the black space:

A = (3A+B)/4

A = B

B = (A+2B)/4

A = (3A)/4

A = B = 0

Cool. I did white space, used 12 triangles of three types and had to throw a 1 in the mix.

Your way is simpler.

[bonanova]

Illustrating gavinksong's description of the progression of points:

The graphic shows the progression of smaller and smaller triangles that fill the outer boundary.

A1: 1 red triangle, 1/4 of the size of the outer boundary

A2: 3 green triangles, each 1/4 of the size of the red triangle

A3: 9 blue triangles, each 1/4 of the size of the green triangles.

A4: 27 red triangles, each 1/4 of the size of the blue triangles

A5: 81 green triangles, each 1/4 of the size of the red triangles.

....

The trajectories of two dots placed in A1 is shown.

A black dot starts in the upper right corner, and a red dot starts in the center.

With each step, each dot progresses through red, green, blue, red green ... triangles,

maintaining its relative position within each triangle.

This underscores how sparse the dots are.

Only a single dot is placed in each of the areas A1, A2, A3, ...

That is, at each level, there is a collection of triangles.

One and only one of them receives a single point.

The other triangles at that level are totally white.

This accounts for the appearance of white triangular spaces in the simulation.

Since a single dot will never color an entire triangle, no matter how small the triangle is, no triangle can be said to be black. Every triangle is white. The entire triangle is therefore white.

[BMAD]

love it!