Community

Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.
Login Register Memberlist Search AoPS Blogs Contests Galleries Forum Index
The time now is Sat Nov 28, 2009 1:14 pm
All times are UTC - 8
 		View posts since last visit
View unanswered posts
Home » High School Contests & Programs » Other US Contests & Programs » Mathcamp
 
Random Triangle
Moderators: DanZ, ztbb
Post new topic   Reply to topic View previous topicView next topic
21 Posts • Page 1 of 2 • 1, 2 Next
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
Random Triangle
2009 Qualifying Quiz, Problem 5
Three real numbers are chosen at random between 0 and 1. What is the probability that they form the side lengths of a triangle? Prove your answer.

PostPosted: Wed Jun 03, 2009 9:41 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
The answer is \dfrac{1}{2}.

Let the three numbers be x,y,z. Note that any ordered triple (x,y,z) corresponds to a point in 3-D space within the unit cube bounded by the 8 binary strings of 0's and 1's: (0,0,0),(0,0,1), etc. Note that this has volume 1. We want the volume of the set of points such that x+y>z, y+z>x, and z+x>y. Equivalently, we can take the volume of the set of points such that either x+y<z, y+z<x, or z+x<y, and subtract it from the volume of the whole cube. Note that we can disregard cases such as x+y=z because these represent planes, not contributing anything to the volumes.

Note that it is impossible for any point (x,y,z) to belong to more than one of the regions x+y<z,y+z<x,z+x<y, since if, for example, x+y<z, since x,y,z>0, we have z>y,x. This implies that y+z>x and z+x>y, so (x,y,z) can only be in one of these three regions. Thus we can find the volumes of each of the regions separately. By symmetry, we only need to consider x+y<z. x+y=z represents a plane, so we want the volume of the set of points on one side of the plane, within the unit cube. Note that (0,0,0), (0,1,1), and (1,0,1) all satisfy x+y=z, so these points are on the plane. Now, (0,0,1) satisfies x+y<z, so we want the volume of the part of the cube on the same side of the plane as (0,0,1). We see that this is simply the pyramid with apex (1,0,1) and base vertices (0,0,1),(0,0,0),(0,1,1). The height is clearly 1 (the distance between (1,0,1) and (0,0,1), since this length is perpendicular to the base), and the base has area 1/2, so the volume is \dfrac{1}{3}\cdot\dfrac{1}{2}\cdot1=1/6.

Therefore, the total volume of the region we don't want to count is 3\cdot\dfrac{1}{6}=\dfrac{1}{2}, and thus the region we want is 1-\dfrac{1}{2}=\dfrac{1}{2}. The volume of the cube is 1, giving a probability of \dfrac{1}{2}, as desired.
_________________
~Carl 白人看不懂

MELODIOUS

PostPosted: Wed Jun 03, 2009 11:19 am  Back to top 
  ProfilePMBlog
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
#3
I decided to be lame and use calculus on this one in my solutions, but here's another solution:

Another Solution
Consider the set \{\frac1n, \frac2n, \cdots 1 \}. Let P_n represent the probability that a randomly chosen subset \{a, b, c\} of three not necessarily distinct elements of the set form a triangle.

We here find 1-P_n, i.e. the probability that they don't form the sides of a triangle. For simplicity let r=na, s=nb, t=nc. Note that the condition that r, s, t don't form a triangle is equivalent to exactly one of r+s \leq t, s+t \leq r, and t+r \leq s being true. WLOG let r+s \leq t. Then, by a standard argument, there exists some positive integer m such that r+s+m=t+1. For each value of t, by Balls and Urns, there are \binom{t}{2} ways to select r, s, m. Since t \leq n, there are then \sum^n_{t=1} \binom{t}{2} total ways to choose r, s, t, which by Hockey stick is equal to \binom{n+1}{3}. Thus, because of our assumption that r+s \leq t, there are 3\binom{n+1}{3} ways to choose r, s, t so that they don't form a triangle. Thus, since there are n^3 ways to choose r, s, t, P_n=\frac{n^3-3\binom{n+1}{3}}{n^3}=\frac{n^2+1}{2n^2}.

Now, as n gets large, the discrete case we've been looking at approaches the continuous case the problem asks for. Therefore, \lim_{n \to \infty} P_n=\frac12, which is our answer.
_________________
"Sarcasm is the protest of people who are weak."--John Knowles

"Yeah, OK"--Sam Trabucco

PostPosted: Wed Jun 03, 2009 1:20 pm  Back to top 
  ProfilePMWWWAIMBlog
benzi455
Poincare Conjecture
Poincare Conjecture

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

Now, as n gets large, the discrete case we've been looking at approaches the continuous case the problem asks for. Therefore, \lim_{n \to \infty} P_n = \frac12, which is our answer.


Well, even as n gets large, P_n is only a set of rational numbers. I don't see a quick way to adapt the argument to the real line without starting over. (Then again, there probably is one, so please prove me wrong.)

By the way, I'm with you on the calculus thing. I mentioned geometry, but I do not consider "geometric probability" to be a legitimate proof. Besides, with the calculus it took absolutely no work. I didn't even do the calculation by hand; I just used Maxima.

PostPosted: Wed Jun 03, 2009 4:45 pm  Back to top 
  ProfilePM
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
#5
Blech there I am not paying attention--I had actually seen this problem before, and that's where I got the argument above. Well, I thought I had--Now that I look back it specified rationals there. Luckily I used the boring integration on the quiz!
_________________
"Sarcasm is the protest of people who are weak."--John Knowles

"Yeah, OK"--Sam Trabucco

PostPosted: Wed Jun 03, 2009 6:19 pm  Back to top 
  ProfilePMWWWAIMBlog
Temperal
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 19 Mar 2007
Posts: 2096
Location: Omaha, NE
ChinaUnited States
To rate posts you must be logged in
#6
I don't understand why the limit wouldn't work - the rationals are uniformly distributed among the reals, are they not?
_________________
"we should make an asian mob and attack DC" -- Alan
...在美国

PostPosted: Wed Jun 03, 2009 7:06 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
#7
Intuitively the limit thing makes sense to me, but I don't have enough mathematical knowledge (or the right angle on the question) to make it rigorous. Could you please explain what you mean in a precise mathematical sense by "the rationals are uniformly distributed among the reals"? The rationals are dense in the reals, but the entire rational line is of measure zero, so what does a "distribution" of the rationals among the reals entail?

And then if you want to be really nice you can pamper me and give a full justification of the "limit" argument bridging the rational argument with the real one.

PostPosted: Wed Jun 03, 2009 7:54 pm  Back to top 
  ProfilePM
Temperal
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 19 Mar 2007
Posts: 2096
Location: Omaha, NE
ChinaUnited States
To rate posts you must be logged in
#8
Well, the probability function perfect describes is bounded on the interval we're considering, so the integral and the limit are interchangeable.

As for uniform distribution, essentially it means that on any closed subinterval, the expected value of of a randomly chosen rational and a randomly chosen real are the same.
_________________
"we should make an asian mob and attack DC" -- Alan
...在美国

PostPosted: Thu Jun 04, 2009 6:58 am  Back to top 
  ProfilePMBlog
Darmani
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 04 Apr 2008
Posts: 126
To rate posts you must be logged in
#9
Very simple solution

Without loss of generality, assume c is the largest of a,b,c. Divide each length by c. We now must find the probability that a + b > 1, which is obviously \frac {1}{2}. (Just draw a unit square -- we want the probability the probability (a,b) is above the diagonal.)

You would want to do a little more work to show that all values in the range (0,1) are still equiprobable, which is not hard -- just treat it as if you picked c first.


Thank you to Josh Alman, who, by sheer coincidence, shared the similar problem with a near-identical solution method "Randomly pick a,b,c from (0,1); find the probability they form an acute triangle" just a few days before the qualifying quiz was posted.

PostPosted: Thu Jun 04, 2009 8:49 am  Back to top 
  ProfilePM
Zeph
Hodge Conjecture
Hodge Conjecture

Offline
Joined: 29 Jul 2008
Posts: 77
To rate posts you must be logged in
#10
Unfortunately, I haven't had calculus yet (self-studying with Spivak right now, so it should take a while, too >_> I guess I'll study it concurrently with my ACTUAL calculus class, heh), so I did it Catalyst's way. I wasn't quite sure it was rigorous either, and I'd actually quite like to know whether geometric probability is or is not a valid proof method.

PostPosted: Sat Jun 06, 2009 12:37 pm  Back to top 
  ProfilePMAIM
JAM
Riemann Hypothesis
Riemann Hypothesis

Offline
Joined: 14 Jun 2004
Posts: 495
United States
To rate posts you must be logged in
#11
I see no reason why a geometric solution wouldn't be rigorous. Really it's the same thing as the calculus solution, except we're finding the volume of the region by basic geometry instead of integration.
_________________
Wishing it was the first week again
Wishing we could turn back time...

PostPosted: Sat Jun 06, 2009 12:53 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
#12
Definitely. I mean, I suppose both the P_n thing and the geometry could both be justifiable, but at the root of it, the only way I see to justify them is to set up the calculus and then, once that is established, show that your alternate solution is equivalent to the calculus.

And Zeph, I've been trying to get my hands on Spivak's book for the longest time. What I used this year (in addition to an AP calculus class -- a great deal of good that has done) was a short old real analysis text that I borrowed from my teacher. Everyone raves about Spivak, but I haven't been able to find it in a library.

PostPosted: Sat Jun 06, 2009 4:31 pm  Back to top 
  ProfilePM
JAM
Riemann Hypothesis
Riemann Hypothesis

Offline
Joined: 14 Jun 2004
Posts: 495
United States
To rate posts you must be logged in
#13
A lot of this comes down to how you define probability, which can be a bit of a deep subject. In this situation it would be reasonable to define the probability of picking a point in some set E, out of a set of possible points \Omega to be:
P(E) = \frac{m(E)}{m(\Omega)}
(where m(X) represents the measure (volume) of a set X).

In this case either integration or geometry would be valid ways to find m(E).
_________________
Wishing it was the first week again
Wishing we could turn back time...

PostPosted: Sat Jun 06, 2009 4:47 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
#14
Now you're getting beyond me. But that does seem reasonable. Defining probability in terms of geometry never really sat well with me, but it would work because of the link between synthetic geometry and Euclidean space which I find to be very nontrivial. Anyway, even in the geometry, I ended up with a couple of tetrahedra, and I don't know how to find the volume of one of those without calculus. At every step of the way it is clear that the analytic and the analytic-geometric methods are the same. What discomforts me personally about it is that I'm basically saying,

Quote:

If we wish to find the probability that three real numbers a_1,a_2,a_3 chosen independently and randomly from (0,1) with uniform distribution satisfy the so-called "triangle" inequalities a_i + a_j > a_k, then it is sufficient to consider three mutually perpendicular lines in Euclidean three-space, and then label each point in the space with coordinates, and consider the locus of points whose coordinates satisfy the inequalities. We can prove that this is a region bounded by this plane, this plane and that plane, which takes the form of an octahedron. In this space, we define "volume" to mean such-and-such, and we define probability to be the ratio of volumes. Oh, by the way, all this is independent of the choice of mutually perpendicular lines. Incidentally, this definition can be shown to coincide with other definitions based on axioms that did not originate in 300 B.C.


To someone who is more experienced than me in this, that's probably trivial. But personally I try to avoid using geometry to prove things that in my mind "are not geometry" because I feel that I'm BS-ing it, for the sole reason that if someone sat me down in a room and asked me to justify everything I had said down to symbols, I would not be able to do so. Yes, I am a strange person.

PostPosted: Sat Jun 06, 2009 5:15 pm  Back to top 
  ProfilePM
noobius
New Member
New Member

Offline
Joined: 13 May 2009
Posts: 4
To rate posts you must be logged in
#15
I actually usually feel the opposite way. For things like this I try to see spacial arrangements because when I'm messing with symbols it seems like they do the thinking for me and I end up not actually understanding what I'm doing.

Anyways, in this case I also initially did this with calc. But when I saw the answer I looked for a better solution and imagined a three dimensional graph, had one dimension be the long side, and realized that the other two had to form a 45 45 90 triangle cross section with linearly increasing sides to contain all the volume that would not form a triangle with the three lengths. Since one third of a cube would just be the same thing with a square instead of the triangle, 1/2 of possibilities form triangles.

PostPosted: Fri Jun 12, 2009 7:14 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
#16
Yeah, I'm really not describing this in the right way. Let me try again. I consider a proof to be a proof, and any other consideration of mathematics might be BS or someone might claim that you have failed to justify it. (even if you're obviously right, there are some people like that no I am not saying the mathcamp people are like that) Maybe it would help to clarify if I mentioned that I really, really wanted to get into this program and I had serious doubts that I would make it, so I was VERY careful to make sure nothing went unsaid in my solutions. They were eleven pages long Lol. Plus diagrams.

PostPosted: Tue Jun 16, 2009 12:45 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
#17
You're not alone in that. My solutions were 24 pages last year (although I always started a new problem on a new page). Still, I did things such as proving that, if you convert the sequence of powers and sums of powers of three into ternary, order will be preserved, and overall just tried to let nothing go unstated.

I know some others did similarly, such as one girl who mentioned that she wrote her proofs as if "talking to a three year-old."

PostPosted: Wed Jun 17, 2009 1:01 pm  Back to top 
  ProfilePM
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
#18
My proofs weren't too verbose, in my opinion, and didn't do anything unnecessary, and ended up being 14 pages long. To be fair, two of the pages only had two lines, but still...
_________________
"Sarcasm is the protest of people who are weak."--John Knowles

"Yeah, OK"--Sam Trabucco

PostPosted: Wed Jun 17, 2009 4:11 pm  Back to top 
  ProfilePMWWWAIMBlog
benzi455
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 02 Jun 2008
Posts: 225
To rate posts you must be logged in
#19
@Darmani LOL. It's because the people at Mathcamp are so stupid and have so little experience in math. We need to make sure they can digest our complex ideas. And it worked, didn't it? We got in.

@perfect628 Why did you sometimes have two lines to a page? Did you start each solution on a new page?

PostPosted: Wed Jun 17, 2009 7:44 pm  Back to top 
  ProfilePM
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
#20
Yes I started each solution on a new page...Did others not?
_________________
"Sarcasm is the protest of people who are weak."--John Knowles

"Yeah, OK"--Sam Trabucco

PostPosted: Thu Jun 18, 2009 2:23 pm  Back to top 
  ProfilePMWWWAIMBlog
Display posts from previous:   Sort by:   
21 Posts • Page 1 of 2 • 1, 2 Next
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