Sign in to follow this  
Followers 0

Points on the 2D plane...

6 posts in this topic

Posted · Report post

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: ornhaa.jpg
  2. Join: 2iru444.jpg join two points at their center of mass.
  3. Split: 2j3rvxy.jpg split a point into 2, notice this is not the inverse move to 2.
  4. Rotate, 264j8zr.jpg 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.

9se6qe.png

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)

2jbwmky.png

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).

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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

Edited by CaptainEd
0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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

Edited by CaptainEd
0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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 by CaptainEd
0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

Sorry I forgot to mention:

The split move needs to preserve the total mass, as in p = q1 + q2

sorry I forgot to mention that...

Edited by Anza Power
0

Share this post


Link to post
Share on other sites

Posted · Report post

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...

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.