Author |
Topic: Number of midpoints (Read 426 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Number of midpoints
« on: Jul 3rd, 2004, 6:17am » |
 Quote  Modify
|
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.
|
| « Last Edit: Jul 3rd, 2004, 6:18am by Aryabhatta » |
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Number of midpoints
« Reply #1 on: Jul 3rd, 2004, 12:29pm » |
Quote Modify
|
::
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)
::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number of midpoints
« Reply #2 on: Jul 4th, 2004, 1:32am » |
Quote Modify
|
Well done, TenaliRaman! Here’s how I did it.
[smiley=blacksquare.gif]
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) p1, …, pn, then the midpoints of the pairs p1p2, …, pn-1pn; p1p3, …, pn-2pn are all different, which gives the minimum of 2n-3 points.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Number of midpoints
« Reply #3 on: Jul 4th, 2004, 7:27am » |
Quote Modify
|
Nice job Tenali and Barukh!
Here is another solution
:
Assume n [ge] 3.
If points are P1, P2,..., Pn, we can always rearrange them as Q1, Q2,..., Qn such that Qi+1 lies outside the convex hull of Q1, Q2,..., Qi [forall] i.
The case Q1, Q2,..., Qn are collinear, we can show 2n-3 points easily. Suppose they are not.
Look at Q1, Q2 and Q3. These give rise to 3 red points. Now adding Q4, Q5,...,Qn 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.
:
|
| « Last Edit: Jul 4th, 2004, 7:34am by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print