• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Another interesting geometry problem

 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
(from a Maths Olympiad more than a decade ago)

You have four points A, B, C and D, in the same plane, no three points lying on a straight line.
(i.e. no three being collinear).
First question: find a point E in the plane such that AE + BE + CE + DE is minimal
Second question: prove that your answer to the first question is correct
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First guess for the first question after thinking about it for only twenty seconds:

Two cases: Either A, B, C, D make a convex or a concave quadrilateral.
- If convex, E is at the intersection of the two diagonals.
- If concave, E is at the one point that is at the concave angle.

Still thinking about it.

 
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's what I thought as well. Here's an argument (though probably not a proof) that it's at least a local minimum.

Case 1: Convex, with E the intesect of AC and BD.

Points on the line AC have a minimal value of AE + CE (and AE + CE is constant along that line). Points on the line BD have a minimal value of BE + DE. So we can minimise those two contributions independently, and that occurs at the intersection.

Case 2: Concave, with D within the triangle ABC.

Starting at D, any small move towards A keeps AE + DE unchanged. But both BE and CE increase, so the total sum of differences must increase. A similar argument applies to moving towards B or C. So any infinitesimal move in any other direction is also going to increase the sum (to the first order we can consider it a superposition in steps towards two of the other points.

So, which parts of that argument do you think need shoring up the most?
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That was the exact same "proof" I had in mind, but you put it more concisely than I was about to.

The only part that wasn't immediately obviously correct to me is if you let point E in case 2 move directly away from one of the points that make up the outer triangle. i.e. Point A, B or C to use your labeling. However, any movement of E directly away from A by some small amount x, adds 2x to the total distance because of AE and DE but only decreases the total distance for CE and BE by x multiplied by some sine or cosine for each. Ok, it took a couple seconds, but I'm convinced.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What if we remove the noncolinearity restriction? How many additional cases does that add, and what are the answers for those cases?
 
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

from a Maths Olympiad more than a decade ago



Did you take part?
 
Ivan Jozsef Balazs
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Case 1: Convex, with E the intesect of AC and BD.



Let us fabricate a horizontal table from a frictionless material and drill small holes at the points A,B,C,D into it.
Let us take equal weights and attach strings to them, and put the strings through the holes, and bind together to a point on the upper size of the table, with the weighs hanging down.
We then let the things loose and wait until they finds the equilibrium. The strings will stretch to make straight stages.

On the one hand the weights tend to hang towards the Earth as far as they can, so the sum of the strings hanging down below the table gets maximized, that is, the sum of the lengths on the table gets minimized.

On the other hand the middle point where the strings are stitched together does not move any longer if the forces working on it cancel out.

So for which point E is it true, that the unity vectors (the weigths are equal, so the gravity forces are equal) pointing from E towards A,B,C,D cancel each other out when summed up?
Well, two unity vectors pointing out from a given point yield a sum whose size is proportional to the cosine of the half angle between the directions, and the direction is that of the bisetrix.

From here it follows (I am not not able to provide a figure...) that the angle EA,EB must be equal to the angle EC,ED and the bisectrices must point to opposite directions, which is possible if E is the intesect of AC and BD.

(Huh, that was hard! Not only is English not my first language, arguably not even the second best, and even though I learned and studied maths, never in English.)

 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Ivan,

no, I did not attend this Olympiad! At my age, I'm glad enough to even remember the whole thing!

Still reading your last post, looks interesting, but I have not gotten it yet (again the old age?).

And for all the other contributions: to my shame I must admit that I only thought of normal, ordinary
day-to-day convex quadrilaterals. Therefore, I've kept very quiet all the time...

Greetz,
Piet
 
Ivan Jozsef Balazs
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Which part was not clear?

The physics part is a substitute for working with derivatives.

Let me rephrase the geometry part with complex numbers.
So we have four unity complex numbers (that is, ones with 1 as the absolute value) which sum up to zero and we want to prove that they cancel out pairwise.
(If one pair cancels out, then the other must also.)
So zi (i=1,2,3,4) are unity complex numbers and they sum up to zero:
z1+z2+z3+z4 = 0

z1+z2 = - z3 - z4

If both sides equal, so we can take the square of the absolute value, that is, if we multiply both sides with their complex conjugates:

(*) (z1+z2)(co(z1)+co(z2)) = the same with z3 and z4

Let ci denote co(zi), the conjugate value of zi.

zi is unity absolute value, so zi.ci = 1


So the left side of (*) looks like this:
(z1+z2).(c1+c2) = z1.c1 + z2.c1+z1.c2+z2.c2 = 2 + z2/z1 + z1/z2

The right side is 2 + z3/z4 + z4/z3

So z1/z2 + z2/z1 = z3/z4 + z4/z3

z2/z1 is a unity complex number, so it can be written like this: exp(i.a) = cos(a)+ i.sin(a)
then z1/z2 = cos(a)-i.sin(a) and z1/z2 + z2 / z1 = 2 .cos(a)

Likewise z3/z4 = exp(i.b) = cos(b) + i sin (b)
z4/z3 = cos(b) - i sin (b) and z3/z4 + z4/z3 = 2.cos(b)

So cos(a) and cos(b) equal! Then either sin(a)=sin(b) or sin(a)=-sin(b).

If on the one hand the sin values are equal, then z1/z2 = z3/z4, and let us denote this common value with w, so we have

0 = z1+z2+z3+z4 = w.z2+z2 + w.z4+ z4 = (1+w).(z2+z4)

Now if 1+w = 0, then w = -1, so z1 and z2 and z3 and z4 cancel out pairwise,
if 1+w != 0, then z2+z4 = 0.


If on the other hand sin(a)=-sin(b), then if w = cos(a)+i.sin(a) then z1/z2 = w, z4/z3 = w,
and the above computation can be applied for z1,z2,z4,z3:
either z1 and z2 and z3 and z4 cancel out pairwise, or z2+z3 = 0.

(RANT:
The forum software won't let me use the letter
The specific error message is: "u" is a silly English abbreviation; use "you" instead.

In theory I agree and also detest SMS-speak styled abbreviations in the forums, the letter is appropriate as a variable name. SIGH.
)
 
Ivan Jozsef Balazs
Rancher
Posts: 1044
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A friend suggests this solution for the following excercise:
There are 4 unity vectors in the plane which sum up to zero. It follows that they cancel out pairwise.

Here is why. We have four unity vectors z1,z2,z3,z4 that sum up to zero.
Let us consider the points 0, z1=X, z1+z2=Y, z1+z2+z3=Z, z1+z2+z3+z4=0.
So X and Z are both of unity distance from 0 and Y, so they either equal or they lie symmetric.

In either case, the vectors cancel out pairwise.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic