[contest] 10 bit math questions

[Martin]

No, these aren't from my homework.

1. In something of a whimsical mood, the great probabilistic geometer, Drew Diecaster, selected two distinct random points on a straight line segment L. What are the chances that he can construct a triangle from the three resulting lengths?

[mynameisbob]

100% chance....

[wtd]

I thought about answering, but I'm glad someone else was able to.

[Cervantes]

You know that's not the answer for two reasons:

1) It's too easy
2) One example proves it wrong. Assuming the line goes from 0 to 1, what if Drew picked his points at 0.1 and 0.9? You can't make a triangle with that, because the three lines you'd have to work with are of lengths 0.1, 0.1, and 0.8. To successfully make a triangle, the lengths of the two smaller lines must be greater than or equal to the length of the longest line. (right?)

Very interesting problem Martin, I'm going to be thinking about this for a long time. Longer than the 24 game with 5,5,5,1 8)
Did you think up that problem yourself?

[wtd]

D'oh. This is what I get for being so sick.

[Mazer]

EDIT: this post never happened. HA!

[Cervantes]

Yes, you are wrong. again, if it's a 0% chance, only one example will prove it wrong.
Say Drew selects 0.4 and 0.8.
Length one is 0.4, Length two is 0.4, and Length 3 is 0.2.
The two smaller lengths (in this case, its the smallest length and one of the larger lengths, since they are the same) total 0.6, the larger length totals 0.4. Hence, you can make a triangle.

EDIT: That mistake never happened. HA! 8)

wtd: I hope you get better soon.
I didn't think about it for long before I realized that I could write a program to give me an average. I came up with an average of 24.964%.

Oh, and now that I think about it, I think the sum of the two shorter lines would have to be greater than that of the longer line, because if they were exactly equal you'd end of up with a straight line that consists of three line segments piled ontop of one another.

[Mazer]

Cervantes wrote:

Say Drew selects 0.4 and 0.8.
Length one is 0.4, Length two is 0.4, and Length 3 is 0.3.
The two smaller lengths (in this case, its the smallest length and one of the larger lengths, since they are the same) total 0.7, the larger length totals 0.4. Hence, you can make a triangle.

I see that you are right, not sure why I was thinking that... but in your example, I assume you chose the points like that so that it would represent a percentage of the actual length of the line (as we don't know the real length), but somehow your third length grew. It should be 0.2.

[wtd]

Cervantes wrote:

wtd: I hope you get better soon.

Thanks. So do I.

[Martin]

No, I didn't make up the problem myself. I can't tell you where I got it though, for obvious reasons

By the way, all of your answers are wrong.

Here is my hint: http://mathworld.wolfram.com/TriangleInequality.html

[Cervantes]

Martin wrote:

By the way, all of your answers are wrong.

even the answer I cheated to get? It's small and in white text, in my second post.
I think this is more than a 10-bit problem

[Genesis]

25% chance...?

EDIT: And I see that Cervantes already got that number...pretty much. Didn't notice his small print when I posted this.

[Cervantes]

err, I put it small and white for a reason: so that people who didn't want to see the answer I had come up with wouldn't see it just by reading through the thread. So that only people who were driven to insanity would look there for a clue. Oh well, I'm posting the answer (well, I think its the answer)

I'm reasonably certain:

again, using 0.0 to 1.0 line segment.

p1 = the first point placed
p2 = the second point placed

code:

if p1 < 0.5 then     if p2 > 0.5 and p2 < p1 + 0.5 then         put "A triangle is made.  HuZaA!"     end if end if similarly, if p1 > 0.5 then     if p2 < 0.5 and p2 > p1 - 0.5 then         put "A triangle is made.  HuZaA!"     end if end if

Let's look at the first part, if p1 < 0.5.

-there is a 50% chance that p1 is less than 0.5 *see note
-there is a 50% chance that p2 is greater than 0.5
-there is a 50% chance that p2 is less than p1 + 0.5 (the range that p2 could be in for this to be true is between p1 and p1 + 0.5. since p1 is less than 0.5, p1 + 0.5 is less than 1.0, so the full 0.5 is used, if you understand what I mean. it's not as if p1 is 7.5 and p1 + 0.5 is 12.5, but since p2 can only be up to 1.0, there is a full 2.5 that isn't used, so in that case the chance of p2 falling in the range of p1 and p1 + 0.5 would be 25%. but since p1 is less than 0.5, the chance of p2 being between p1 and p1 + 0.5 is always 50%

50% * 50% * 50% is 12.5%.
Then we consider the other side of the coin, if p1 were to be greater than 0.5. That gives us another 12.5% to make a triangle.
12.5% + 12.5% = 25%.

As for how I came up with the if p1 > 0.5 and p2 < 0.5 and p2 > p1 - 0.5 etc., I just played around with different values, and began to see a threshold.
I don't think I can explain it. I tried, several times, but always failed. just play around with the following numbers, making one of them 0.01 bigger or smaller, and then making the other 0.01 bigger or smaller.

code:

_____|____1_______2______3___ -----|----------------------- p1 = |  0.25    0.25    0.75      | p2 = |  0.50    0.50    0.50

*note: Coutsos said this before he deleted his post: we will use infinate precision, infinate decimal points, in this problem. So there is a 50-50 chance of p1 being less than 0.5, as well as a 50-50 chance of p1 being less than or equal to 0.5

[Genesis]

Yeah that's kinda how I figured it out. Except I used pencil and paper. (And my trusty calculator.) I didn't even think to write a program, good idea!

I'm pretty sure it's right though.

[Martin]

Good work guys. I'm on links right now (KDE takes a while to compile...) so I'll give you bits once I get this OS up and running. Yes, 0.25 is the right answer.