Challenge Micromass' big probability challenge

[ProfuselyQuarky]

I have a stick of $1$ meter. I break this stick in $3$ pieces in such a way that every point of the stick has as much chance of being a break point. Find the probability that I can combine the three pieces into an obtuse triangle.

I am utterly dumbfounded by this one because you specified that the triangle must be obtuse.

The pieces of the $1$ meter stick (after the stick is broken in two places) has the side lengths $a$, $b$, and $(1-a-b)$. If the three parts are greater than half the meter stick, then you can't make a triangle. That leaves that no piece can be greater than half the meter stick, which I believe implies that there is a 25% chance that the meter stick can even make any sort of triangle. For instance, if you break the stick into equal thirds, you can get and equilateral triangle, but that's not obtuse!

Can't wait to see the answer to this one.

 

[micromass]

I am utterly dumbfounded by this one because you specified that the triangle must be obtuse.

The pieces of the $1$ meter stick (after the stick is broken in two places) has the side lengths $a$, $b$, and $(1-a-b)$. If the three parts are greater than half the meter stick, than you can't make a triangle. That leaves that no piece can be greater than half the meter stick, which I believe implies that there is a 25% chance that the meter stick can even make any sort of triangle. For instance, if you break the stick into equal thirds, you can get and equilateral triangle, but that's not obtuse!

Can't wait to see the answer to this one.

How can three pieces be larger than half the meter stick? Won't you need 1.5 meters for that?

 

[micromass]

I have removed two questions since they are about statistics and not about probability. Don't worry, I will post them in a statistics challenge soon!

 

[ProfuselyQuarky]

How can three pieces be larger than half the meter stick? Won't you need 1.5 meters for that?

I meant a piece being greater than HALF of the stick. Sorry.

 

[CrackerMcGinger]

I am utterly dumbfounded by this one because you specified that the triangle must be obtuse.

The pieces of the $1$ meter stick (after the stick is broken in two places) has the side lengths $a$, $b$, and $(1-a-b)$. If the three parts are greater than half the meter stick, than you can't make a triangle. That leaves that no piece can be greater than half the meter stick, which I believe implies that there is a 25% chance that the meter stick can even make any sort of triangle. For instance, if you break the stick into equal thirds, you can get and equilateral triangle, but that's not obtuse!

Can't wait to see the answer to this one.

Well, what is the probability of a stick being broken into three unequal parts, one shorter, one longer, and another shorter again? If it has a probability that each point of the stick can be broken, then what's the probability that the stick can be broken into 3 equal parts?

 

[mrspeedybob]

#3
I would expect the ball numbers to be distributed randomly though the range of possible ball numbers. Since they can be put in numerical order, regardless of the order picked, then let b1 be the smallest ball, b5 be the largest ball, and t be the total number of balls.
I would expect that on average b1=t/6, b2=2t/6, b3=3t/6 etc, so the average difference between consecutive balls would be t/6
In the example you gave the differences are...
10-0=10, 50-10=40, 104-50=54, 130-104=26, and 213=130=83
The average spacing is 42.6 so I would expect the total to be 255.6
Since I can't actually have .6 balls I would have to say 256.

 

[CrackerMcGinger]

Hey! Can someone break a meter stick into three pieces 100 times for me and tell us the results! That would be great.

 

[micromass]

#3
I would expect the ball numbers to be distributed randomly though the range of possible ball numbers. Since they can be put in numerical order, regardless of the order picked, then let b1 be the smallest ball, b5 be the largest ball, and t be the total number of balls.
I would expect that on average b1=t/6, b2=2t/6, b3=3t/6 etc, so the average difference between consecutive balls would be t/6
In the example you gave the differences are...
10-0=10, 50-10=40, 104-50=54, 130-104=26, and 213=130=83
The average spacing is 42.6 so I would expect the total to be 255.6
Since I can't actually have .6 balls I would have to say 256.

Sorry, I removed that question. But I will post a new challenge soon which contains this very question. You should post it there.

 

[thephystudent]

I understand what you're saying, but I'm not sure how to formalize this... Not that BiGy's answer is all that formal. In either case, BiGy's answer is closer to yours, I'm afraid.

It seems to me the more formal solution can be found here http://link.springer.com/article/10.1007/BF02762038. But it seems rather technical, so I'm not going to try to apply those results on your Monk's problem for now.

 

[thephystudent]

Hey! Can someone break a meter stick into three pieces 100 times for me and tell us the results! That would be great.

Hopefully the experiment will give this result?

I used https://www.artofproblemsolving.com/wiki/index.php?title=Pythagorean_Inequality and the constraint a+b+c=1, where all numbers are positive.

My result is
$$P=\int_0^1 dc \int_0^1 db \int_0^1 da \Theta(c^2-a^2-b^2)\Theta(c) \delta(a+b+c-1) \approx 0.15 ,$$

where $\Theta$ is a heaviside-function and $\delta$ a dirac delta

I am a bit cautious about a proportionality constant resulting from permutation of the three parts, but after every two cuts you can always identify the largest part and call it c.

 

[CrackerMcGinger]

Hopefully the experiment will give this result?

I used https://www.artofproblemsolving.com/wiki/index.php?title=Pythagorean_Inequality and the constraint a+b+c=1, where all numbers are positive.

My result is
$$P=\int_0^1 dc \int_0^1 db \int_0^1 da \Theta(c^2-a^2-b^2)\Theta(c) \delta(a+b+c-1) \approx 0.15 ,$$

where $\Theta$ is a heaviside-function and $\delta$ a dirac delta

I am a bit cautious about a proportionality constant resulting from permutation of the three parts, but after every two cuts you can always identify the largest part and call it c.

Can you rephrase that in simpler terms so I can understand what you said.

 

[micromass]

Hopefully the experiment will give this result?

I used https://www.artofproblemsolving.com/wiki/index.php?title=Pythagorean_Inequality and the constraint a+b+c=1, where all numbers are positive.

My result is
$$P=\int_0^1 dc \int_0^1 db \int_0^1 da \Theta(c^2-a^2-b^2)\Theta(c) \delta(a+b+c-1) \approx 0.15 ,$$

where $\Theta$ is a heaviside-function and $\delta$ a dirac delta

I am a bit cautious about a proportionality constant resulting from permutation of the three parts, but after every two cuts you can always identify the largest part and call it c.

Close, but not correct.

 

[thephystudent]

Close, but not correct.

First of all $\Theta (c)$ is abundant since I already included it in the integration border.

Secondly, to calculate the total volume of probability space, a and b can only run from 0 to c if c is defined as the longest one, so

$$N^{-1}=\int_0^1dc c^2=1/3$$, which would result in a probability of 0.45, a number that seems quite reasonable to me.

Can you rephrase that in simpler terms so I can understand what you said.

Ok, I just 'counted' the possibilities that it is true that a triangle is obtuse, and because a,b,c are continuous this counting becomes integrals. The $\delta$-function fixes a+b+c=1 and the $\Theta$-function makes sure c^2>a^2+b^2. You could also write it down just with substitutions presumably, but it looks less concise than to my opinion. The $N$ I calculated here is the total number of a,b,c configurations when c is the biggest, so the previous result should be divided by this one

 

[micromass]

First of all $\Theta (c)$ is abundant since I already included it in the integration border.

Secondly, to calculate the total volume of probability space, a and b can only run from 0 to c if c is defined as the longest one, so

$$N^{-1}=\int_0^1dc c^2=1/3$$, which would result in a probability of 0.45, a number that seems quite reasonable to me.

Sorry, that is also not the correct answer.

 

[Fightfish]

For number 7, the instinctive approach is to define a recurrence relation to count the number of scenarios in which Trump always has more votes than Hillary:
f(x,y) = \begin{cases} 1 \qquad \mathrm{if}\qquad y = 0 \\ 0 \qquad \mathrm{if}\qquad x = y \\ f(x-1,y) + f(x,y-1) \qquad \mathrm{otherwise} \end{cases}
where $x$ and $y$ are the total number of votes that Trump and Hillary have respectively.

However, this quickly becomes intractable for large values of $x$ and $y$, so there must be some way to simplify the recurrence relation - although at first glance I don't see how. By some reverse engineering though, it seems that
f(x,y) = \frac{(x-y)(x+y-1)!}{x!y!}
although I have been unable to prove it rigorously so far.

This gives a simple result for the probability as
P(x,y) = \frac{x-y}{x+y}

 

[micromass]

For number 7, the instinctive approach is to define a recurrence relation to count the number of scenarios in which Trump always has more votes than Hillary:
f(x,y) = \begin{cases} 1 \qquad \mathrm{if}\qquad y = 0 \\ 0 \qquad \mathrm{if}\qquad x = y \\ f(x-1,y) + f(x,y-1) \qquad \mathrm{otherwise} \end{cases}
where $x$ and $y$ are the total number of votes that Trump and Hillary have respectively.

However, this quickly becomes intractable for large values of $x$ and $y$, so there must be some way to simplify the recurrence relation - although at first glance I don't see how. By some reverse engineering though, it seems that
f(x,y) = \frac{(x-y)(x+y-1)!}{x!y!}
although I have been unable to prove it rigorously so far.

This gives a simple result for the probability as
P(x,y) = \frac{x-y}{x+y}

That is correct. I will credit you and anybody else who is able to prove this rigorously.

 

[PeroK]

Amended answer for number 4 (100 pairs this time):

To have exactly one complete pair, you need one pair and six odd shoes. The pair is equally likely to be any two shoes, from the 1st and 2nd to the 7th and 8th. There are, therefore, $\binom{8}{2} = 28$ equally likely ways to get a pair.

The probability that the 1st and 2nd shoes are the pair is:

$p_{12} = \frac{200}{200} \times \frac{1}{199} \times \frac{198}{198} \times \frac{196}{197} \times \frac{194}{196} \times \frac{192}{195} \times \frac{190}{194} \times \frac{188}{193}$

Hence, the total probablity that there is exactly one pair is:

$p = 28 \times p_{12} = 0.13$

 

[QuantumQuest]

Problem 4

There are 100 ways of choosing 1 pair of shoes from 100 pairs. Because we have to choose exactly one complete pair, for all the remaining shoes we cannot have a match, so there are $99 \choose 6$ ways to choose pairs for the remaining shoes. Now, in order to select individual shoes from the six pairs the possible ways are $2^6$. So, if we multiply $99 \choose 6$ $\cdot 100 \cdot 2^6$ and divide by the number of possible ways of selecting 8 shoes we get what is asked:

$\frac {{99 \choose 6} \cdot 100 \cdot 2^6}{200 \choose 8} \approx 0.130154$

 

[PeroK]

I understand what you're saying, but I'm not sure how to formalize this... Not that BiGy's answer is all that formal. In either case, BiGy's answer is closer to yours, I'm afraid.

For question 1:

1) If the game is to toss a coin until you get a tail, then the average length of the game is $2$, as was seen in the cereal box problem. So, the Monk gets approx $2.16 \times 10^{17}$ games.

2) The probability of getting a run of exactly $54$ heads followed by a tail in anyone game is $2^{-55} = 2.78 \times 10^{-17}$. That's once every $3.6 \times 10^{16}$ games. The Monk would expect to get a run of exactly $54$ heads $6$ times.

Similarly: A run of $55$ heads $3$ times; $56$ heads $1.5$ times; $57$ heads $0.75$ times etc.

I'm not sure how to calculate this precisely, but using a bit of estimating I got an expected value of $57.4$

 

[PeroK]

Problem 4

There are 100 ways of choosing 1 pair of shoes from 100 pairs. Because we have to choose exactly one complete pair, for all the remaining shoes we cannot have a match, so there are $99 \choose 6$ ways to choose pairs for the remaining shoes. Now, in order to select individual shoes from the six pairs the possible ways are $2^6$. So, if we multiply $99 \choose 6$ $\cdot 100 \cdot 2^6$ and divide by the number of possible ways of selecting 8 shoes we get what is asked:

$\frac {{99 \choose 6} \cdot 100 \cdot 2^6}{200 \choose 8} \approx 0.130154$

We're in agreement then!

 

[PeroK]

So here's my thinking (not a huge probability guy, so I might be missing something, but I think this makes sense):

We want to find the number of consecutive heads/tails such that the probability is 1 in 4.320432x10^17. The probability of flipping 1 heads is 1/2, the probability of two is (1/2)^2, and the probability of n heads is (1/2)^n. So we have (1/2)^n = 1/4.320432x10^(17)
or
$2^n = 4.320432E17$
$\text{log}_2(2^n) = \text{log}_2(4.320432E17)$ which gives us about $n=58.584$ which honestly seems a little low to me. But that's my guess, anyways.

I think you might have missed that to get exactly $n$ heads, you also need to follow up the heads with a tail. So, what you calculated is $n+1 = 58.584$.

 

[andrewkirk]

Here's my attempt at Problem 4:

The number of different 8-shoe sequences that can be picked in 8 selections is T\equiv P^{200}_8=\frac{200!}{(200-8)!}

The number of those that have exactly one pair is the product of the following factors:

• (number of different pairs that could be the complete pair)
• (number of different ordered pairs of integers from {1,...,8} without replacement that could denote the pick numbers of the left and right shoes in the complete picked pair)
  
• (number of different ordered 6-tuples from {1,...,99} without replacement that could denote the pairs from which the six picked unpaired shoes come)
  
• (number of different ordered 6-tuples from {left,right} with replacement that could denote which foot each picked, unpaired shoe is for)

This is

$$R\equiv 100\times P^8_2\times P^{99}_6\times 2^6$$

So the probability of picking exactly one pair from eight picks is $R/T$.

A quick calc tells me this is about 13%.

 

[andrewkirk]

Here's my attempt at number 6:

The number of spots in which aces can be placed is

$$N=\sum_{i=1}^{52-6}\ \ \sum_{j=i+2}^{52-4}\ \ \sum_{k=j+2}^{52-2}\ \ \sum_{l=k+2}^{52-0}1=
\sum_{i=1}^{52-6}\ \ \sum_{j=i+2}^{52-4}\ \ \sum_{k=j+2}^{52-2}\ \ (54-k)$$

The outer sum is over possible positions for the first ace, the sum inside that over possible positions for the second ace, and so on. The deductions from the upper sum limits are to leave room for the remaining aces without any of them being adjacent. The lower sum limits are to leave at least one space between this ace and the preceding one.

So the number of arrangements with no aces adjacent is

N x
(number of different orders for the four aces) x
(number of different orders for the remaining 48 cards)

This is
$$R=N\times 4!\times 48!$$

The probability of this occurring will be

$$\frac{R}{52!}=\frac{24N}{52\cdot 51\cdot 50\cdot 49}$$

My calc is that N=263,764, in which case the probability would be 97%. That's surprisingly high. I'll have to check.

 

[andrewkirk]

Here is my partial attempt at 8.

The probability will be $3!=6$ times $R$ where $R$ is the probability that the first piece is the longest, the third piece the shortest and an obtuse triangle is formed. That factor of six allows for the different possible orderings of the pieces.

Then, letting x and y be the coordinates of the first and second breaks, we have

$$R=\int_{1/3}^{1/2}\int_{\frac{x+1}2}^{2x}\chi_A((x,y))dy\ dx$$

where $A=\{(x,y)\in\mathbb R^2\ |\ x^2>(y-x)^2+(1-y)^2\}$ is the requirement that the triangle be obtuse (there are points in A that are not triangles, but that doesn't matter because the integration limits ensure triangularity.

The integral limits are necessary and sufficient conditions for the first piece to be the longest, the second to be the next longest and for a triangle to be formed.

1. lower outer limit could have been 0 but, because of the inner limits, the integrand will be zero if x is in [0,1/3], so we might as well set the limit to 1/3.
   
2. upper outer limit is necessary for a triangle to be possible (triangle inequality)
3. lower inner limit is necessary and sufficient for the 3rd piece to be shorter than the 2nd
4. upper inner limit is necessary and sufficient for 2nd piece to be shorter than 1st

Limits 3 and 4 together ensure that 1st length > 2nd length > 3rd length.

My problem is that I can't yet see an analytic formulation of the indicator function $\chi_A$.

A crude numerical integration gives a number between $8\frac12$% and 9%.

 

[fresh_42]

Here is my partial attempt at 8.

The probability will be $3!=6$ times $R$ where $R$ is the probability that the first piece is the longest, the third piece the shortest and an obtuse triangle is formed. That factor of six allows for the different possible orderings of the pieces.

Then, letting x and y be the coordinates of the first and second breaks, we have

$$R=\int_{1/3}^{1/2}\int_{\frac{x+1}2}^{2x}\chi_A((x,y))dy\ dx$$

where $A=\{(x,y)\in\mathbb R^2\ |\ x^2>(y-x)^2+(1-y)^2\}$ is the requirement that the triangle be obtuse (there are points in A that are not triangles, but that doesn't matter because the integration limits ensure triangularity.

The integral limits are necessary and sufficient conditions for the first piece to be the longest, the second to be the next longest and for a triangle to be formed. My problem is that I can't yet see an analytic formulation of the indicator function $\chi_A$.

A crude numerical integration gives a number between $8\frac12$% and 9%.

You can transform $x^2>(y-x)^2+(1-y)^2$ into $uv > 1$. Could this help?

 

[micromass]

Amended answer for number 4 (100 pairs this time):

To have exactly one complete pair, you need one pair and six odd shoes. The pair is equally likely to be any two shoes, from the 1st and 2nd to the 7th and 8th. There are, therefore, $\binom{8}{2} = 28$ equally likely ways to get a pair.

The probability that the 1st and 2nd shoes are the pair is:

$p_{12} = \frac{200}{200} \times \frac{1}{199} \times \frac{198}{198} \times \frac{196}{197} \times \frac{194}{196} \times \frac{192}{195} \times \frac{190}{194} \times \frac{188}{193}$

Hence, the total probablity that there is exactly one pair is:

$p = 28 \times p_{12} = 0.13$

Problem 4

There are 100 ways of choosing 1 pair of shoes from 100 pairs. Because we have to choose exactly one complete pair, for all the remaining shoes we cannot have a match, so there are $99 \choose 6$ ways to choose pairs for the remaining shoes. Now, in order to select individual shoes from the six pairs the possible ways are $2^6$. So, if we multiply $99 \choose 6$ $\cdot 100 \cdot 2^6$ and divide by the number of possible ways of selecting 8 shoes we get what is asked:

$\frac {{99 \choose 6} \cdot 100 \cdot 2^6}{200 \choose 8} \approx 0.130154$

Those replies are both correct. I'm afraid for QuantumQuest that PeroK was first though, so he gets credited.

 

[micromass]

Here's my attempt at Problem 4:

The number of different 8-shoe sequences that can be picked in 8 selections is T\equiv P^{200}_8=\frac{200!}{(200-8)!}

The number of those that have exactly one pair is the product of the following factors:

• (number of different pairs that could be the complete pair)
• (number of different ordered pairs of integers from {1,...,8} without replacement that could denote the pick numbers of the left and right shoes in the complete picked pair)
  
• (number of different ordered 6-tuples from {1,...,99} without replacement that could denote the pairs from which the six picked unpaired shoes come)
  
• (number of different ordered 6-tuples from {left,right} with replacement that could denote which foot each picked, unpaired shoe is for)

This is

$$R\equiv 100\times P^8_2\times P^{99}_6\times 2^6$$

So the probability of picking exactly one pair from eight picks is $R/T$.

A quick calc tells me this is about 13%.

Correct, but PeroK was first.

Here's my attempt at number 6:

The number of spots in which aces can be placed is

$$N=\sum_{i=1}^{52-6}\ \ \sum_{j=i+2}^{52-4}\ \ \sum_{k=j+2}^{52-2}\ \ \sum_{l=k+2}^{52-0}1=
\sum_{i=1}^{52-6}\ \ \sum_{j=i+2}^{52-4}\ \ \sum_{k=j+2}^{52-2}\ \ (54-k)$$

The outer sum is over possible positions for the first ace, the sum inside that over possible positions for the second ace, and so on. The deductions from the upper sum limits are to leave room for the remaining aces without any of them being adjacent. The lower sum limits are to leave at least one space between this ace and the preceding one.

So the number of arrangements with no aces adjacent is

N x
(number of different orders for the four aces) x
(number of different orders for the remaining 48 cards)

This is
$$R=N\times 4!\times 48!$$

The probability of this occurring will be

$$\frac{R}{52!}=\frac{24N}{52\cdot 51\cdot 50\cdot 49}$$

My calc is that N=263,764, in which case the probability would be 97%. That's surprisingly high. I'll have to check.

That number is too high.

Here is my partial attempt at 8.

The probability will be $3!=6$ times $R$ where $R$ is the probability that the first piece is the longest, the third piece the shortest and an obtuse triangle is formed. That factor of six allows for the different possible orderings of the pieces.

Then, letting x and y be the coordinates of the first and second breaks, we have

$$R=\int_{1/3}^{1/2}\int_{\frac{x+1}2}^{2x}\chi_A((x,y))dy\ dx$$

where $A=\{(x,y)\in\mathbb R^2\ |\ x^2>(y-x)^2+(1-y)^2\}$ is the requirement that the triangle be obtuse (there are points in A that are not triangles, but that doesn't matter because the integration limits ensure triangularity.

The integral limits are necessary and sufficient conditions for the first piece to be the longest, the second to be the next longest and for a triangle to be formed.

1. lower outer limit could have been 0 but, because of the inner limits, the integrand will be zero if x is in [0,1/3], so we might as well set the limit to 1/3.
   
2. upper outer limit is necessary for a triangle to be possible (triangle inequality)
3. lower inner limit is necessary and sufficient for the 3rd piece to be shorter than the 2nd
4. upper inner limit is necessary and sufficient for 2nd piece to be shorter than 1st

Limits 3 and 4 together ensure that 1st length > 2nd length > 3rd length.

My problem is that I can't yet see an analytic formulation of the indicator function $\chi_A$.

A crude numerical integration gives a number between $8\frac12$% and 9%.

All I will say now is that the correct answer is not between your two limits.

 

[andrewkirk]

On problem 6, prompted by MM's observation, I see that my summand (54-k) is incorrect. Since the previous ace was in position k, there are only 52-(k+1) =51-k remaining valid places for the last ace.

The calc using that summand instead gives N=211,876.
That would give the probabiity as $\frac{24N}{52\cdot 51\cdot 50\cdot 49}$ which is 78%.

 

[micromass]

On problem 6, prompted by MM's observation, I see that my summand (54-k) is incorrect. Since the previous ace was in position k, there are only 52-(k+1) =51-k remaining valid places for the last ace.

The calc using that summand instead gives N=211,876.
That would give the probabiity as $\frac{24N}{52\cdot 51\cdot 50\cdot 49}$ which is 78%.

Very good. The answer is in fact
\frac{49\cdot 48\cdot 47\cdot 46}{52\cdot 51\cdot 50\cdot 49}
A simple reasoning for this short expression will be given in the OP.

 

[andrewkirk]

All I will say now is that the correct answer is not between your two limits.

On problem 8, I see from a brute force calc that my answer appears to be three times what I think it should be. It looks like I should have multiplied R by 2 rather than by 6, but I can't immediately see why. I must have done something silly in working out the different orders the lengths could be and how that affects the probability. I'll think about that later.

But I have a method that avoids assuming an order, in which the probability of an obtuse triangle is as follows:

$$\int_0^{\frac12}\int_{\frac12}^{x+\frac12} \chi_A\ dy\ dx$$

the integration limits collectively ensure that no side is longer than 1/2, and hence that a triangle can be formed. The indicator function $\chi_A$ requires the triangle to be obtuse.

The answer I get from a numerical integration on that is about 2.9%. That's the same as for my brute force calc and one third of my erroneous answer above.

EDIT: I think there may still be an error in this. Can you hold off commenting please MicroMass until I've thought about it a little more? I could have deleted it but decided it's better not to since it has already been quoted.
A bit later: I've confirmed it needs correction, because

1. it doesn't allow for the fact that any of the three sides could be opposite the obtuse angles; and
2. it needs to be doubled, since it assumes the cut that relates to the outer integral will be closer to the left end than the other cut.

I'll post the corrected version in a new post.