Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Points on the 2D plane...


  • Please log in to reply
5 replies to this topic

#1 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 07 June 2012 - 08:56 PM

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.
  • Move: Posted Image
  • Join: Posted Image join two points at their center of mass.
  • Split: Posted Image split a point into 2, notice this is not the inverse move to 2.
  • Rotate, Posted Image 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.
Posted Image

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)

Posted Image

And so on.

Spoiler for hint

  • 0

#2 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 June 2012 - 10:16 PM

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

Edited by CaptainEd, 07 June 2012 - 10:25 PM.

  • 0

#3 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 June 2012 - 11:07 PM

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

Edited by CaptainEd, 07 June 2012 - 11:11 PM.

  • 0

#4 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 June 2012 - 11:53 PM

Spoiler for Third time's a charm?

Edited by CaptainEd, 07 June 2012 - 11:54 PM.

  • 0

#5 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 08 June 2012 - 08:21 AM

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, 08 June 2012 - 08:23 AM.

  • 0

#6 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 15 June 2012 - 03:24 PM

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




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users