wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 2005 Points, Even Triangles
        
(Message started by: TenaliRaman on Nov 26^th, 2006, 9:30pm)

Title: 2005 Points, Even Triangles
Post by TenaliRaman on Nov 26^th, 2006, 9:30pm

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

Title: Re: 2005 Points, Even Triangles
Post by ecoist on Nov 27^th, 2006, 5:01pm

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.

Title: Re: 2005 Points, Even Triangles
Post by Icarus on Nov 27^th, 2006, 5:12pm

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 ]

Title: Re: 2005 Points, Even Triangles
Post by TenaliRaman on Nov 27^th, 2006, 9:26pm

on 11/27/06 at 17:01:06, 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 11/27/06 at 17:12:15, Icarus wrote:

As i mentioned, extending it for higher values is what i am not able to see at the moment. :-[

-- AI

Title: Re: 2005 Points, Even Triangles
Post by ecoist on Nov 27^th, 2006, 10:26pm

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?

Title: Re: 2005 Points, Even Triangles
Post by Sameer on Nov 28^th, 2006, 9:55am

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.

Title: Re: 2005 Points, Even Triangles
Post by ecoist on Nov 28^th, 2006, 2:51pm

My proof just collapsed! So my suggestion is worth what you paid for it.

Title: Re: 2005 Points, Even Triangles
Post by azalia on Nov 28^th, 2006, 5:35pm

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.

Title: Re: 2005 Points, Even Triangles
Post by azalia on Nov 28^th, 2006, 6:40pm

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.

Title: Re: 2005 Points, Even Triangles
Post by rmsgrey on Nov 28^th, 2006, 7:52pm

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.

Title: Re: 2005 Points, Even Triangles
Post by Aryabhatta on Nov 29^th, 2006, 10:13am

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 L₁, L₂, ..., L_N. 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 L_j 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]

Title: Re: 2005 Points, Even Triangles
Post by steall on Dec 3^rd, 2006, 1:56pm

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.

Title: Re: 2005 Points, Even Triangles
Post by ecoist on Dec 3^rd, 2006, 3:33pm

Such clarity! Danke sehr, steall!