Points on the 2D plane...

[Anza Power]

This question has been posed to us by our Algorithms teacher, anyone who solved it would've gotten a bonus directly on the final grade and they did not state that only 1 person may solve it, we were given more than 3 months yet still no one in the entire course was able to solve it, can you?

The puzzle is a game, on the XY plane you have points and each point has a weight, we start off with two points at (1,0) and (0,1) each with weight of 0.5.

The object of the game is to use a set of allowed operations to move/split/join/rotate the points in order to end up with exactly 1 point at coordinates (x,y) where x,y<=2/3 (in other words your point has to be in the square defined by (0,0) (2/3,2/3) )

The x y coordinates of the points must remain non-negative, and weights must remain positive.

The allowed moves are as follows (note the writing p(x,y) or [p](x,y) means a point at coordinates (x,y) with weight p), for moves that are done on two or more points all the points must be on the same horizontal or vertical line.

1. Move:
   
2. Join: join two points at their center of mass.
   
3. Split: split a point into 2, notice this is not the inverse move to 2.
   
4. Rotate, some more explanation can be found below.
   

Explanation for Rotate: for k=1 the operation is useless, for k=2 we can calculate that:

START = [1/12](r-2d) , [1/6](r+d)

END = [1/12](r+2d) , [1/6](r-d)

Since we can multiply the weights by epsilon the exact weights themselves don't matter what matters is the relationship between the weights, now we can see that if you have point P1 with weight w and point P2 with weight 2w and they are 2d units apart (P1 is closer to 0 than P2), then we can rotate them around their center of mass, moving P1 4d units ahead but point P2 2d units back.

For k=3 you can calculate that the relations are:

START = [1](r-3d) , [5](r-d) , [4](r+2d)

END= [1](r+3d) , [5](r+d) , [4](r-2d)

And so on.

Notice for k>=2, the 4th type of movement preserves the point's center of mass, also the join, the move always pushes the center of mass upwards or left and the split operation as far as I know always raises the center of mass as well, at the start the center of mass of the entire system is at (0.5 , 0.5) and each move only raises it's coordinates so at all time in the game your the center of mass of all the points must stay below (2/3 , 2/3).

[CaptainEd]

(Answer removed, had not noticed that (d > 0). I knew it was too easy!)

Edited June 7, 2012 by CaptainEd

[CaptainEd]

(I"m wrong again, but the split appears to allow the COG to move inward...)

Edited June 7, 2012 by CaptainEd

[CaptainEd]

1) .5(0,1) -> .5(1,1) // move bottom point to (1,1)

2) .5(1,0) -> .5(1,1) // move left point to (1,1)

3) .5(1,1) + .5(1,1) -> 1(1,1) // merge two points on y = 1, say

4) 1(1,1) -> 1/3( 2/3, 1) + 1/3( 2/3, 1) // split, same y

5) 1/3(2/3,1) + 1/3(2/3,1) = 2/3 (2/3, 1) // merge, same y

6) 2/3( 2/3, 1) -> 2/9 (2/3, 2/3) + 2/9 (2/3, 2/3) //split, same x

7) 2/9 (2/3, 2/3) + 2/9 (2/3, 2/3) -> 4/9 (2/3, 2/3) // merge, same x

Edited June 7, 2012 by CaptainEd

[Anza Power]

Sorry I forgot to mention:

The split move needs to preserve the total mass, as in p = q₁ + q₂

sorry I forgot to mention that...

Edited June 8, 2012 by Anza Power

[CaptainEd]

Are you sure the JOIN doesn't preserve the center of mass?

Thank you for the statement that the SPLIT is not the inverse of JOIN--it really does look like SPLIT; JOIN does move the COM away from the origin.

Thank you for a very tough problem. My reticence in the last week has not been due to lack of interest, but lack of progress...