Community

Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.
Login Register Memberlist Search AoPS Blogs Contests Galleries Forum Index
The time now is Tue Dec 01, 2009 12:38 am
All times are UTC - 8
 		View posts since last visit
View unanswered posts
Home » High School Contests & Programs » Other US Contests & Programs » Mathcamp
 
Line Segments
Moderators: DanZ, ztbb
Post new topic   Reply to topic View previous topicView next topic
13 Posts • Page 1 of 1
Author Message
archimedes1
Navier-Stokes Equations
Navier-Stokes Equations


Offline
Joined: 01 Feb 2007
Posts: 1454
IndiaUnited States
To rate posts you must be logged in
#1
Line Segments
2009 Qualifying Quiz, Problem 8
On the x,y coordinate plane, there is a finite set of line segments. Each line segment lies completely in the square bounded by (0,0), (0,1), (1,0), and (1,1), and the sum of the lengths of all the line segments is 18. Prove that there exists a straight line in the plane that crosses at least ten of the segments.

PostPosted: Wed Jun 03, 2009 9:45 am  Back to top 
  ProfilePMBlogAlbum
CatalystOfNostalgia
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 19 Oct 2007
Posts: 1727
Location: Lexington, MA
MalaysiaUnited States
To rate posts you must be logged in
#2
Click to reveal hidden content
We will show that in fact, there exists such a straight line that is parallel to one of the axes (x or y). Notice that the solution easily generalizes; if the sum of the lengths of the segments is 2n, there exists a horizontal or vertical line crossing at least n+1 of them, where n is a positive integer.

Lemma. Consider a set of horizontal segments lying completely within the given unit square such that the sum of the lengths of the segments is 9. Then, there exists a vertical line that intersects at least 10 of them.
Proof. Here, we use the assumption that the segments are closed; that is, their endpoints are part of the segment. Consider all vertical lines x=k, where 0<k<1. Note that the expected value of the number of segments the line passes through is 9, since the sum of the lengths of the segments is 9 and their x-coordinates all lie in (0,1), an interval of size 1. Thus, if no vertical line intersects 10 or more of them, each of them intersect exactly 9 of them. Consider the vertical line x=\epsilon, where \epsilon>0. For a sufficiently small \epsilon, all 9 horizontal lines intersecting x=\epsilon extend to the line x=0. But they must be completely within the square, so they are open on the left side, contradiction. Therefore, this configuration is impossible, and we need some vertical line to intersect at least 10 of the horizontal segments.
---end lemma---

We now proceed to the main proof. For each segment, construct a right triangle with the segment as the hypotenuse, whose legs are parallel to the axes. To do this, pick one endpoint and draw the parallel to the x-axis, and take the other, drawing the parallel to the y- axis, giving a right triangle. If the segment is horizontal or vertical, the triangle will be degenerate. Let the lengths of the legs be a_{i} and b_{i}, where i=1,2,\ldots, where the a_{i} is the length of the horizontal side and the b_{i} is the lengths of the vertical side, and let c_{i} be the length of the hypotenuse. Note that

\displaystyle\sum\sqrt{a_{i}^{2}+b_{i}^{2}}=\displaystyle\sum c_{i}=18.

Also,

\displaystyle\sum\sqrt{a_{i}^{2}+b_{i}^{2}}\le\displaystyle\sum\sqrt{a_{i}^{2}+2a_{i}b_{i}+b_{i}^{2}}=\displaystyle\sum(a_{i}...,

since the lengths are nonnegative. Therefore, \displaystyle\sum(a_{i}+b_{i})=\displaystyle\sum a_{i}+\displaystyle\sum b_{i}>18, and one of \displaystyle\sum a_{i},\displaystyle\sum b_{i} is greater than 9. Without Loss of Generality, let \displaystyle\sum a_{i}>9. Now, by the lemma there exists a vertical line that intersects at least 10 of the horizontal edges of the right triangles. But this vertical line will intersect the hypotenuses as well, and thus the original segments. Therefore, the desired line exists, and we're done.
_________________
~Carl 白人看不懂

MELODIOUS

PostPosted: Wed Jun 03, 2009 11:25 am  Back to top 
  ProfilePMBlog
archimedes1
Navier-Stokes Equations
Navier-Stokes Equations


Offline
Joined: 01 Feb 2007
Posts: 1454
IndiaUnited States
To rate posts you must be logged in
#3
Click to reveal hidden content
Let there be n line segments in our finite set, labeled L_i for 0 < i \le n. Let each L_i have endpoints (x_i^0, y_i^0) and (x_i^1, y_i^1). Finally, for each L_i, define X_i and Y_i to be the quantities |x_i^1 - x_i^0| and |y_i^1 - y_i^0|, respectively. In other words, X_i and Y_i are the lengths of the projections of L_i onto the x axis and the y axis, respectively. Note that the length of segment L_i is \sqrt{X_i^2 + Y_i^2}, so we have \sum_{i=1}^n \sqrt{X_i^2 + Y_i^2} = 18.

Now, assume for the sake of contradiction that no line crosses more than 9 of the L_i segments. Then clearly, we must have \sum_{i=1}^n X_i < 9, because otherwise, there would exist a vertical line crossing 10 of the L_i Similarly, we must have \sum_{i=1}^n Y_i < 9.

Thus, because \sqrt{a^2 + b^2} \le a + b for all positive a and b (simply square both sides and rearrange to obtain 0 < 2ab), we have

\sum_{i=1}^n \sqrt{X_i^2 + Y_i^2} \le \sum_{i=1}^n X_i + Y_i,
so
18 \le \sum_{i=1}^n X_i + Y_i < 18,

which is a contradiction, so there must exist some line crossing more than 9 of the segments.

I just stated Catalyst's lemma without proof... Huh? Is such a complicated explanation necessary, or is that generally the way such statements are proven?

PostPosted: Wed Jun 03, 2009 12:13 pm  Back to top 
  ProfilePMBlogAlbum
perfect628
Navier-Stokes Equations
Navier-Stokes Equations


Offline
Joined: 18 Jul 2006
Posts: 2170
Location: Massachusetts
United States
To rate posts you must be logged in
#4
My proof was essentially the same as Catalyst's but I just used the Triangle Inequality to show that \sum a_i +\sum b_i \geq \sum c_i...
_________________
"Sarcasm is the protest of people who are weak."--John Knowles

"Yeah, OK"--Sam Trabucco

PostPosted: Wed Jun 03, 2009 12:22 pm  Back to top 
  ProfilePMWWWAIMBlog
mustafa
Yang-Mills Theory
Yang-Mills Theory


Offline
Joined: 07 May 2006
Posts: 992
Location: wisconsin
United States
To rate posts you must be logged in
#5
So would it be legit to say that if two lines are identical, they cross each other?

PostPosted: Wed Jun 03, 2009 1:41 pm  Back to top 
  ProfilePMBlog
benzi455
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 02 Jun 2008
Posts: 225
To rate posts you must be logged in
#6
SIGH SO EASY!

Darn, should have thought of that.

Can anyone extend that argument to prove that the same thing holds even when the segments do not have to lie strictly within the square (i.e. they can touch the square boundary)? I'm asking this because me humongous proof is much longer than and very different-looking from this one (although now I can see how in essence the arguments stem from the same principle), but my proof does extend to the non-strict case also.

EDIT:
Yes. Construct a right triangle with a horizontal and a vertical leg at each segment as above, allowing degeneracy. Let H be the sum of the lengths of the horizontal legs and V that of the vertical legs. In the non-strict version, H + V \geq 18. If equality does not hold, then either H > 9 or V > 9 (without loss of generality say the former). Then the expected value of the number of segments a vertical line through the square hits is greater than 9, so one of them hits 10.

If equality does hold, then all the segments are either vertical or horizontal, and in this case we have either H \geq 9 or V \geq 9 (without loss of generality the former). If equality does not hold, then it is the same as above.

If equality does hold, then both H = 9 and V = 9 must hold. Then the expected value of the number of horizontal segments that a vertical line through the square will hit is 9. Suppose for the sake of contradiction that no line hits ten segments. Then suppose some vertical line hit 8 or fewer segments. Then, because there are finitely many segments, there would be an entire real interval of vertical lines which hit 8 or fewer segments, which would make the expected value of the number of segments a vertical line hits macroscopically less than 9, a contradiction. Therefore no vertical line hits 8 or fewer segments, i.e., each vertical line hits exactly 9 segments.

Then just take a vertical line that passes through one of the vertical segments, and it hits ten.

So that's it. My two-and-a-half page proof with pretty diagrams was completely unnecessary.

PostPosted: Wed Jun 03, 2009 4:50 pm  Back to top 
  ProfilePM
Boy Soprano II
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 02 Nov 2005
Posts: 1467
Location: North Metro Atlanta, GA/Bloomington, IN
United States
To rate posts you must be logged in
#7
mustafa wrote:
So would it be legit to say that if two lines are identical, they cross each other?

The question speaks of lines crossing segments. I think that a line crosses its subsegments.

Quote:
SO EASY!

The problem is not easy; the solution just seems easy because it is simple.

So here is a generalization that seems natural to me : given an arbitrary bounded, connected, closed (or open) region \mathcal{R} of the plane and an integer n, how do we determine the least positive real S such that given any finite collection of segments in \mathcal{R} whose total length is S, there is some line that passes through at least n of these segments?
_________________
I am Boy Soprano.

PostPosted: Wed Jun 03, 2009 6:36 pm  Back to top 
  ProfilePMWWWBlog
benzi455
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 02 Jun 2008
Posts: 225
To rate posts you must be logged in
#8
Okay, fine.

SIGH EASIER THAN MY SOLUTION.

See attached.
problem8.pdf
Description  Long
 pdf

 Download 
Filename  problem8.pdf 
Filesize  81.27KB 
Downloaded  62 Time(s) 

PostPosted: Wed Jun 03, 2009 8:09 pm  Back to top 
  ProfilePM
bananalin
New Member
New Member

Offline
Joined: 01 May 2009
Posts: 5
To rate posts you must be logged in
#9
Wow, my random musings on the problem (which i did not write up) actually led to a solution (i was in no way close, though)
ps: very nice problem & solution

PostPosted: Wed Jun 10, 2009 9:57 pm  Back to top 
  ProfilePM
Darmani
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 04 Apr 2008
Posts: 126
To rate posts you must be logged in
#10
Though, as an alum, I'm not required to take the Quiz, I spent a good part of one random morning (car ride to school + much of my first 50-minute class) thinking about this problem, but I did not realize that the segments were not allowed to have endpoints on the box.

My main mode of thinking was to try to use pigeonhole to prove there must be some line through the box for which the lengths of the projection of the line segments onto that line added up to greater than 9 (and, of course, with endpoints on the box, it's quite easy to make the projections of the segments onto the axes both have total lengths of exactly 9, so the real solution would not work). In doing so, I ran into trying to solve some tough trigonometric inequalities. I'm quite disappointed to see how the stipulation that endpoints may not be on the box trivializes (relatively speaking) this problem.

PostPosted: Thu Jun 11, 2009 10:03 am  Back to top 
  ProfilePM
benzi455
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 02 Jun 2008
Posts: 225
To rate posts you must be logged in
#11
Darmani wrote:

I ran into trying to solve some tough trigonometric inequalities. I'm quite disappointed to see how the stipulation that endpoints may not be on the box trivializes (relatively speaking) this problem.


Was there something wrong with my extension of the expected value argument?

benzi455 wrote:

Construct a right triangle with a horizontal and a vertical leg at each segment as above, allowing degeneracy. Let H be the sum of the lengths of the horizontal legs and V that of the vertical legs. In the non-strict version, H + V \geq 18. If equality does not hold, then either H > 9 or V > 9 (without loss of generality say the former). Then the expected value of the number of segments a vertical line through the square hits is greater than 9, so one of them hits 10.

If equality does hold, then all the segments are either vertical or horizontal, and in this case we have either H \geq 9 or V \geq 9 (without loss of generality the former). If equality does not hold (i.e., if \mathbf{H > 9}), then it is the same as above.

If equality does hold, then both H = 9 and V = 9 must hold. Then the expected value of the number of horizontal segments that a vertical line through the square will hit is 9. Suppose for the sake of contradiction that no line hits ten segments. Then suppose some vertical line hit 8 or fewer segments. Then, because there are finitely many segments, there would be an entire real interval of vertical lines which hit 8 or fewer segments, which would make the expected value of the number of segments a vertical line hits macroscopically less than 9, a contradiction. Therefore no vertical line hits 8 or fewer horizontal segments, i.e., each vertical line hits exactly 9 horizontal segments.

Then just take a vertical line that passes through one of the vertical segments, and it hits ten.


(proofread and put edits in bold)

PostPosted: Thu Jun 11, 2009 12:07 pm  Back to top 
  ProfilePM
Darmani
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 04 Apr 2008
Posts: 126
To rate posts you must be logged in
#12
Thanks, that's pretty nice. Triangle inequality does remove all the trigonometric stuff.

Yes, there is a problem: I'm not sure having a segment pass through another parallel segment counts as an intersection. That's a small problem though -- just take an "almost-vertical" segment instead.

Also, the expectation value does kinda obscure the proof. I prefer to think of it as mapping the unit segment to the integer of the number of segments a vertical segment through that point would intersect, with the total integral being 9. (Well, actually that's not what I prefer to think of it as. That's just what you get if you turn the handwavy idea of "every point the horizontal projections have length density less than 9, there must be some other point whose horrizontal projections have length density greater than 9 -- and length densities must be integral" in my brain into rigorous math. And what's in quotation marks isn't really what I'm thinking -- thought are rarely easily articulable.)

PostPosted: Thu Jun 11, 2009 1:29 pm  Back to top 
  ProfilePM
benzi455
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 02 Jun 2008
Posts: 225
To rate posts you must be logged in
#13
Hmm. I would say that overlapping counts as intersecting, but of course that is a subjective matter.

Anyway, I don't "trust" expected value too much either. Your process sounds kind of like what I did: There are finitely many segments, so projecting them onto the x-axis defines a partition of the interval [0, 1]. Clearly no subinterval can contain parts of ten or more different segments, so they all have to contain parts of exactly nine segments. The PDF I attached a while ago has a diagram for this, but it also contains a very long process that was not necessary at all, since the only necessary cases in that proof were \phi = 0 and \phi = \pi/2.

PostPosted: Thu Jun 11, 2009 7:03 pm  Back to top 
  ProfilePM
Display posts from previous:   Sort by:   
13 Posts • Page 1 of 1
Post new topic   Reply to topic View previous topicView next topic
Home » High School Contests & Programs » Other US Contests & Programs » Mathcamp
 
Jump to:  


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 vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum


© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us