Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Thomas comments on Open thread, August 14 - August 20, 2017 - Less Wrong Discussion

2 Post author: Thomas 14 August 2017 07:48AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (57)

You are viewing a single comment's thread.

Comment author: Thomas 14 August 2017 07:51:03AM 2 points [-]

Another week, another open thread, another problem, too!

Comment author: Oscar_Cunningham 14 August 2017 10:59:39AM *  2 points [-]

EDIT: Clarified some things.

Suppose we have a bunch of spherical billiard balls rolling around on an infinite plane. Suppose there is no friction and the collisions are elastic. They don't feel the influence of gravity or any other force except the collisions. At least one ball is moving. Can they ever return to their original positions and velocities?

Comment author: cousin_it 14 August 2017 11:55:17AM *  3 points [-]

1) If only positions should match, then the answer is yes. Just roll two identical balls at each other.

2) If both positions and velocities should match, then the answer is no. Here's a sketch of a proof:

Assume without loss of generality that some balls have nonzero velocity along the X axis. Let's define the following function of time: take all balls having nonzero X velocity, and take the lowest X coordinate of their centers. A case analysis shows that the function can change from increasing to decreasing, but never the other way. Therefore it cannot be periodic. But since it's determined from the configuration, that means the configuration can't be periodic, QED.

Comment author: Oscar_Cunningham 14 August 2017 12:13:39PM 0 points [-]

Yep, that looks pretty airtight to me. Well done!

Comment author: cousin_it 15 August 2017 12:09:59PM *  0 points [-]

Note that the case analysis is tricky because the function can be discontinuous. The interesting cases are when a ball's X velocity becomes zero due to a collision, or (more subtly) two balls with only Y velocity gain X velocity due to an off-center collision. But I think the statement about monotonicity still holds.

Comment author: Oscar_Cunningham 15 August 2017 01:14:34PM 0 points [-]

Yeah I thought about those two cases as well, but I agree that they are correct. Perhaps we could make the proof a bit simpler by picking the X direction to be one that the balls never travel perpendicular too (although in fact I can't even think of a proof that such a direction exists).

Comment author: tgb 20 August 2017 04:10:30PM *  1 point [-]

The full answer is: they cannot return if there are only finitely many balls, but they can if there are infinitely many.

Let's first assume that there are finitely many balls. As Thomas pointed out, we can assume that the center of mass is fixed. Let's consider R defined to be the distance from the center of mass to the furthest ball and call that furthest ball B (which ball that is might change over time). R might be decreasing at the start - we might start with B going towards the center of mass. But if R decreased forever then we would know that they never return to their starting location (since R would be different)! So at some point it must become at least as large as it was at the start. At that point either the derivative of R is 0 or it is positive. In either case, R must increase forever onwards - which again shows it can't return to its original starting point. Why is it always increasing from that point onwards? Well, the only way for the ball B to turn around and start heading back towards the center is if there is another ball further away than it to collide with it. But that can't be, since B is the furthest out ball! (Edit: I see now that this is essentially equivalent to cousin_it's argument.)

For infinitely many balls, you can construct a situation where they return to their original position! We're going to put a bunch of balls on a line (you don't even need the whole plane). In the interval [0,1], there'll be two balls with initial velocity heading in towards each other at unit speed, with one ball at the left edge of the interval and one ball at the right. Then do the same thing for each interval [k,k+1]. When you let them go, each pair in each interval will collide and then be heading outwards with unit interval. Then they'll collide at the boundary with the next interval with the ball from the next interval. That sets them back at the starting position. I.e. all balls collide first with their neighbor on one side, then their neighbor on the other side, setting them back to their starting position.

Comment author: jmh 18 August 2017 03:54:28PM *  0 points [-]

Possibly not a rational answer (so possilbly not living up to the less wrong philosophy!) but given the assumption of an infinite plane I would think the probability is vanishingly small of returning to the original position and velocity.

Something would need to constrain the vectors taken to prevent any ball from taking off in some direction that could be described as "away from the group". Perhaps that could be understood be be on a path for which the the path of no other ball can possible intersect. At that point this ball can will never change it's current velosity and never return to it's oiginal position.

I cannot offer a proof that such a condition must eventually occur in your experimnt but my intuition is that it will. If so that vanishing small probablity that everyting return to some orginal state goes to zero.

Comment author: Thomas 14 August 2017 11:17:23AM 0 points [-]

Two balls which are orbiting around its common mass center, they do return to a previous position. If there is no gravity, a finite bunch of rolling balls will never again return to the present state. Never again.

Comment author: Oscar_Cunningham 14 August 2017 11:27:52AM 0 points [-]

I'm assuming no gravity (and that at least one ball is moving). Do you have a proof for your assertion?

Comment author: Thomas 14 August 2017 01:23:41PM 0 points [-]

Sure.

If the center of gravity moves, it moves with the velocity v. So it will be in the position r+v*t after some time t. Now it's at the position r. A different position of gravity (mass) center means different position. For the whatever finite t.

In the case when the gravity center doesn't move, you can divide the composition into two sub-compositions, where both gravity centers do move. If only one had moved, then the combined gravity center would move and we would have the solved case above.

But if both gravity centers move, they can either move apart and never collide - in which case they will both have different position vectors lately - or they will collide. In that case, they will reverse their directions after the elastic collision and we have a solved case then.

Well, that's an approximate proof.

Comment author: Oscar_Cunningham 14 August 2017 01:50:57PM 0 points [-]

But if both gravity centers move, they can either move apart and never collide - in which case they will both have different position vectors lately - or they will collide. In that case, they will reverse their directions after the elastic collision and we have a solved case then.

I'm not convinced by this bit. Usually we can calculate the results of an elastic collision by using both conservation of energy and conservation of momentum. But we can't know the energy of the sub-compositions based just on the velocity of their centres of mass. They will also have some internal energy. So we can't calculate the results of the collision.

Comment author: Thomas 14 August 2017 02:36:04PM 0 points [-]

Do we agree, that if there will be no collision, and both gravity centers move, that they will never return to the present position?

Comment author: Oscar_Cunningham 14 August 2017 02:44:27PM 0 points [-]

Yes.

Comment author: Thomas 14 August 2017 03:57:51PM 0 points [-]

Then, both gravity centers travel with a certain velocity each and will collide. How can they return back here? If they will reverse both velocities after the collision. Then, they can return. But with the opposite velocities, and therefore this will not be the same state.

Since they always move in lines, there will be no another collision. And therefore no return to the present state.

Comment author: Oscar_Cunningham 14 August 2017 07:17:10PM 0 points [-]

What do you mean by "the" collision? If each part has several balls then there will be multiple collisions.

Comment author: Thomas 16 August 2017 03:33:37PM *  0 points [-]

It's an old problem, cousin_it has posted:

Here's another problem that might be easier. Make an O(n log n) sorting algorithm that's simple, stable, and in place.

Radix. Except that it's not in place.

Comment author: cousin_it 17 August 2017 11:38:57AM *  0 points [-]

I know several reasonable algorithms for stable sorting in O(n log n) time and O(sqrt(n)) extra space, like Mrrl's SqrtSort. That's good enough for all practical purposes, because anyone who wants to sort a billion elements can afford an extra array of 30000 elements. And all known algorithms using less extra space essentially emulate O(sqrt(n)) bits of storage by doing swaps inside the array, which is clearly a hack.

Radix sort has its own rabbit hole. If you're sorting strings that are likely to have common prefixes, comparison sorting isn't the best way, because it needs to look at the initial characters over and over. There are many faster algorithms for string sorting based on ideas from radix sort: American flag sort, three-way radix quicksort, etc. The Haskell package Data.Discrimination generalizes the idea from strings to arbitrary algebraic datatypes, allowing you to sort them in almost linear time (in terms of total size, not number of elements).