Bouncing Point

[gavinksong]

This may not be very good, since it is my first problem - but here it goes...

There is a two-dimensional box and a point.

The point starts somewhere in the box and moves straight in some direction. When it hits a wall, it bounces off of it.

The point leaves behind a black line as it travels.

Is there ever a case where the entire box becomes colored if the point travels forever? If not, what is the minimum area of the "white space"?

[Anza Power]

I have a proof:

Ok assume that the point isn't going vertically (otherwise it will remain on the same vertical line and never fill the box)

Assume the rectangle is a square with vertices (0,0) (0,1) (1,0) (1,1), we'll draw a vertical line inside the square at x=0.5.

Now let a_n be the y value of the point when it crosses the line for the n'th time, if the point was to cover the entire square then for every y in range [0,1] there must exist some n such that a_n=y, but this says that the range [0,1] is countable which we know it's not.

_n such that forall y in [0,1) exists n in N such that a_n=y, here's what you do:

Let's do it for the range [0,1), assume it is countable, as in we found a series a

Build a 2D table that starts at the top left and extends infinitely to the right and down, now now every real number can be written as 0.539563,,, ignore the 0 and the decimal point and take the digits after the decimal point, for each a_n take it and put it's digits in the n'th row of the table.

Let t(i,j) be the value at row i column j of the table, now take all the digits at the diagonal of the table t(m,m) and make a new number from these digits by adding 1 to each digits and warping (0 becomes 1, 1 becomes 2 ... 8 becomes 9, 9 becomes 0), so if the table looked like this:

11704...

68700...

05978...

56752,,,

,,,,,,,,,,,,,

The number we'll get is 0.2906...

Now it is impossible for this number to be in the table, because if it were at row m then the value of t(m,m) is it's m'th digit, but it's m'th digit it t(m,m) plus 1,

Edited August 3, 2013 by Anza Power

[bonanova]

Consider the trajectory as a straight line through an infinite square tiling of the plane. You then want the line to eventually cross every point on the replicated horizontal boundary. The trajectories through each square are parallel, so if every point on the horizontal boundary is touched, then every point in the replicated square will be touched as well. So what must be avoided is a rational relationship among those crossing points. By the way, this would also ensure every point on the vertical boundary is crossed.

I will throw out the following assertion, that yes, this can be done. The box is the unit square occupying the first quadrant. The path begins at the origin. It continues upward and to the right, hitting the upper boundary at x=pi/4, y=1.

It will require an uncountably infinite number of bounces, but no replicated point will be visited twice. For any given target point, one should be able to calculate the number of bounces needed for it to be visited. I guess that would be a proof.

So the question would be answered if the number of bounces can be calculated to visit say the point x=1/e, y=1/sqrt(2).

Edit:

Let x_o, y_o be the point in the box to be visited.

Let y = mx be the trajectory, beginning at the origin.

Let p be the number of horizontal traversals of the box

Let q be the number of vertical traversals of the box.

In the infinite tiling case, this means x = p + x_o, y = q + y_o.

Then ( q + y_o) = m ( p + x_o) or q = m ( p + x_o) - y_o

We seek a solution for integer values of p and q.

In the above case, q = (4/pi) ( p + 1/e) - 1/sqrt(2). Number of bounces is p + q.

So the answer to the OP is whether an integer solution exists.

This might boil down to finding a rational expression for an irrational number, which would be impossible.

Edited August 2, 2013 by bonanova
Equation for bounces

[DeGe]

This is the same case as that of a point in the triangle: A line has zero area, so any line on its own can not bound any area.
Lets assume that a group of lines form an infinitesimally small area within the rectangle. Then for any point within this area, there is a line that passes through this point at each and every angle from 0 to 360 degrees. For this to be possible, there are 2 lines that are also perpendicular to the sides of the rectangle. However, this is not possible; if you have 1 line perpendicular to the side, it will keep tracking the same line and never change direction, so the other perpendicular line can not be made. Therefore, there is not even an infinitesimally small area covered by the lines within the rectangle.
The minimum area of the white rectangle then is the area of the rectangle itself.

[gavinksong]

This is the same case as that of a point in the triangle: A line has zero area, so any line on its own can not bound any area.

Lets assume that a group of lines form an infinitesimally small area within the rectangle. Then for any point within this area, there is a line that passes through this point at each and every angle from 0 to 360 degrees. For this to be possible, there are 2 lines that are also perpendicular to the sides of the rectangle. However, this is not possible; if you have 1 line perpendicular to the side, it will keep tracking the same line and never change direction, so the other perpendicular line can not be made. Therefore, there is not even an infinitesimally small area covered by the lines within the rectangle.

The minimum area of the white rectangle then is the area of the rectangle itself.

I was hoping somebody would bring this up.

I purposefully asked about the minimum "white space" to recall BMAD and bonanova's triangle problem.

Of course, since a line has zero area, the area to my minimum white space question is almost certainly zero or the area of the entire rectangle - so the way I phrased that question is actually rather unnecessary. It was mostly to get people to think about how it is possible for an infinite series of lines to completely color a plane, in contrast to the solution for the fractal problem. If you look at bonanova's post on this thread, you can see how he defines "completely coloring the plane," and he is correct. If it is possible to calculate, for any point in the rectangle, the time at which the line crosses that point, then the rectangle is completely colored.

Your explanation is not the one I was looking for - although I have to admit that since this is an original problem, I am not quite sure of my own solution. Could you explain how you came upon this conclusion: "Then for any point within this area, there is a line that passes through this point at each and every angle from 0 to 360 degrees"? Isn't it sufficient for every point within the area to have just one line that passes through it?

Edited August 3, 2013 by gavinksong

[gavinksong]

Consider the trajectory as a straight line through an infinite square tiling of the plane. You then want the line to eventually cross every point on the replicated horizontal boundary. The trajectories through each square are parallel, so if every point on the horizontal boundary is touched, then every point in the replicated square will be touched as well. So what must be avoided is a rational relationship among those crossing points. By the way, this would also ensure every point on the vertical boundary is crossed.

I will throw out the following assertion, that yes, this can be done. The box is the unit square occupying the first quadrant. The path begins at the origin. It continues upward and to the right, hitting the upper boundary at x=pi/4, y=1.

It will require an uncountably infinite number of bounces, but no replicated point will be visited twice. For any given target point, one should be able to calculate the number of bounces needed for it to be visited. I guess that would be a proof.

So the question would be answered if the number of bounces can be calculated to visit say the point x=1/e, y=1/sqrt(2).

Edit:

Let x_o, y_o be the point in the box to be visited.

Let y = mx be the trajectory, beginning at the origin.

Let p be the number of horizontal traversals of the box

Let q be the number of vertical traversals of the box.

In the infinite tiling case, this means x = p + x_o, y = q + y_o.

Then ( q + y_o) = m ( p + x_o) or q = m ( p + x_o) - y_o

We seek a solution for integer values of p and q.

In the above case, q = (4/pi) ( p + 1/e) - 1/sqrt(2). Number of bounces is p + q.

So the answer to the OP is whether an integer solution exists.

This might boil down to finding a rational expression for an irrational number, which would be impossible.

These are all good observations.

In your original post, you predicted that it is possible to color the entire rectangle if the slope is irrational, but in your edit, it looks like you concluded that your equations might not have a solution. So it looks like it could go either way at this point.

Edited August 3, 2013 by gavinksong

[DeGe]

Your explanation is not the one I was looking for - although I have to admit that since this is an original problem, I am not quite sure of my own solution. Could you explain how you came upon this conclusion: "Then for any point within this area, there is a line that passes through this point at each and every angle from 0 to 360 degrees"? Isn't it sufficient for every point within the area to have just one line that passes through it?

Within an "area", if you consider any random point, then all the points around it must also be colored, meaning that there must be lines through this point in all possible directions, hence the 0 to 360 degree comment. The problem is similar to the triangle problem where the naked eye tells you that there is a "black area" but infact it is so because you choose the thickness of a point, or a line in this case. If instead of point bouncing off, you had a ball bouncing, I would definitely agree with Bonanova that the complete rectangle can be colored and a 0 white area left off as minimum

[Rainman]

We can't color a non-zero area (even in infinite time), and by extension we can't color the entire box.

Proof: We can list the lines which will ever be on the moving point's trajectory (first line, second line, third line, ..., n-th line, (n+1)-th line, ...), hence they are countably many. Let A be the set of points which will ever be colored. Suppose A has a non-zero area. Then A has an internal point P. Being an internal point, every point close to P must also be in A. Formally, there exists a d>0 such that if |P-P'|<d, then P' is in A. Now, there are uncountably many lines that pass through P, but only countably many that will ever be on the moving point's trajectory. So there must be a line L passing through P which will never be on the moving point's trajectory. Each line on the trajectory can only intersect L once. So there are only countably many intersection points on L which are also in A. However, there are uncountably many points P' on L such that |P-P'|<d, implying that there are uncountably many points on L which are also in A. This is a contradiction.

Note: DeGe has already made the observation about an internal point, but has not considered that the box may be of irregular shape.

Edited August 3, 2013 by Rainman

[gavinksong]

Your explanation is not the one I was looking for - although I have to admit that since this is an original problem, I am not quite sure of my own solution. Could you explain how you came upon this conclusion: "Then for any point within this area, there is a line that passes through this point at each and every angle from 0 to 360 degrees"? Isn't it sufficient for every point within the area to have just one line that passes through it?

Within an "area", if you consider any random point, then all the points around it must also be colored, meaning that there must be lines through this point in all possible directions, hence the 0 to 360 degree comment. The problem is similar to the triangle problem where the naked eye tells you that there is a "black area" but infact it is so because you choose the thickness of a point, or a line in this case. If instead of point bouncing off, you had a ball bouncing, I would definitely agree with Bonanova that the complete rectangle can be colored and a 0 white area left off as minimum

Just because all the points around a point are colored does not mean that there must be lines going through the point at all angles. Just consider the scenario where there are an infinite number of parallel lines going through all of the points.

In the triangle problem, it was because the "black areas" for a given initial point were in fact points-sized and were sparsely packed. In other cases, you can consider any solid area to be made up of an infinite number of points. The infinitesimal thickness of a line or a point is not sufficient to conclude that an area composed of an infinite number of these is also zero.

bonanova was getting very close to the answer.

[gavinksong]

We can't color a non-zero area (even in infinite time), and by extension we can't color the entire box.

Proof: We can list the lines which will ever be on the moving point's trajectory (first line, second line, third line, ..., n-th line, (n+1)-th line, ...), hence they are countably many. Let A be the set of points which will ever be colored. Suppose A has a non-zero area. Then A has an internal point P. Being an internal point, every point close to P must also be in A. Formally, there exists a d>0 such that if |P-P'|<d, then P' is in A. Now, there are uncountably many lines that pass through P, but only countably many that will ever be on the moving point's trajectory. So there must be a line L passing through P which will never be on the moving point's trajectory. Each line on the trajectory can only intersect L once. So there are only countably many intersection points on L which are also in A. However, there are uncountably many points P' on L such that |P-P'|<d, implying that there are uncountably many points on L which are also in A. This is a contradiction.

Note: DeGe has already made the observation about an internal point, but has not considered that the box may be of irregular shape.

This is honestly a much more complicated proof than I had in mind. To be honest, this is going to take me a while to read and understand. So give me a moment. Maybe several.

But first, I'll go ahead and say that you are correct in saying that the rectangle can never be colored completely, and that there IS a simpler explanation out there. And also, I meant for the box to be rectangular.

[Rainman]

It would be nice to see a proof that doesn't use the concept of countability

[gavinksong]

It would be nice to see a proof that doesn't use the concept of countability

That would be very impressive.

The explanation I have in mind does, but bonanova didn't really mention it in his post, so perhaps we will see one.

[gavinksong]

I have a proof:

Ok assume that the point isn't going vertically (otherwise it will remain on the same vertical line and never fill the box)

Assume the rectangle is a square with vertices (0,0) (0,1) (1,0) (1,1), we'll draw a vertical line inside the square at x=0.5.

Now let a_n be the y value of the point when it crosses the line for the n'th time, if the point was to cover the entire square then for every y in range [0,1] there must exist some n such that a_n=y, but this says that the range [0,1] is countable which we know it's not.

That is exactly right.

You didn't need make the assumption that it was a square or use coordinates, but using those formalities is probably good practice...

Good job!