Author |
Topic: 2005 Points, Even Triangles (Read 2067 times) |
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
 |
2005 Points, Even Triangles
« on: Nov 26th, 2006, 9:30pm » |
 Quote  Modify
|
Someone in another forum had asked this BMO problem, which sort of intrigued me. I believe it should have a very neat elegant solution albeit it sort of eludes me so far,
Let T be a set of 2005 coplanar points with no three collinear. Show that, for any of the 2005 points, the number of triangles it lies strictly within, whose vertices are points in T, is even.
-- AI
|
|
 IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2005 Points, Even Triangles
« Reply #1 on: Nov 27th, 2006, 5:01pm » |
Quote Modify
|
Cute problem. Nothing sacred about 2005 except that it is odd; the conclusion is false for this year. So one can experiment with a smaller odd number of points until something clicks.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 2005 Points, Even Triangles
« Reply #2 on: Nov 27th, 2006, 5:12pm » |
Quote Modify
|
I suspect it is true for any odd number of such points. This suggests one approach could be to prove it by induction. The result is trivial for 3 points (each lies within 0 triangles). Now assume it is true for odds up to 2n-1, and show it for 2n+1.
[ edit ] Not sure how I spent 11+ minutes on this, but ecoist hadn't replied when I started.[ /edit ]
|
| « Last Edit: Nov 27th, 2006, 5:13pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 2005 Points, Even Triangles
« Reply #3 on: Nov 27th, 2006, 9:26pm » |
Quote Modify
|
on Nov 27th, 2006, 5:01pm, ecoist wrote:| Cute problem. Nothing sacred about 2005 except that it is odd; the conclusion is false for this year. So one can experiment with a smaller odd number of points until something clicks. |
|
Yeah thats what i tried to do. 3 points is trivial and 5 point is very easy. But, extending the idea to higher numbers is where i was having trouble or rather i went blank at that point.
on Nov 27th, 2006, 5:12pm, Icarus wrote:I suspect it is true for any odd number of such points. This suggests one approach could be to prove it by induction. The result is trivial for 3 points (each lies within 0 triangles). Now assume it is true for odds up to 2n-1, and show it for 2n+1.
[ edit ] Not sure how I spent 11+ minutes on this, but ecoist hadn't replied when I started.[ /edit ] |
|
As i mentioned, extending it for higher values is what i am not able to see at the moment. 
-- AI
|
| « Last Edit: Nov 27th, 2006, 9:26pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2005 Points, Even Triangles
« Reply #4 on: Nov 27th, 2006, 10:26pm » |
Quote Modify
|
Ok, TanaliRaman. How about breaking the problem into two parts, those points on the convex hull of T and those points interior to that convex hull?
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: 2005 Points, Even Triangles
« Reply #5 on: Nov 28th, 2006, 9:55am » |
Quote Modify
|
i was thinking the same as Tenali and Ecoist.
Three as mentioned is trivial.
For five, there are two cases.
Consider four points forming a quadrilateral and the fifth lying within that quadrilateral and not lying on any of the diagonals. In that case, it is easy to see that the fifth point is contained within 2 triangles.
Consider the case when the fifth is outside the quadrilateral (e.g. pentagon), in which case 0 triangles have any point within them. Thus looks like instead of a single even number you can have a series of even numbers as answers depending on arrangement.
Now, as Icarus suggested let's assume 2k-1 points are contained within 2m triangles.
So for 2k+1 points, we have two additional points. This marks an increase of ( 2k+1,3) - (2k-1,3)
= (2k+1)(2k)(2k-1)/6 - (2k-1)(2k-2)(2k-3)/6
= (2k-1)/3 * [(2k+1)(k) - (k-1)(2k-3)]
= (2k-1)/3 * [2k^2 + k - 2k^2 +4k -3]
= (2k-1)(5k-3)/3
These are total increase in triangles. Now I have no idea how to show that only even number of these triangles actually contain any of those points.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2005 Points, Even Triangles
« Reply #6 on: Nov 28th, 2006, 2:51pm » |
Quote Modify
|
My proof just collapsed! So my suggestion is worth what you paid for it.
|
|
IP Logged |
|
|
|
azalia
Newbie
Posts: 36
|
|
Re: 2005 Points, Even Triangles
« Reply #7 on: Nov 28th, 2006, 5:35pm » |
Quote Modify
|
I haven't worked it all out, so this might be pointless, but I think I see a direction for a solution.
First, instead of taking an odd set of points and proving it for each point, consider taking an even number of points and proving every region where the next point could go is in an even number.
Next, note that the converse is not true. When you have an odd number of points, there are both even and odd regions within the convex hull.
That means that when the next point is added, every even region will get an even number of additional triangles, while every odd region will get an odd number, even though some regions will be split in half and both halves won't get the same number of triangles.
That led me to add points one at a time and only count how many triangles are added by the new point. I mainly checked regular polygons, but I also checked one or two more complex sets of points, and it seems that when a new point is added, every region that was along the outside border of the previous convex hull gets 1 new triangle. Every region that is one space farther toward the newly added point gets 2, and for the next region in, 3.
That explains why the count parity switches from all even to some even and odd to all even again.
I know this isn't a formal proof, and it still has to be confirmed with the more complex arrangements, but it seems to be the general answer.
|
| « Last Edit: Nov 28th, 2006, 6:43pm by azalia » |
IP Logged |
|
|
|
azalia
Newbie
Posts: 36
|
Here are a couple examples of going from 5 points to 6. The blue regions were within 3 triangles when we had 5 points; the white were in 4 and the reds were in 5 triangles. Adding the sixth green point increased each space by the listed numbers. The increases climb by one as you start at any edge of the former hull and move toward point six.
|
|
IP Logged |
 |
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 2005 Points, Even Triangles
« Reply #9 on: Nov 28th, 2006, 7:52pm » |
Quote Modify
|
People seem to be overlooking the second case with 4 points - where they form a triangle with interior point (OK, or a non-convex quadrilateral) - granted it may be being included as a special case, but it's not immediately obvious that convex and non-convex quadrilaterals would have the same behaviour (for instance, the triangle has only 3 interior regions where the quadrilateral has 4)
On the other hand, I think azalia's approach solves the problem anyway.
Assume that any arrangement with 2n points consists solely of "even" regions (labelling regions as "even" or "odd" according to the number of triangles that region is in).
Now consider an arbitrary arrangement with 2n+1 points. We want to show that, for any two neighbouring regions, one is odd and the other even (note that the exterior region is trivially even, being in 0 triangles, so the odd/even labelling is completely specified this way).
Pick any point, P, in that arrangement, and removing it will leave an all even arrangement (by hypothesis). Call the triangles that would be removed this way P-triangles. Extending the lines radiating from P through the other 2n points divides the arrangement into 2n wedges (one between each adjacent pair of rays). Considering a single wedge, each line that crosses it represents a unique pair of points, which form a unique P-triangle that overlaps the wedge on the side of the line nearer P, and not on the other, meaning that the number of P-triangles a given region within the wedge is in increases by 1 as you cross a line moving towards P. Since the regions within the wedge would all be even without the P-triangles, for each pair of adjacent regions within the wedge, one must be odd, and the other even. To extend the proof to all pairs of adjacent regions, just observe that, if two regions are adjacent across a segment of line PQ, then taking wedges from the closest point other than P or Q will put them adjacent in the same wedge, so one must be odd and the other even. So for any arrangement of 2n+1 points, adjacent regions must have opposite parities as required.
With 2n+2 points, the same argument shows that adjacent regions within a wedge must have the same parity (they had opposite parities and the number of additional triangles each is in also has opposite parities) so all regions must have the same parity. Since the exterior is still even, all arrangements with 2n+2 points must be all even.
Since the two arrangements with 4 points are both all even, the induction works.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 2005 Points, Even Triangles
« Reply #10 on: Nov 29th, 2006, 10:13am » |
Quote Modify
|
Interesting problem Tenali...
It seems like a counting problem:
Suppose there are n points.
Assume that the points are such, that none of the lines formed cross the first quadrant. (positive x and positive y)
Let the total number of lines be N. Say the lines are L1, L2, ..., LN. Each line separates the plane into 2 regions, the positive half which contains the origin and the negative half which does not contain the origin.
Now for each point P, it lies on exactly n-1 of those lines. For the remaining N-n+1 lines, separate the lines into two sets POS and NEG as follows:
Given any line Lj it is in POS if point P is in the positive half of that line, else the line goes in NEG.
Now the triangles in which P lies can be found by picking 3 lines, such that two lines are from one of POS, NEG and the third is from the other set.
Let |POS| = p and |NEG| = m
and assume p >= 2 and m >= 2.
The number of triangles which contain P is
m(m-1)/2 * p + p(p-1)/2 * m = mp(m+p-2)/2
Now if N-n+1 = m+p = 2 (mod 4) then the number of such triangles is even. This seems to be the case when n = 2005.
If m < 2 or p < 2, the number of triangles which contain point P is 0.
I haven't tried proving everything. Also, it does look like it need not be true for all odd numbers as seems to be the consensus. I haven't read rmsgrey's proof though.
[EDIT] The above does not look correct. Back to the drawing board [/EDIT]
|
| « Last Edit: Nov 29th, 2006, 12:36pm by Aryabhatta » |
IP Logged |
|
|
|
steall
Newbie
Posts: 1
|
|
Re: 2005 Points, Even Triangles
« Reply #11 on: Dec 3rd, 2006, 1:56pm » |
Quote Modify
|
Different solution (I think):
Consider a point P in a set containing an odd number of points. Add two points Q and R to the set. The lines PQ and PR divide the plane into four sections, defined as follows:
Q and R lie on the boundary of section A.
Q lies on the boundary of section B.
R lies on the boundary of section C.
Neither lie on the boundary of D.
Let a=number of points strictly within A etc.
Consider the different ways of adding triangles containing P:
Case 1: Vertices of triangle are Q, a point in C and a point in D: cd triangles containing P added.
Case 2: Vertices are R, point in B and point in D: bd triangles containing P added.
Case 3: Two vertices are a point in A and a point in D: ad triangles containing P added, third vertex either Q or R depending on circumstance.
Case 4: Two vertices are point in B and a point in C: either 0 or 2 triangles containing P added, depending on circumstance; let total number added be 2m.
Case 5: Vertices are Q, R and a point in D: d triangles containing P added.
All other cases do not add triangles containing P.
Total number of relevant triangles added is therefore (ad+bd+cd+d+2m)=d(a+b+c+1)+2m=(d(S-d)+2m) where S is the total number of points in the original set (including P).
If d is odd then (S-d) is even since S is odd. Therefore d(S-d)+2m is even. QED by induction.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2005 Points, Even Triangles
« Reply #12 on: Dec 3rd, 2006, 3:33pm » |
Quote Modify
|
Such clarity! Danke sehr, steall!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print