Re: puzzle question
- From: quasi <quasi@xxxxxxxx>
- Date: Mon, 02 Jan 2006 06:44:06 -0500
On Mon, 02 Jan 2006 05:28:30 EST, "M.A.Fajjal" <h2maf@xxxxxxxxx>
wrote:
>> On Mon, 02 Jan 2006 03:36:35 EST, "M.A.Fajjal"
>> <h2maf@xxxxxxxxx>
>> wrote:
>>
>> >> On Sun, 01 Jan 2006 22:06:34 EST, "M.A.Fajjal"
>> >> <h2maf@xxxxxxxxx>
>> >> wrote:
>> >>
>> >> >> On Sun, 01 Jan 2006 13:31:29 EST, "M.A.Fajjal"
>> >> >> <h2maf@xxxxxxxxx>
>> >> >> wrote:
>> >> >>
>> >> >> >> On Sun, 01 Jan 2006 02:02:08 -0500, quasi
>> >> >> >> <quasi@xxxxxxxx> wrote:
>> >> >> >>
>> >> >> >> >On 31 Dec 2005 22:46:54 -0800, "mathbee"
>> >> >> >> <buntygill@xxxxxxxxx> wrote:
>> >> >> >> >
>> >> >> >> >>Given a stick of length L, what is the
>> chance
>> >> >> that
>> >> >> >> you can break it
>> >> >> >> >>into 3 pieces that can form a triangle?
>> >> >> >> >>
>> >> >> >> >>My answer is 1/8 (many other people got
>> the
>> >> same
>> >> >> >> answer) but the
>> >> >> >> >>interviewer said it is 1/3.
>> >> >> >> >>
>> >> >> >> >>Any ideas?
>> >> >> >> >
>> >> >> >> >It depends on the assumptions for the how
>> the
>> >> >> >> breaking is done.
>> >> >> >> >
>> >> >> >> >Assuming the 2 breakpoints are chosen
>> >> >> independently
>> >> >> >> and with a uniform
>> >> >> >> >distribution, I don't get 1/8 or 1/3 -- I
>> get
>> >> a
>> >> >> >> probability of 1/4.
>> >> >> >> >
>> >> >> >> >quasi
>> >> >> >>
>> >> >> >> Ok, quick challenge problem ...
>> >> >> >>
>> >> >> >> With the same assumptions, what is the
>> >> probability
>> >> >> >> that you can form
>> >> >> >> an acute triangle?
>> >> >> >>
>> >> >> >let the angls of triangle are a, b, c
>> >> >> >
>> >> >> >a+b+c=180
>> >> >> >
>> >> >> >assume the angles are integers
>> >> >> >
>> >> >> >Acute triangle cases = 44/179
>> >> >> >
>> >> >> >Probability of acute triangle for the same
>> case
>> >> >> assumptions = 1/4 * 44/179 = 11/179
>> >> >>
>> >> >> As pointed out in another reply, there no
>> simple
>> >> way
>> >> >> to convert the
>> >> >> problem from a problem of choosing 2 random
>> break
>> >> >> points to a problem
>> >> >> of choosing angles.
>> >> >>
>> >> >> But even if we change the problem to a problem
>> of
>> >> >> choosing angles, I
>> >> >> don't see how you got 44/179. What do you mean
>> by
>> >> >> "Acute triangle
>> >> >> cases"?
>> >> >>
>> >> >> And why are you multiplying by 44/179 by 1/4?
>> >> What's
>> >> >> the logic?
>> >> >>
>> >> >The probability to form any triangle is 1/4
>> >> >
>> >> >let the angls of the formed triangle are a, b, c
>> >> >
>> >> >a+b+c=180
>> >> >
>> >> >assume the angles are integers
>> >> >
>> >> >possible angles = 179*178/2 = 15931
>> >> >
>> >> >Acute triangle where 1=<a<90 and 1=<b<90 and
>> 1=<c<90
>> >> >
>> >> >Acute triangle cases = 3916 (Counting by simple
>> >> program)
>> >> >
>> >> >Probability of acute triangle for the same case =
>> >> 1/4 * 3916/15931 = 11/179
>> >> >
>> >> >The code for the program in VB6 shall be as
>> follows
>> >> >
>> >> >
>> >> >Private Sub Command1_Click()
>> >> >Open "D:\puzzle.txt" For Output As #1
>> >> >Print #1, Time
>> >> >k = 0
>> >> >u = 0
>> >> >For a = 1 To 180
>> >> > For b = 1 To 180
>> >> > For c = 1 To 180
>> >> > DoEvents
>> >> > If a + b + c = 180 Then
>> >> > k = k + 1
>> >> > If a < 90 and b < 90 and c < 90 Then
>> >> > u = u + 1
>> >> > End If
>> >> > End If
>> >> > Next
>> >> > Next
>> >> > Next
>> >> > Print #1, u & " " & k
>> >> > Print #1, Time
>> >> > End
>> >> >
>> >> >End Sub
>> >> >
>> >> >The results
>> >> >19:02:50
>> >> >3916 15931
>> >> >19:02:58
>> >>
>> >> Ok, thanks for explaining it -- at least now I
>> >> understand your logic.
>> >>
>> >> The answer is wrong for at least 5 reasons:
>> >>
>> >> (1) You are assuming integer angles. Hence, even
>> if
>> >> the rest was
>> >> correct, the result would only be approximate.
>> >>
>> >> (2) You are assuming the first angle is uniformly
>> >> distributed.
>> >> However, the set of possible triangles obtainable
>> >> from 2 random break
>> >> points does not imply a uniform distribution on
>> the
>> >> angles.
>> >>
>> >> (3) You are assuming the 2nd angle must be
>> different
>> >> than the first
>> >> (as shown by your choice of the 2nd factor as
>> 178).
>> >> There's no reason
>> >> to assume that the 2nd angle must be different.
>> >>
>> >> (4) You are assuming that, except for being not
>> >> equal, the value of
>> >> the 2nd angle is independent of the value of the
>> >> first. This is
>> >> clearly false. An easy way to see this is to note
>> >> that the first angle
>> >> has taken up some amount of the 180 total, so the
>> >> bigger the first
>> >> angle, the less choices for the 2nd.
>> >>
>> >> Of all the errors so far, this is the worst one,
>> but
>> >> there's an even
>> >> worse error here -- namely, your calculation
>> >> 179*178/2 includes pairs
>> >> of angles whose sum is already greater than 180 --
>> >> your pair sums
>> >> range from 3 degrees to 357 degrees.
>> >>
>> >> (5) Your counting loop counts the same triple
>> again
>> >> in a permuted
>> >> order, but your calculation 179*178/2 is
>> inconsistent
>> >> with this
>> >> assumption since you are dividing by 2.
>> >>
>> >> But even here, there is a worse error. To see the
>> >> error dramatically,
>> >> take out the test for acute and count again.
>> You'll
>> >> get a count of
>> >> 180^3, but by your logic, the total should equal
>> >> 179*178/2. However,
>> >> 180^3 and 179*178/2 are not even close.
>> >>
>> >> The errors here, especially (2), (4), (5), totally
>> >> invalidate any
>> >> result you might obtain.
>> >>
>> >
>> >The triangle has been already formed with the
>> probability of 1/4.
>> >Now, starting new problem, what the probability of
>> cute triangle. All angle values are possible.
>>
>> Once a triangle has been formed, all angles are not
>> possible.
>>
>> Obviously, you don't understand the experiment.
>>
>> The break points are being chosen at random, not the
>> angles.
>>
>> >If fraction of angles is allowed for a, b, c
>> (uniform distributed),
>>
>> As pointed out above, it's the break points that are
>> uniformly
>> distributed.
>>
>> The fact that the break points are uniformly
>> distributed doesn't
>> automatically imply that the angles are uniformly
>> distributed.
>>
>> In fact, the angles are _not_ uniformly distributed.
>
>Why?
Because it's not the angles that are being chosen -- it's the break
points. The angles (and also the sides) are forced once the break
points are chosen.
The break points are assumed independent and uniformly distributed in
the interval [0,1].
But the angles are not uniformly distributed (in [0,180]) and also not
independent of each other.
Similarly, the sides are also not uniformly distributed and also not
independent of each other.
If you want to try a discrete experiment to approximate the correct
answer, revise your program as follows:
(1) Assume the length of the stick is 100 units.
(2) Keep 2 counters:
* A count of the total number of trials
* A count of the number trials which resulted in acute triangles
Initialize both counters to 0.
(2) For all pairs x,y of integers with 0 < x < y < 100, use x,y as
break points. For each pair (x,y) increment the count of the number of
trials.
(3) Let a=x, b=y-x, c=100-y
(4) Reject (a,b,c) unless the triangle inequalities hold:
a+b>c, b+c>a, c+a>b
(5) Use the law of cosines to determine if the triangle with sides
a,b,c is acute. Reject (a,b,c) if the triangle is not acute. If the
triangle is acute, increment the count of the number of acute
triangles.
(6) Once all pairs (x,y) have been tested, output the value of the
ratio (acute count)/(number of trials).
If you implement a program using the above design, the result you get
will be approximately correct since it's based on choosing break
points, not angles (the angles and side are both forced).
Note, the result you get by the above method will only be an
approximation since, in the actual problem, the assumption is that the
break points can vary continuously.
To get the exact answer, a standard approach is:
(1) View the break points x,y as corresponding to a point (x,y) of the
unit square S. Thus, the unit square can be viewed as the sample
space. Since we are assuming that x,y are independent and uniformly
distributed in [0,1], it follows that the point (x,y) is uniformly
distributed in S.
(2) Let D be the region of S such that, if x,y were used as break
points for a stick of length 1, the resulting 3 segments could be used
to form an acute triangle. Since the area of S is 1, the probability
that a random point of S is in D is area(D)/area(S), and since
area(S)=1, the probability is just area(D).
(3) By symmetry, it suffices to consider the subregion D1 of D for
which x<y. After finding the area of D1, we can then simply multiply
by 2 to get the area of D.
(4) Find the equations of the boundary curves for D1 and draw the
region D1.
(5) Calculate the area of D1. For many such problems of this type, the
area of the desired region can be calculated by simple geometry,
however for this problem, calculus will be required. Once you see the
region D1, it will be clear why.
If you follow the plan outlined above, you'll get the exact answer:
3*ln(2) - 2
which is approximately:
0.079441542
quasi
.
- Follow-Ups:
- Re: puzzle question
- From: M.A.Fajjal
- Re: puzzle question
- References:
- Re: puzzle question
- From: quasi
- Re: puzzle question
- From: M.A.Fajjal
- Re: puzzle question
- Prev by Date: Proof / counterexample requested
- Next by Date: Re: puzzle question
- Previous by thread: Re: puzzle question
- Next by thread: Re: puzzle question
- Index(es):
Relevant Pages
|
Loading
