It is currently Sat May 10, 2025 8:06 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 17 posts ] 
Author Message
Offline
 Post subject: geometry problem ( that nagged me )
Post #1 Posted: Tue Sep 06, 2011 8:12 am 
Lives in sente
User avatar

Posts: 801
Location: Amsterdam (NL)
Liked others: 353
Was liked: 107
Rank: KGS 7 kyu forever
GD Posts: 460
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)

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #2 Posted: Tue Sep 06, 2011 8:22 am 
Gosei
User avatar

Posts: 2116
Location: Silicon Valley
Liked others: 152
Was liked: 330
Rank: 2d AGA
GD Posts: 1193
KGS: lavalamp
Tygem: imapenguin
IGS: lavalamp
OGS: daniel_the_smith
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.

_________________
That which can be destroyed by the truth should be.
--
My (sadly neglected, but not forgotten) project: http://dailyjoseki.com


Last edited by daniel_the_smith on Tue Sep 06, 2011 8:36 am, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #3 Posted: Tue Sep 06, 2011 8:22 am 
Lives in gote

Posts: 493
Liked others: 80
Was liked: 71
Rank: sdk
GD Posts: 175
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???

_________________
If you say no, Elwood and I will come here for breakfast, lunch, and dinner every day of the week.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #4 Posted: Tue Sep 06, 2011 8:32 am 
Lives in gote

Posts: 502
Liked others: 1
Was liked: 153
Rank: KGS 2k
GD Posts: 100
KGS: Tryss
I believe you should read it as : "Prove that this euro cannot cover every group of 3 points"

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #5 Posted: Tue Sep 06, 2011 8:35 am 
Lives in gote
User avatar

Posts: 655
Location: Czechia
Liked others: 29
Was liked: 41
Rank: 1d KGS
KGS: Laman
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

_________________
Spilling gasoline feels good.

I might be wrong, but probably not.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #6 Posted: Tue Sep 06, 2011 9:03 am 
Oza
User avatar

Posts: 2659
Liked others: 310
Was liked: 631
Rank: kgs 6k
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.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #7 Posted: Tue Sep 06, 2011 9:05 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #8 Posted: Tue Sep 06, 2011 9:22 am 
Gosei
User avatar

Posts: 1744
Liked others: 704
Was liked: 288
KGS: greendemon
Tygem: greendemon
DGS: smaragdaemon
OGS: emeraldemon
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.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #9 Posted: Tue Sep 06, 2011 9:25 am 
Lives in gote

Posts: 502
Liked others: 1
Was liked: 153
Rank: KGS 2k
GD Posts: 100
KGS: Tryss
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)

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #10 Posted: Tue Sep 06, 2011 2:20 pm 
Lives in sente
User avatar

Posts: 801
Location: Amsterdam (NL)
Liked others: 353
Was liked: 107
Rank: KGS 7 kyu forever
GD Posts: 460
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.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #11 Posted: Wed Sep 07, 2011 2:30 am 
Lives in gote
User avatar

Posts: 643
Location: Munich, Germany
Liked others: 115
Was liked: 102
Rank: KGS 3k
KGS: LiKao / Loki
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...

_________________
Sanity is for the weak.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #12 Posted: Wed Sep 07, 2011 3:54 am 
Lives in gote

Posts: 493
Liked others: 80
Was liked: 71
Rank: sdk
GD Posts: 175
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.

_________________
If you say no, Elwood and I will come here for breakfast, lunch, and dinner every day of the week.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #13 Posted: Wed Sep 07, 2011 4:15 am 
Lives in sente
User avatar

Posts: 801
Location: Amsterdam (NL)
Liked others: 353
Was liked: 107
Rank: KGS 7 kyu forever
GD Posts: 460
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.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #14 Posted: Wed Sep 07, 2011 4:54 am 
Lives in gote
User avatar

Posts: 312
Liked others: 52
Was liked: 41
Rank: 7K KGS
KGS: tictac
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

_________________
In theory, there is no difference between theory and practice. In practice, there is.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #15 Posted: Wed Sep 07, 2011 6:23 am 
Lives in sente
User avatar

Posts: 801
Location: Amsterdam (NL)
Liked others: 353
Was liked: 107
Rank: KGS 7 kyu forever
GD Posts: 460
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

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #16 Posted: Wed Sep 07, 2011 12:49 pm 
Lives in gote
User avatar

Posts: 312
Liked others: 52
Was liked: 41
Rank: 7K KGS
KGS: tictac
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:

_________________
In theory, there is no difference between theory and practice. In practice, there is.

Top
 Profile  
 
Offline
 Post subject: Re: geometry problem ( that nagged me )
Post #17 Posted: Wed Sep 07, 2011 2:52 pm 
Lives in sente
User avatar

Posts: 801
Location: Amsterdam (NL)
Liked others: 353
Was liked: 107
Rank: KGS 7 kyu forever
GD Posts: 460
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 17 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group