Life In 19x19
http://prod.lifein19x19.com/

geometry problem ( that nagged me )
http://prod.lifein19x19.com/viewtopic.php?f=8&t=4609
Page 1 of 1

Author:  cyclops [ Tue Sep 06, 2011 8:12 am ]
Post subject:  geometry problem ( that nagged me )

You have four points in a plane and one euro. The euro cannot cover all four points ( at once, OC ). Prove that this euro cannot cover some three of these points.

( for the blessed among us : the euro is a coin in the form of a circle. Shrinking too fast, though)

Author:  daniel_the_smith [ Tue Sep 06, 2011 8:22 am ]
Post subject:  Re: geometry problem ( that nagged me )

Is there some additional constraint? It seems relatively easy to put 3 points in a plane that can be covered by a circle, with one far away.

Perhaps the plane is a square the same size as the coin? Edit: nah, even that doesn't help.

Author:  entropi [ Tue Sep 06, 2011 8:22 am ]
Post subject:  Re: geometry problem ( that nagged me )

cyclops wrote:
You have four points in a plane and one euro. The euro cannot cover all four points ( at once, OC ). Prove that this euro cannot cover some three of these points.

( for the blessed among us : the euro is a coin in the form of a circle. Shrinking too fast, though)


As the question is formulated, it cannot be proven because the euro can cover some three of these points even if the fourth point is too far away to be covered. But are there some constraints for the locations of the four points in the plane???

Author:  Tryss [ Tue Sep 06, 2011 8:32 am ]
Post subject:  Re: geometry problem ( that nagged me )

I believe you should read it as : "Prove that this euro cannot cover every group of 3 points"

Author:  Laman [ Tue Sep 06, 2011 8:35 am ]
Post subject:  Re: geometry problem ( that nagged me )

daniel_the_smith, entropi: i understand it differently - you have four points in a plane, their only property is that they cant be all covered by a single unit circle. prove that among these four points exists at least one group of three points that has the same property

EDIT: too late, Tryss wrote it first

Author:  jts [ Tue Sep 06, 2011 9:03 am ]
Post subject:  Re: geometry problem ( that nagged me )

This is equivalent to asking whether for some scalar D there exists point a s.t. d(a,x)<D/2, d(a,y)<D/2, etc., for all the points that the "Euro" covers.

If d(a,x)<D/2, then if d(a,y)<D/2, then d(x,y)<D. (And vice-versa, of course).

If no point a exists for {w,x,y,z}, then that implies there is at least one of d(w,x), d(w,y)... etc. such that d(-,-)>D. If that is true, then the point a doesn't exist for at least one of {w, x, y}, {w, y, z}, {x, y, z}, {w, x, z}, because collectively those four triplets require d(-,-)<D for all six of the pairs.

Author:  HermanHiddema [ Tue Sep 06, 2011 9:05 am ]
Post subject:  Re: geometry problem ( that nagged me )

If a set of points is entirely within a certain circle of radius X, then the distance between any two of them is at most 2X.

Conversely, if a set of point is not entirely within some circle of radius X, then there exist at least two points within the set whose mutual distance is larger then 2X.

The given set of four points therefore contains at least two points whose mutual distance is larger than the diameter of the euro coin. Those two points cannot, therefore, be covered simultaneously by the euro coin.

Given that there exists at least one set of two points that cannot simultaneously be covered, there also exist at least two sets of three points that cannot be covered by said euro coin.

Author:  emeraldemon [ Tue Sep 06, 2011 9:22 am ]
Post subject:  Re: geometry problem ( that nagged me )

HermanHiddema wrote:
Conversely, if a set of point is not entirely within some circle of radius X, then there exist at least two points within the set whose mutual distance is larger then 2X.


I don't think this is true. Imagine a triangle, then the smallest circle containing that triangle. Unless the points are colinear, the largest distance between two of the points will be less than 2*radius. So if you increase the distance of those two points a tiny bit, you will have 3 points that cannot fit in the circle of that radius, but the distance is still less than 2*radius. Unless I'm misunderstanding, jts's method has the same flaw.

Author:  Tryss [ Tue Sep 06, 2011 9:25 am ]
Post subject:  Re: geometry problem ( that nagged me )

Quote:
Conversely, if a set of point is not entirely within some circle of radius X, then there exist at least two points within the set whose mutual distance is larger then 2X.

This is wrong:
Take X = 1 and the points of affixes :
A(0,sqrt(3))
B(-1,0)
C(1,0)
D(0,1-sqrt(3))

You have d(A,B) = d(A,C) = d(A,D)= d(B,C) = 2 and d(B,D) = d(C,D) = sqrt(5-2sqrt(3)) < 2, but you don't have a point a where d(a,-)<1 for each point in {w,x,y,z}. The smaller circle that cover every 4 points has a radius of 2/sqrt(3) > 1 (the 4 points are concyclics)

Author:  cyclops [ Tue Sep 06, 2011 2:20 pm ]
Post subject:  Re: geometry problem ( that nagged me )

Laman wrote:
daniel_the_smith, entropi: i understand it differently - you have four points in a plane, their only property is that they cant be all covered by a single unit circle. prove that among these four points exists at least one group of three points that has the same property

EDIT: too late, Tryss wrote it first

thx, Laman and Tryss: you both restated the problem correctly.

Author:  Li Kao [ Wed Sep 07, 2011 2:30 am ]
Post subject:  Re: geometry problem ( that nagged me )

One interesting observation is that this is not true for 4 points in 3D. (A Tetraeder violates this).

My impression is that a square is the shape that comes closest to violating this rule, but it holds even for it. But how to prove that...

Author:  entropi [ Wed Sep 07, 2011 3:54 am ]
Post subject:  Re: geometry problem ( that nagged me )

Li Kao wrote:
One interesting observation is that this is not true for 4 points in 3D. (A Tetraeder violates this).


Likewise, it is also not true for 3 points in 2D because a triangle violates it (see emeraldemon's post above).

cyclops, do you have an answer for the question? Apparently it is not as easy as it looks.

Author:  cyclops [ Wed Sep 07, 2011 4:15 am ]
Post subject:  Re: geometry problem ( that nagged me )

entropi wrote:
cyclops, do you have an answer for the question? Apparently it is not as easy as it looks.


I got it from the book I mentioned in my previous thread about math problem. There are hints in it. I intend to publish asap.
Also there are answers. I'll publish it as soon as the discussion here fades out.
I didn't read the hint or solution yet. Although I am very curious!
I took this problem with me on my holiday trip, trekking in the Alps. I must say I got a little bit frustrated. Trying to solve it in my head didn't work.

edit: maybe some people doubt the preposition. In that case it should be easy find a counterexample. One is enough.

Author:  perceval [ Wed Sep 07, 2011 4:54 am ]
Post subject:  Re: geometry problem ( that nagged me )

lets reverse the problem:
put a coin on each of th 4 points:
if the 4 coin overlap, you can center a coin on the overlapping region and it will cover everything.
now lets assume that you have 3 overlapping circle of the same radius R:C1,C2,C3
try to draw a 4th circle o that intersect all three circles but NOT the common region: impossible.

now to prove that mathematically..
lets assume that C1,C2, C3 have a non empty intersection , lets take a point A
lets assume that C1,C2, C4 have a non empty intersection , lets take a point B in it
lets assume that C1,C3, C4 have a non empty intersection , lets take a point C
lets assume that C2,C3, C4 have a non empty intersection , lets take a point D in it

my bet is that the barycenter of A,B,C,D will be in all 4 circles.ie it will be a valid choice.


i guess it is related to the convexity of those intersections: if A and B are in an intesection, the whole [A,B] segment is, and the barycenter of 4 point in on the semgent between all 2 by 2 barycenter.

i need to work a bit (real work that pays the bill) i ll come back

Author:  cyclops [ Wed Sep 07, 2011 6:23 am ]
Post subject:  Re: geometry problem ( that nagged me )

I hided the book for myself, but found it again. "The green book of mathematical problems" by Kenneth Hardy and Kenneth S. Williams, 1985, ISBN 0-486-69573-5 (pbk).

Definition: A unit disk is a disk of unit radius. That is its radius is 1.

Problem 88: ( As stated in the book). If four distint points lie in the plane such that any three of them can be covered by a unit disk then all four points can be covered by a unit disk.

Hint, if you use it please hide your solution for a few days
Given 4 points in a plane one of the following is true:
1. One of the points is in or at the triangle formed by the remaining 3 points.
2. The 4 points form a quadrilateral with intersecting diagonals.

please hide your solution for a few days

Author:  perceval [ Wed Sep 07, 2011 12:49 pm ]
Post subject:  Re: geometry problem ( that nagged me )

maybe i got it:

hint:
A convex set is a set S such as if A and B are in S, all points in the segment [A,B] are in S.
-disks are convex/ if K and L are such that d(A,K)<R and d(A,L)<R; d(A,P)<R for each point in [K,L]
that is because on the line K,L you can write:
f(x)=d(x,A)=sqrt(r2+x2)
(here r is the min distance between the (KL) line and A)
the function as a minimum at x=0 but no local maximum;
so for each x,x1,x2 such as x1<x <x2
f(x)< max(f(x1),f(x2));
==>D(A,P)<R if p between K and L

- an intersection of convex sets is a convex (obvious)


proposed solution/
i was still thinking about a convexity argument and here is what got:
You have your 4 points A,B,C,D.
suppose you can cover A,B,C with a circle of radius R centered in K
... A,B,D with a circle of radius R centered in L
... A,C,D with a circle of radius R centered in M
B,C,D with a circle of radius R centered in N
1)
The convexity argument is as follow:
as d(A,K) <R AND (A,L)<R , D(A,P)<R for each point between K and L; same thing for d(B,P)
And we have equivalent properties for all 6 segment made of 2 points ou of K,L;M,N

2)now:
lets assume that the segment [K,L] and [M,N] intersects
by the property above the intersection I is such that d(I,A)<R, d(I,B)<R (because I is on [K,L]), and d(I,C)<R and d(I,D)<R (becasue I is on [M,N])
a centre of radius R centerd at I will cover A,B,C and D
same thing if any 2 other segment intersect of course
3)
now what if there is no such intersection?
fo example K=(0,-1);L=(0,+1),M=(2,0) N=( 1,0) : no pair of segment intersects
in that case i think we are still ok:
it means that one of the 4 points is inside the triangle made by the 3 others (i am not sure how to demonstrate that but it seems obvious if you try to draw).
Edit: that is actually exactly cyclops hint :clap: so this is a good track
in the example N is inside the triancle K, L, M :
K; L and M are all inside the circle of radius R centered in A, so N is inside the circle too (convexity again):

so N is a good candidate:
d(N,A)<R and by definition of N: d(N,B)<R,d(N,C)<R d(N,D)<R
a centre of radius R centered at N will cover A,B,C and D
there is probably something more beautiful :scratch:

Author:  cyclops [ Wed Sep 07, 2011 2:52 pm ]
Post subject:  Re: geometry problem ( that nagged me )

perceval wrote:
maybe i got it:

Congratulations. You are too clever for my problems. I doubt there is a more elegant solution. It is the solution of the book.
For the missing link see:


Edit: oops, corrected two terrible grammatical errors. Shame on me.

Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/