Computer Science Canada

[contest] 10 bit math questions
Author:  Martin [ Sat Oct 09, 2004 12:45 pm ]
Post subject:  [contest] 10 bit math questions
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?
Author:  mynameisbob [ Sat Oct 09, 2004 5:51 pm ]
Post subject: 
100% chance....
Author:  wtd [ Sat Oct 09, 2004 5:54 pm ]
Post subject: 
I thought about answering, but I'm glad someone else was able to. Smile
Author:  Cervantes [ Sat Oct 09, 2004 5:56 pm ]
Post subject: 
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?
Author:  wtd [ Sat Oct 09, 2004 6:04 pm ]
Post subject: 
D'oh. This is what I get for being so sick.
Author:  Mazer [ Sat Oct 09, 2004 6:17 pm ]
Post subject: 
EDIT: this post never happened. HA!
Author:  Cervantes [ Sat Oct 09, 2004 6:26 pm ]
Post subject: 
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.
Author:  Mazer [ Sat Oct 09, 2004 6:47 pm ]
Post subject: 
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.
Author:  wtd [ Sat Oct 09, 2004 6:52 pm ]
Post subject: 
Cervantes wrote:
wtd: I hope you get better soon.


Thanks. So do I. Smile
Author:  Martin [ Sat Oct 09, 2004 7:29 pm ]
Post subject: 
No, I didn't make up the problem myself. I can't tell you where I got it though, for obvious reasons Wink

By the way, all of your answers are wrong.

Here is my hint: http://mathworld.wolfram.com/TriangleInequality.html
Author:  Cervantes [ Sat Oct 09, 2004 9:15 pm ]
Post subject: 
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 Confused
Author:  Genesis [ Sat Oct 09, 2004 9:43 pm ]
Post subject: 
25% chance...?

EDIT: And I see that Cervantes already got that number...pretty much. Didn't notice his small print when I posted this.
Author:  Cervantes [ Sat Oct 09, 2004 10:07 pm ]
Post subject: 
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. Confused 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
Author:  Genesis [ Sat Oct 09, 2004 10:50 pm ]
Post subject: 
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.
Author:  Martin [ Sun Oct 10, 2004 12:44 am ]
Post subject: 
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.
Author:  Cervantes [ Sun Oct 10, 2004 7:16 am ]
Post subject: 
Genesis wrote:
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.

I used pencil and paper too (but no calculator Razz). Writing a program is cheating, and I wanted to figure out why.
Author:  bugzpodder [ Sun Oct 10, 2004 9:55 am ]
Post subject: 
aww, i wanted the 10 bits Sad but i am too late


Cervantes wrote:
if it's a 0% chance, only one example will prove it wrong.


That is mostly right. But not quite. I think the probability of you selecting a integer in the reals is 0%. (yes, exactly 0)

i think it is same for rationals as well, but i am not 100% sure
Author:  Martin [ Mon Oct 11, 2004 1:29 pm ]
Post subject: 
2. Root 2 is Irrational

Prove it. This one's for 20 bits.
Author:  Andy [ Mon Oct 11, 2004 2:50 pm ]
Post subject: 
if we were to square root 2, we'd get the good old integer 2... if we were to rewrite 2 as a rational number, we'd have 2x/x... since both 2x and x cannot both have an even number of factors, we know that at least one of them is not a perfect square. thus the square root of 2x/x cannot be rational which means root 2 is irrational
Author:  Martin [ Sun Oct 17, 2004 3:59 pm ]
Post subject: 
Awesome.

3. Limits
This one might seem easy, but I want a proof, not just inspection. 40 bits.

code:
Prove:
Lim (x^2 - 1) = 3
x -> -2
Author:  Andy [ Mon Oct 18, 2004 3:26 pm ]
Post subject: 
LS:
if we were to factor x^2-1, we could rewrite the limit as

Lim ((x-1)(x+1))
x->-2

as x gets closer and closer to -2, x-1 gets closer and closer to -3, and x+1 gets closer and closer to -1, and -1*-3=3

RS:
3

LS=RS

Lim (x^2 - 1) = 3
x -> -2
Author:  apomb [ Mon Oct 18, 2004 4:51 pm ]
Post subject: 
I have a complaint about dodge ... or other mods replying to this thread, since its for bits, why should they be able to answer, mabe they can , if they know it, put hints or something, i just find it unfair... because bits are involved
Author:  Andy [ Mon Oct 18, 2004 4:56 pm ]
Post subject: 
more than one person can answer you know.. as long as the solutions are different
Author:  apomb [ Mon Oct 18, 2004 4:58 pm ]
Post subject: 
ya, but will Martin give bits to both people?
Author:  Andy [ Mon Oct 18, 2004 4:59 pm ]
Post subject: 
if ur solution's nice, i'll give u bits
Author:  bugzpodder [ Mon Oct 18, 2004 4:59 pm ]
Post subject: 
dodge_tomahawk wrote:
LS:
if we were to factor x^2-1, we could rewrite the limit as

Lim ((x-1)(x+1))
x->-2

as x gets closer and closer to -2, x-1 gets closer and closer to -3, and x+1 gets closer and closer to -1, and -1*-3=3

RS:
3

LS=RS

Lim (x^2 - 1) = 3
x -> -2

actually you need a delta, epsilon proof.
Author:  Andy [ Mon Oct 18, 2004 5:00 pm ]
Post subject: 
sry bugz, not that far yet in calc wit Ing
Author:  apomb [ Mon Oct 18, 2004 5:08 pm ]
Post subject: 
Dodge: thanks for adressing my issue with such promptness
bugspodder :you are a fast poster!
-Compwiz
Author:  Brightguy [ Mon Oct 18, 2004 7:56 pm ]
Post subject:  Re: [contest] 10 bit math questions
code:
Prove:
Lim (x^2 - 1) = 3
x -> -2

Did you happen to get that question from your calculus assignment by any chance? Laughing That question was on mine at least.
Author:  Andy [ Tue Oct 19, 2004 3:13 pm ]
Post subject: 
martin's in uni...
Author:  Brightguy [ Tue Oct 19, 2004 5:12 pm ]
Post subject:  Re: [contest] 10 bit math questions
Yes, in fact we are a part of the same faculty. Not sure if the assignments are the same, though, as he might be getting "advanced" problems... and working on special Putnam-level stuff on the side, of course. Surprised
Author:  Andy [ Tue Oct 19, 2004 5:23 pm ]
Post subject: 
just as an aside, hey martin, rumors say that ur smoking even john at math marks.. is this true?
Author:  Martin [ Tue Oct 19, 2004 5:52 pm ]
Post subject: 
I have no idea, but I really doubt it. My math mark is about 10% lower than john's I'd guess (at ~115%).

That question was out of the math 137 textbook, as I was trying to learn how to do Delta-Epsilon proofs.
Author:  Andy [ Tue Oct 19, 2004 7:08 pm ]
Post subject: 
y not just pay bugz a visit
Author:  Brightguy [ Tue Oct 19, 2004 7:42 pm ]
Post subject:  Re: [contest] 10 bit math questions
So the advanced courses are actually a lot different, then? I'm guessing there are a lot of proofs. Anyway, here goes this one:

For all ε > 0 we must find a δ > 0 such that, for all x,
0 < |x - (-2)| < δ ⇒ |(x² - 1) - 3| < ε

This simplifies to showing that there exits a δ so that:
If 0 < |x + 2| < δ then |x - 2||x + 2| < ε

Now, if |x + 2| < 1, then
-1 < x + 2 < 1
-5 < x - 2 < -3
|x - 2| < 5
and |x - 2||x + 2| < 5|x + 2|
but we want to show: |x - 2||x + 2| < ε
We can get this is true if |x + 2| < ε/5, because then
|x - 2||x + 2| < 5(ε/5)
|x - 2||x + 2| < ε

So, we have shown that if |x + 2| < 1 and |x + 2| < ε/5, then |x - 2||x + 2| < ε
So, take δ = 1 or ε/5, whichever is lower. Then, the following must be true:
0 < |x + 2| < δ ⇒ |x - 2||x + 2| < ε

So, by definition of a limit,
lim
x→-2 (x² - 1) = 3

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy