wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Number of midpoints
        
(Message started by: Aryabhatta on Jul 3^rd, 2004, 6:17am)

Title: Number of midpoints
Post by Aryabhatta on Jul 3^rd, 2004, 6:17am

I saw this problem in an Iranian math olympiad I think.

You are given n [ge] 2 points in the 2-D plane. For each pair of points (P,Q) from the n points, mark the midpoint of PQ red. Show that there are at least 2n-3 distinct red points. For each n, show an arrangement of n points for which there are exactly 2n-3 distinct red points.

Title: Re: Number of midpoints
Post by TenaliRaman on Jul 3^rd, 2004, 12:29pm

::[hide]
Let me define < such that,
(a,b)<(c,d) if a<c or if(a==c and b<d)

Since the given n points are distinct, WLOG assume that
(x_1,y_1)<(x_2,y_2)<...<(x_n,y_n) ... (1)

given 1, it is easy to see that,
((x_1+x_2)/2,(y_1+y_2)/2)<((x_1+x_3)/2,(y_1+y_3)/2)<((x_1+x_4)/2,(y_1+y_4)/2)<...<((x_1+x_n)/2,(y_1+y_n)/2)<((x_2+x_n)/2,(y_2+y_n)/2)<((x_3+x_n)/2,(y_3+y_n)/2)<...<((x_[n-1]+x_n)/2,(y_[n-1]+y_n)/2)

So we have 2n-3 distinct values which proves part 1.

For part 2,
make all y's of the points equal.Then our inequality above reduces to comparison of only x's.

note that smallest sum in (1,2,3,...,n) is 3 and max sum is 2n-1, hence the range of possible sum is 2n-3.

so lets make (x_i,y_i) = (i,y_i), this configuration will have exactly 2n-3 midpoints.

(also u can keep the x's constant and put y_i=i giving the same result)
[/hide]::

Title: Re: Number of midpoints
Post by Barukh on Jul 4^th, 2004, 1:32am

Well done, TenaliRaman! Here’s how I did it.

[smiley=blacksquare.gif][hide]
Perform a parallel projection of the whole configuration (including red points) onto a line. Parallel projection preserves the “midpoint” property, and the number of red points cannot decrease.

Now, if the projections of given points are (from left to right) p₁, …, p_n, then the midpoints of the pairs p₁p₂, …, p_n-1p_n; p₁p₃, …, p_n-2p_n are all different, which gives the minimum of 2n-3 points.
[/hide][smiley=blacksquare.gif]

Title: Re: Number of midpoints
Post by Aryabhatta on Jul 4^th, 2004, 7:27am

Nice job Tenali and Barukh!

Here is another solution
:
[hide]

Assume n [ge] 3.
If points are P₁, P₂,..., P_n, we can always rearrange them as Q₁, Q₂,..., Q_n such that Q_i+1 lies outside the convex hull of Q₁, Q₂,..., Q_i [forall] i.

The case Q₁, Q₂,..., Q_n are collinear, we can show 2n-3 points easily. Suppose they are not.
Look at Q₁, Q₂ and Q₃. These give rise to 3 red points. Now adding Q₄, Q₅,...,Q_n in order gives rise to at least 2 additional red points with each new point added. Thus we have at least 2n-3 red points.
[/hide]
: