dcordb's blog

Help with this problem from NEERC 2008
By dcordb, 7 years ago, In English

Hello.

I was doing this problem (problem G) from NEERC 2008.

The problem basically says that you are given N points and in a minute all the points connect to all the others points, forming segments, now you choose the center of each segment as new points an delete the old ones. You have to say the time where one point is generated by at least 2 segments or say is 0 if it never happens.

I realized that if N ≤ 3 the answer is 0, if two different segments cuts in the middle then the answer is 1. And by looking to the solutions I saw that the answer is 2 in other case. Why does this happen, can anybody proof this?

Thank you.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If there is four point P, Q, W, Z, at the beggin we can form all the middle points , mid(P,Q) , mid(P,W) , mid(P,W) , mid(P,Z) , mid(Q,W) , mid(Q,Z) and mid(W,Z), in the second turn we can form -> mid(mid(P,W) , mid(Q,Z)) and mid(mid(W,Z) , mid(P,Q)) and mid(mid(W,Z) , mid(P,Q)) = mid(mid(P,W) , mid(Q,Z)) and we are done =)

→ Reply